Cryptography Reference
In-Depth Information
F.3 Primes is in P
The following is an unconditional deterministic polynomial-time algorithm
for primality testing presented in [6]by M. Agrawal, N. Kayal, and N. Saxena.
For notation in what follows, see Appendix A, especially Definition A.22 on
page 479 and Definition A.23 on page 479, as well as results on polynomial
rings especially as they pertain to finite fields on pages 484-490.
In what follows,
Z
n
for a given integer
n>
1 denotes
Z
/n
Z
, and if
h
(
X
)
∈
Z
n
[
X
], then the notation,
f
(
X
)
≡
g
(
X
) (mod
h
(
X
)
,n
))
,
is used to represent the equation
f
(
X
)=
g
(
X
) in the quotient ring
Z
n
[
X
]
/
(
h
(
X
)). In particular, for suitably chosen
r
and
a
, values, we will be
looking at equation of the following type:
(
X
+
a
)
n
X
n
+
a
(mod
X
r
≡
−
1
,n
)
.
(F.2)
Algorithm F.1
—
Unconditional Deterministic Polynomial-Time Primality Test
Input an integer
n>
1
, and execute the following steps.
1. If
n
=
a
b
for some
a
∈
N
and
b>
1, then terminate with output
“
n
is composite”.
such that ord
r
(
n
)
>
4 log
2
n
.
2. Find the smallest
r
∈
N
3. If 1
<
gcd(
a,n
)
<n
for some
a
≤
r
, then output
“
n
is composite”.
4. If
n
≤
r
, then output
“
n
is prime”.
5. Set
a
= 1 and execute the following:
(
X
+
a
)
n
X
n
a
(mod
X
r
(i) Compute
Y
(
a
)
≡
−
−
−
1
,n
).
0 (mod
X
r
(ii) If
Y
(
a
)
≡
−
1
,n
), output
“
n
is composite”.
Otherwise, go to step (iii).
(iii) If
Y
(
a
)
2
φ
(
r
)
≡
0 (mod
X
r
−
·
1
,n
), set
a
=
a
+1. If
a<
log
2
(
n
)
, go to step (i). Otherwise, go to step 6.
6. Output
“
n
is prime”.
Search WWH ::
Custom Search