SafePrimes.html

Safe Primes

ŠMike May, S.J., 2002, maymk@slu.edu

> restart;

For various public key cryptosystems, we want a large prime p where p-1 has a sufficiently large factor. It is worthwhile to explore how we can find such primes efficiently.

Efficiently finding 2-primes

We want to begin with a test that is fairly efficient and generally finds a prime. We recall that for any random composite n we tested 2^(n-1) was not congruent to 1 mod (n-1). This leads to a simple test for numbers that are probably prime.

> test := rand(10^100)();
if((test mod 2) = 0) then test := test + 1 fi:
while((Power(2,test-1) mod test)<>1) do
test := test + 2:
od:
test;
isprime(test);

The test is fairly inefficient, since with each odd candidatewe use modular exponentiation of 2 to a large power, which is a long operation. We would like to eliminate most candidates by noting that they share a factor with a small prime. To do that we compute the product of the primes less than 100, and the primes from 100 to 1000.

> smallPrimes := 2:
testp := 2:
while (testp < 100) do
testp := nextprime(testp):
smallPrimes := smallPrimes*testp:
od:
smallPrimes:
medPrimes := 101:
testp := 101:
while (testp < 1000) do
testp := nextprime(testp):
medPrimes := medPrimes*testp:
od:
medPrimes:

This gives a faster test for 2-primes, which we turn into a procedure.

>    next2prime := proc(n)
   local test, doneTest:
   test := n:
   if((test mod 2) = 0) then test := test + 1 fi:
   doneTest := 0:
   while (doneTest = 0) do
      if (igcd(smallPrimes,test)<>1) then test := test + 2:
      elif (igcd(medPrimes,test)<>1) then test := test + 2:
      elif ((Power(2,test-1) mod test)<>1) then test := test + 2:
      else doneTest := 1: fi:
   od:
   test;
end:

Finding safe 2-primes. (p=2*q+1)

Ideally, for El Gamal, we would like to use a safe or Noether prime. These have the form form 2q+1 where q is also prime. These primes are obviously rarer, so it will take longer to find them. Thus our first pass at a procedure to find these primes will print out progress reports after every 20 q that we try.

>    test:= next2prime(rand(10^50)());
   doneTest := 0:
   count := 1;
   while (doneTest = 0) do
      test2 := 2*test+1;
      if (igcd(smallPrimes,test2)<>1) then
         test := next2prime(test+2):
         count := count +1:
      elif (igcd(medPrimes,test2)<>1) then
         test := next2prime(test+2):
         count := count +1:
      elif ((Power(2,test2-1) mod test2)<>1) then
         test := next2prime(test+2):
         count := count +1:
      else doneTest := 1: fi:
      if (count mod 20 = 0) then print(count, test, test2) fi;
   od:
print(count, test, test2);
isprime(test2);
test2;

>    nextsafe2prime := proc(n)
   local test, test2, doneTest:
   doneTest := 0:
   test := iquo(n,2)+1:
   test2 := 2*test+1;
   while (doneTest = 0) do
      test2 := 2*test+1;
      if (igcd(smallPrimes,test2)<>1) then
         test := next2prime(test+2):
      elif (igcd(medPrimes,test2)<>1) then
         test := next2prime(test+2):
      elif ((Power(2,test2-1) mod test2)<>1) then
         test := next2prime(test+2):
      else doneTest := 1: fi:
   od:
   test2;
end:

> p1 := nextsafe2prime(rand(10^40)());
isprime(p1);
numtheory[factorset](p1-1);

Finding primes where p-1 has a large prime factor.

For other uses we don't need to restrict our primes so tightly. Generally, we simply want a prime of the form p=qk+1 where q is sufficiently large. Suppose we want a 100 digit prime of this form where q should be 40 digits.

>    q := next2prime(rand(10^39..10^40)());
k := rand(10^60)();
   doneTest := 0:
   count := 1;
   while (doneTest = 0) do
   test := 2*q*k+1;
      if (igcd(smallPrimes,test)<>1) then
         k := k+1:
         count := count +1:
      elif (igcd(medPrimes,test)<>1) then
         k := k+1:
         count := count +1:
      elif ((Power(2,test-1) mod test)<>1) then
         k := k+1:
         count := count +1:
      else doneTest := 1: fi:
      if (count mod 50 = 0) then print(count, test) fi;
   od:
print(count, q, k, test);
isprime(test);
test;

>    nextnice2prime := proc(qstart, kstart)
   local q, k, test, test2, doneTest:
   q := next2prime(qstart);
   k := kstart;
   doneTest := 0:
   while (doneTest = 0) do
   test := 2*q*k+1;
      if (igcd(smallPrimes,test)<>1) then
         k := k+1:
      elif (igcd(medPrimes,test)<>1) then
         k := k+1:
      elif ((Power(2,test-1) mod test)<>1) then
         k := k+1:
      else doneTest := 1: fi:
   od:
   [q, k, test];
end:

For digital signatures, we will ant p to be chosen as a 512 bit prime of the form p=qk+1 where q is a 128 bit prime.

> p1 := nextnice2prime(rand(2^128)(),rand(2^384)());
isprime(p1[3]);

> p1[2];

>