Cryptography Reference
In-Depth Information
Definition 12.1.1
An integer
N
∈ N
is a
Carmichael number
if
N
is composite and
a
N
−
1
≡
1(mod
N
)
for all
a
∈ N
such that gcd(
a,N
)
=
1.
=
l
i
=
1
p
e
i
i
is composite then
G
m
(
)
=
l
i
=
1
G
m
(
/p
e
i
Z
If
N
Z
/N
Z
Z
) and has order
ϕ
(
N
)
p
e
i
−
1
i
and exponent
λ
(
N
)
=
lcm
{
(
p
i
−
1) : 1
≤
i
≤
l
}
.
Exercise 12.1.2
Show that all Carmichael numbers are odd. Show that
N
is a Carmichael
number if and only if
λ
(
N
)
|
(
N
−
1). Show that a composite number
N
∈ N
is a Carmichael
=
l
i
=
1
p
i
is a product of distinct primes such that (
p
i
−
number if and only if
N
1)
|
(
N
−
1) for
i
=
1
,...,l
.
Exercise 12.1.3
Show that 561
=
3
·
11
·
17 is a Carmichael number.
It was shown by Alford, Granville and Pomerance in 1992 that there are infinitely many
Carmichael numbers.
It is natural to replace
G
m
(
Z
Z
/N
) with any algebraic group or algebraic group quotient,
such as the torus
T
2
, the algebraic group quotient corresponding to Lucas sequences (this
gives rise to the
p
+
1 test) or an elliptic curve of predictable group order.
Exercise 12.1.4
Design a primality test based on the algebraic group
T
2
(
Z
/N
Z
), which
has order
N
1if
N
is prime. Also show to use Lucas sequences to test
N
for primality
using the algebraic group quotient.
+
Exercise 12.1.5
Design a primality test for integers
N
≡
3 (mod 4) based on the algebraic
group
E
(
Z
/N
Z
) where
E
is a suitably chosen supersingular elliptic curve.
Exercise 12.1.6
Design a primality test for integers
N
≡
1 (mod 4) based on the algebraic
group
E
(
Z
/N
Z
) where
E
is a suitably chosen elliptic curve.
12.1.2 The Miller-Rabin test
This primality test is also called the Selfridge-Miller-Rabin test or the strong prime test.
It is a refinement of the Fermat test, and works very well in practice. Rather than changing
the algebraic group, the idea is to make better use of the available information. It is based
on the following trivial lemma, which is false if
p
is replaced by a composite number
N
(except for
N
p
a
where
p
is odd).
=
Lemma 12.1.7
Let p be prime. If x
2
≡
1(mod
p
)
then x
≡±
1(mod
p
)
.
2
b
m
where
m
is odd and consider the
For the Miller-Rabin test write
N
−
1
=
a
m
(mod
N
),
a
1
=
a
0
=
a
2
m
(mod
N
), ...,
a
b
=
a
b
−
1
=
a
N
−
1
sequence
a
0
=
(mod
N
)
where gcd(
a,N
)
=
1. If
N
is prime then this sequence must have the form (
∗
,
∗
,...,
∗
,
−
1
,
1
,...,
1) or (
denotes numbers whose values are not
relevant). Any deviation from this form means that the number
N
is composite.
−
1
,
1
,...,
1) or (1
,...,
1) (where
∗
