|
|
A338407
|
|
Values m that allow maximum period in the Blum-Blum-Shub x^2 mod m pseudorandom number generator.
|
|
1
|
|
|
1081, 3841, 7849, 8257, 16537, 16873, 33097, 46897, 59953, 66217, 93817, 94921, 95833, 113137, 120073, 129697, 133561, 136321, 139081, 166681, 173857, 174961, 177721, 226297, 231193, 240313, 248377, 258121, 259417, 265033, 278569, 317377, 321241, 325657
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
Each term must be a semiprime. The prime factors must be distinct, congruent to 3 mod 4, and must satisfy two additional conditions. First, for each factor, F, there must exist primes p and q such that F = 2p+1 and p = 2q+1. Second, 2 can be a quadratic residue modulo p for at most one factor.
The length of the associated PRNG is up to psi(psi(n)), where psi is the reduced totient function.
|
|
LINKS
|
|
|
EXAMPLE
|
1081 is the product of the primes 23 and 47. Both of these numbers are congruent to 3 modulo 4. 23 = 2*11+1, 11 = 2*5+1, note that 2 is a quadratic nonresidue modulo 11. 47 = 2*23+1, 23 = 2*11+1, note that 2 is a quadratic residue modulo 23. Since only one relevant value has 2 as a quadratic residue, 1081 is a term.
The associated PRNG has length up to psi(psi(1081)) = 110.
|
|
PROG
|
(Python)
from sympy.ntheory import legendre_symbol, isprime, sieve
def BBS_primes():
p = 1
S = sieve
while True:
p += 1
if p in S:
if p%4 == 3:
a = (p-1)//2
b = (a-1)//2
if a%2 == 1 and b % 2 == 1:
if isprime(a) and isprime(b):
yield p
S = []
K = {}
T = []
ctr = 0
for s in BBS_primes():
S.append(s)
K[s] = legendre_symbol(2, (s-1)//2)
while len(T) > 0 and T[0] < s*S[0]:
print(T.pop(0))
ctr += 1
if ctr >= N:
return None
for t in S[:-1]:
if K[t] + K[s] != 2:
T.append(t*s)
T.sort()
(PARI)
tf(r)={if(r%8==7 && isprime((r-1)/2) && isprime((r-3)/4), kronecker(2, r\2), 0)}
isok(n)={if(n%8==1 && bigomega(n)==2 && !issquare(n), my(f=factor(n)[, 1], t1=tf(f[1]), t2=tf(f[2])); t1 && t2 && t1+t2!=2, 0)}
forstep(n=1, 10^6, 8, if(isok(n), print1(n, ", "))) \\ Andrew Howroyd, Oct 26 2020
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|