Curves with strong p‐1 and n‐1 divisors - vjudeu/curves1000 GitHub Wiki

index=next_prime((2^256-2^32)//6)
p=6*index+1
while not is_prime(p) or ((p%4 != 3) and (p%8 != 5)):
    index=next_prime(index)
    p=6*index+1
is_running=True
while is_running:
    b_value=3
    n=4
    while (not is_prime(n)) and (b_value<9):
        P=GF(p)
        aP=P(0x0)
        bP=P(b_value)
        curve=EllipticCurve(P,(aP,bP))
        n=curve.order()
        if is_prime(n):
            print("success: p="+hex(p)+", b="+hex(b_value)+", n="+hex(n))
            print("index="+hex(index))
            is_running=False
        else:
            b_value+=2
    if not is_prime(n):
        print("failed: p="+hex(p)+", index="+hex(index))
        index=next_prime(index)
        p=6*index+1
        while not is_prime(p) or ((p%4 != 3) and (p%8 != 5)):
            index=next_prime(index)
            p=6*index+1

Strongest example so far:

p=0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffcce82b9b
b=0x3
n=0xffffffffffffffffffffffffffffffff4baa10269d6cad3c794b5056fcee1c37

Factors:

p-1 = 2 * 3 * 19298681539552699237261830834781317975544997444273427339909597334652045406703
n-1 = 2 * 3 * 19298681539552699237261830834781317975505046236074564924957172105089547131401

160-bit example:

p=0xfffffffffffffffffffffffffffffffffffbdf2b
P=GF(p)
aP=P(0x0)
bP=P(0x3)
curve=EllipticCurve(P,(aP,bP))
n=curve.order()
print(hex(n))
print(factor(n-1))

p=0x100000000000000000000aa2cbd03a810debcf3b3
P=GF(p)
aP=P(0x0)
bP=P(0x3)
curve=EllipticCurve(P,(aP,bP))
n=curve.order()
print(hex(n))
print(factor(n-1))

Output:

0x100000000000000000000aa2cbd03a810debcf3b3
2 * 3 * 243583606221817153033947606057310293537891253747
0xfffffffffffffffffffffffffffffffffffbdf2b
2 * 3 * 243583606221817153033947472119380503275988712071