- (\(p-1\)) has a large prime factor of \(r\).
- (\(p+1\)) has a large prime factor of \(s\).
- (\(r-1\)) has a large prime factor of \(t\).
The following defines the Gordon method [1] of generating strong primes.
Strong Prime (Gordon Method)
[Primes Home][Home]
In RSA, we create a modulus of \(n=pq\), and where \(p\) and \(q\) are random prime numbers. A strong prime number (\(p\)) is when \(r\), \(s\) and \(t\) satisfy the following:
The following defines the Gordon method [1] of generating strong primes. |
In RSA, we create a modulus of \(n=pq\), and where \(p\) and \(q\) are random prime numbers. A strong prime number (\(p\)) is when \(r\), \(s\) and \(t\) satisfy the following:
The following defines the Gordon method of generating strong primes. First we generate two random prime numbers (\(s\) and \(t\)). Next we select an integer (\(i_0\)) and find the first prime number for:
\(r = 2it + 1\)
and where \(i=i_0\), \(i_0+1\), etc, until we find a prime number for \(r\). Next we calculate:
\(p_0=2(s^{r-2} \pmod r)s -1\)
We then select \(j_0\) and find the prime:
\(p=p_0+2jrs\)
and where \(j=j_0\), \(j_0+1\), etc, until we find a prime number for \(p\). The results in a strong prime (\(p\)).
The following is the code:
import libnum import sympy import random import sys from Crypto.Util.number import getPrime from Crypto.Random import get_random_bytes primebits=64 if (len(sys.argv)>1): primebits=int(sys.argv[1]) s = getPrime(primebits,randfunc=get_random_bytes) t = getPrime(primebits,randfunc=get_random_bytes) print (f"s={s}") print (f"t={t}") isPrime=False i=random.randint(0,100) while (isPrime==False): r=2*i*t+1 i=i+1 if (sympy.isprime(r)==True): isPrime=True print (f"r={r}") p_0 = 2*(pow(s,r-2,r))*s-1 print (f"\np_0={p_0}") isPrime=False j=random.randint(0,100) p=0 while (isPrime==False): p=p_0+2*j*r*s j=j+1 if (sympy.isprime(p)==True): isPrime=True print (f"p={p}") print ("\nFactor for (p-1) - should be r:",libnum.gcd(p-1,r)) print ("Factor for (p+1) - should be s:",libnum.gcd(p+1,s)) print ("Factor for (r-1) - should be t:",libnum.gcd(r-1,t))
And a sample run:
s=180722906533722548482289965482380623259 t=293191297304375253837496552816694324423 r=76229737299137565997749103732340524349981 p_0=6380374774948265635991206557691982570699538820845933133273466224000979536440407 p=3726024490805558973860011097960358532901927891736711483176276828910560148234621737 Factor for (p-1) - should be r: 76229737299137565997749103732340524349981 Factor for (p+1) - should be s: 180722906533722548482289965482380623259 Factor for (r-1) - should be t: 293191297304375253837496552816694324423
[1] Gordon, J. (1984, April). Strong primes are easy to find. In Workshop on the Theory and Application of of Cryptographic Techniques (pp. 216-223). Springer, Berlin, Heidelberg. [link].