A
A
Alexander Lyakh2020-10-18 15:07:53
Python
Alexander Lyakh, 2020-10-18 15:07:53

Cornacci algorithm. What is wrong here?

help me please

from modsqrt import modular_sqrt
from FermaTest import IsPrime
from FunctionSqrt import isqrt

m = byte = int(input(),2)
print(byte,"- integer while not prime")

#find melee prime integer
while not(IsPrime(m)):
    m -=1
prime_int_melee = m    
print("m =",m)

#use Tonelli-Shneks for decided x^2 % m = (m-d) % m
for d in range(2,256):#перебираем d
    m = prime_int_melee
    r = modular_sqrt(m-d, m) #use Tonelli-Shneks for decided x^2 % m = (m-d) % m
    #используем алгоритм Евклида
    if r> m/2:
        r = m-r
    while max(r,m)*max(r,m)>prime_int_melee:
        if r>=m:
            r %= m
        else:
            m %= r

    x = max(r,m)
    y = m-r*r
    if y%d == 0:
        y = isqrt(y//d)
        if y[1] == 0:
            print("d =",d,"x =",x,"y =",y[0])
    else:
        print("d =",d,"x = NOT ")#нет решений

Answer the question

In order to leave comments, you need to log in

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question