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,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

Table of n, a(n) for n=1..34.

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

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 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()
(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

Sequence in context: A251795 A092135 A077740 * A078214 A251199 A220334

Adjacent sequences: A338404 A338405 A338406 * A338408 A338409 A338410

Keyword

nonn

Author

Alexander Fraebel, Oct 24 2020

Status

approved