Arrels quadrades modulars.py

from random import randrange
from math import sqrt

def arrelsmod(x, n):
    q = n-1
    e = 0
    while (q % 2 == 0):
        q //= 2
        e += 1
    while(True):
        a = randrange(1, n)
        z = pow(a, q, n)
        if (pow(z, pow(2, e-1, n), n) != 1):
            break
    b = z
    r = e
    a = pow(x, (q-1)//2, n)
    v = a*x % n
    w = v*a % n
    while (True):
        if (w == 1):
            arrel1 = v
            arrel2 = -v
            while (arrel2 < 0):
                arrel2 += n
            return arrel1, arrel2
        k = 0
        while (k < n):
            if (pow(w, pow(2, k), n) == 1):
                break
            else:
                k += 1
        if (r-k-1 < 0):
            return -1, -1
        d = pow(b, pow(2, r-k-1), n)
        b = pow(d, 2, n)
        r = k
        v =  d*v % n
        w = w*b % n
        
N = 19
A = 5
B = 2
coords = []
for x in range(N):
    temp = (pow(x, 3, N) + A*x + B) % N
    while (temp < 0):
        temp += N
    ys = arrelsmod(temp, N)
    if (ys[0] > 0):
        punt1 = [x, ys[0]]
        punt2 = [x, ys[1]]
        if (punt1 not in coords):
            coords.append(punt1)
        if (punt1 not in coords):
            coords.append(punt2)
print(coords)
print("cardinalitat de y^2 = x^3 +",A,"x +",B," sobre Z/",N,"Z =", len(coords)+1)