Gaussian2Squares (Sage)

p = 44560482149
S = ZZ.quotient_ring(ZZ.ideal(p)) # Find a primitive root mod p
for i in range(2,10):
    a = S(i)
    b = S(a^((p-1)/2))
    if b == S(p-1):
        print(i, b, S(a^((p-1)/4)))

(2, 44560482148, 26102926097)
(3, 44560482148, 18457556052)
(8, 44560482148, 18457556052)

(2, 44560482148, 26102926097)
(3, 44560482148, 18457556052)
(8, 44560482148, 18457556052)

def reverse((m,n)):
    return n,m
reverse((2,3))

(3, 2)

(3, 2)

def Euclidean((x,y)):
    if x == 0 or y == 0:
        return x,y
    x1 = x; y1 = y;
    if x.norm() < y.norm():
        x1 = y; y1 = x;
    if (x1 - y1).norm() < x1.norm():
        return Euclidean((x1 - y1, y1))
    if (x1 + y1).norm() < x1.norm():
        return Euclidean((x1 + y1, y1))
    if (x1 - y1*I).norm() < x1.norm():
        return Euclidean((x1 - y1*I, y1))
    if (x1 + y1*I).norm() < x1.norm():
        return Euclidean((x1 + y1*I, y1))
Euclidean((CC(14 + 4*I),CC(1 - I)))

(0, 1.00000000000000 - 1.00000000000000*I)

(0, 1.00000000000000 - 1.00000000000000*I)

p = 44560482149
x = 18457556052
(y, z) = Euclidean((CC(x+I), CC(p)))
a = QQ(z.real()); b = QQ(z.imag());
print(a, b, a^2 + b^2)

(195025, -80782, 44560482149)

(195025, -80782, 44560482149)

next_prime(44560482149)

44560482151

44560482151

Gaussian2Squares

0 seconds ago by pub