Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

small bug in _sqrt function #33

Open
HadarIngonyama opened this issue Apr 28, 2022 · 0 comments
Open

small bug in _sqrt function #33

HadarIngonyama opened this issue Apr 28, 2022 · 0 comments

Comments

@HadarIngonyama
Copy link

HadarIngonyama commented Apr 28, 2022

The Euler criterion is for n!=0.
I added a fix to deal with the case n==0.

def _sqrt(n, p, sign=0):
    """ Generic Tonelli–Shanks algorithm """
    if n == 0:
        return 0

    #check Euler criterion
    if pow(n,(p-1)//2,p) != 1:
        return None

    #compute square root
    p_1 = p-1
    s = 0
    q = p_1
    while q & 1 == 0:
        q = q>>1
        s  = s+1
    if s == 1:
        r = pow(n,(p+1)//4,p)
    else:
        z = 2
        while pow(z,(p-1)//2,p) == 1:
            z = z+1
        c = pow(z,q,p)
        r = pow(n,(q+1)//2,p)
        t = pow(n,q,p)
        m = s
        while True:
            if t == 1:
                break
            else:
                for i in range(1,m):
                    if pow(t,pow(2,i),p) == 1:
                        break
                b = pow(c,pow(2,m-i-1),p)
                r = (r*b)   %p
                t = (t*b*b) %p
                c = (b*b)   %p
                m = i
    if sign:
        sign = 1
    if r&1 != sign:
        r = p-r
    return r
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant