Alexander Fraebel - cp's OEIS frontend

User: Alexander Fraebel

Alexander Fraebel has authored 2 sequences.

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

Alexander Fraebel, Oct 24 2020

nonn

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.

			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.

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

Cf. A016105.

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

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

A337308 Natural numbers that yield a coprime pair representing a proper fraction under the inverse of Cantor's pairing function.

Original entry on oeis.org

8, 13, 18, 19, 26, 32, 33, 34, 41, 43, 50, 52, 53, 62, 64, 72, 73, 74, 75, 76, 85, 89, 98, 99, 100, 101, 102, 103, 114, 116, 118, 128, 131, 133, 134, 145, 147, 149, 151, 162, 163, 164, 165, 166, 167, 168, 169, 182, 184, 188, 200, 201, 202, 203, 204, 205, 206

Offset: 1

Alexander Fraebel, Aug 22 2020

nonn

Equivalently: The image of the function f(x,y)=(x+y)*(x+y+1)/2+y for x,y coprime and 0 < x < y.

			The fully reduced proper fraction 2/5 is mapped to 33 by Cantor's pairing function.

Wikipedia, Cantor's pairing function.

Superset of A277557.

# Edited by M. F. Hasler, Mar 25 2023
from math import gcd
def A337308_first(N):
    L, b = [], 0
    f = lambda a: (a + b) * (a + b + 1) // 2 + b
    while N > 0:
        b += 1
        if len(L) > 1:
            L.sort()
            while L and L[0] < f(1):
                yield L.pop(0)
                N -= 1
        L.extend(f(a) for a in range(1, b) if gcd(a, b) == 1)
print(list(A337308_first(50)))

cp's OEIS Frontend

User: Alexander Fraebel

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python