@AlexanderLyakh
Python

Алгоритм Корначчи. В чём тут ошибка?

Помогите пожалуйста
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 ")#нет решений
  • Вопрос задан
  • 155 просмотров
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы