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

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

Offset: 1

Author

Alexander Fraebel, Oct 24 2020

Keywords

• nonn

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.

Examples

			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.
		

Links

• Hugo Pfoertner, Table of n, a(n) for n = 1..10000
• L. Blum, M. Blum, and M. Shub, Comparison of Two Pseudo-Random Number Generators, In: D. Chaum, R. L. Rivest, A. T. Sherman (eds) Advances in Cryptology. Springer, Boston, MA (1983).
• Wikipedia, Blum Blum Shub

Crossrefs

Cf. A016105.

Programs

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

Python

from sympy.ntheory import legendre_symbol, isprime, sieve
def A338407(N):
    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()