cp's OEIS Frontend

A338407 Values m that allow maximum period in the Blum-Blum-Shub x^2 mod m pseudorandom number generator.

%I A338407 #38 May 27 2025 07:02:41
%S A338407 1081,3841,7849,8257,16537,16873,33097,46897,59953,66217,93817,94921,
%T A338407 95833,113137,120073,129697,133561,136321,139081,166681,173857,174961,
%U A338407 177721,226297,231193,240313,248377,258121,259417,265033,278569,317377,321241,325657
%N A338407 Values m that allow maximum period in the Blum-Blum-Shub x^2 mod m pseudorandom number generator.
%C A338407 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.
%C A338407 The length of the associated PRNG is up to psi(psi(n)), where psi is the reduced totient function.
%H A338407 Hugo Pfoertner, <a href="/A338407/b338407.txt">Table of n, a(n) for n = 1..10000</a>
%H A338407 L. Blum, M. Blum, and M. Shub, <a href="https://doi.org/10.1007/978-1-4757-0602-4_6">Comparison of Two Pseudo-Random Number Generators</a>, In: D. Chaum, R. L. Rivest, A. T. Sherman (eds) Advances in Cryptology. Springer, Boston, MA (1983).
%H A338407 Wikipedia, <a href="https://en.wikipedia.org/wiki/Blum_Blum_Shub">Blum Blum Shub</a>
%e A338407 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.
%e A338407 The associated PRNG has length up to psi(psi(1081)) = 110.
%o A338407 (Python)
%o A338407 from sympy.ntheory import legendre_symbol, isprime, sieve
%o A338407 def A338407(N):
%o A338407     def BBS_primes():
%o A338407         p = 1
%o A338407         S = sieve
%o A338407         while True:
%o A338407             p += 1
%o A338407             if p in S:
%o A338407                 if p%4 == 3:
%o A338407                     a = (p-1)//2
%o A338407                     b = (a-1)//2
%o A338407                     if a%2 == 1 and b % 2 == 1:
%o A338407                         if isprime(a) and isprime(b):
%o A338407                             yield p
%o A338407     S = []
%o A338407     K = {}
%o A338407     T = []
%o A338407     ctr = 0
%o A338407     for s in BBS_primes():
%o A338407         S.append(s)
%o A338407         K[s] = legendre_symbol(2,(s-1)//2)
%o A338407         while len(T) > 0 and T[0] < s*S[0]:
%o A338407             print(T.pop(0))
%o A338407             ctr += 1
%o A338407             if ctr >= N:
%o A338407                 return None
%o A338407         for t in S[:-1]:
%o A338407             if K[t] + K[s] != 2:
%o A338407                 T.append(t*s)
%o A338407         T.sort()
%o A338407 (PARI)
%o A338407 tf(r)={if(r%8==7 && isprime((r-1)/2) && isprime((r-3)/4), kronecker(2,r\2), 0)}
%o A338407 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)}
%o A338407 forstep(n=1, 10^6, 8, if(isok(n), print1(n, ", "))) \\ _Andrew Howroyd_, Oct 26 2020
%Y A338407 Cf. A016105.
%K A338407 nonn
%O A338407 1,1
%A A338407 _Alexander Fraebel_, Oct 24 2020