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
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
KEYWORD
nonn
AUTHOR
Alexander Fraebel, Oct 24 2020
STATUS
approved