supersingular.py

# Use Sage inside Colab
#from sageall import *
from sage.all import *
import math
def is_supersingular_j(p, j):
    F = GF(p)
    jF = F(j)
    E = EllipticCurve_from_j(jF)
    n = E.cardinality()
    print("DEBUG2",p,j,F,jF,E,n)
    return (n - 1) % p == 0

def supersingular_js_Fp(p):
    F = GF(p)
    return [j for j in F if is_supersingular_j(p, j)]

def supersingular_js_Fp2(p):
    F2 = GF(p**2, 'a')
    S = set()
    for j in F2:
        E = EllipticCurve_from_j(j)
        n = E.cardinality()
        print("DEBUG3",p,F2,S,j,E,n)
        if (n - 1) % p == 0:
            S.add(j)
    return S
def is_ogg_prime(p):
    S_p  = set(supersingular_js_Fp(p))
    S_p2 = supersingular_js_Fp2(p)
    F = GF(p)
    S_p2_fixed = {F(j) for j in S_p2 if j in F}
    ret = (S_p == S_p2_fixed) and (len(S_p2) == len(S_p))
    print("checking",p,ret,S_p, S_p2_fixed,len(S_p2),len(S_p))
    return ret

def primes(N):

    if N < 2:
        return []
    sieve = bytearray(b"\x01") * (N + 1)
    sieve[0:2] = b"\x00\x00"

    for i in range(2, int(math.isqrt(N)) + 1):
        if sieve[i]:
            step = i
            start = i*i
            sieve[start:N+1:step] = b"\x00" * ((N - start)//step + 1)
    return [i for i in range(N+1) if sieve[i]]

def ogg_primes_up_to(N):
    return [p for p in primes(N+1) if is_ogg_prime(p)]

print("Ogg primes ≤ 100:")
print(ogg_primes_up_to(100))