Cryptography Reference
In-Depth Information
Artin's Conjecture
If n
N
is not a perfect square, then the number of primes q
m for which
ord q ( n )= q
1 is asymptotically A ( n )
·
m/ ln( m ), where A ( n )is Artin's
constant given by
1
=0 . 3739558136 ...,
A ( n )=
1
p k ( p k
1)
j =1
with p k being the k th prime.
If Artin's conjecture becomes effective for m = O (log 2 ( n )), then it follows
that there is an r = O (log 2 ( n )) with the desired properties.
The other conjecture that supports their contention is given as follows.
Sophie Germane's Prime Density Conjecture
The number of primes q
m such that 2 q +1 a is also a prime is asymptotically
2 C 2 m/ ln 2 ( m ), where C 2 is the twin prime constant given by
C 2 =
p 3
p ( p
2)
1) 2
0 . 6601611816 ....
( p
a Such primes are called Sophie Germane primes .
If the Sophie Germane conjecture holds, then r = O (log 2+ ε
2
( n )) for any ε> 0
4 log 2 ( n ). Hence, the algorithm, with this r value, yields a
time complexity of O (log 6+ 2 ( n )) for any ε> 0.
The authors of [6]leave one more conjecture, the aGrmative solution of
which would improve the complexity of algorithm F.1 to O (log 3+ ε
2
such that ord r ( n )
( n )) for any
ε> 0.
Conjecture F.1 If r is a prime not dividing n> 1 and if
1) n = X n
1 (mod X r
( X
1 ,n ) ,
then either n is prime or n 2
1 (mod r ) .
The result given in Algorithm F.1 is a major breakthrough and the simplicity
of the approach is even more noteworthy given the attempts at finding such an
algorithm through much more diGcult techniques such as those discussed in the
previous section. The algorithm uses essentially only elementary properties of
polynomial rings over finite fields and a generalization of Fermat's little theorem
in that context, quite impressive indeed.
The next section deals with the generation of random primes, another im-
portant feature in the recognition of primes.
Search WWH ::




Custom Search