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 ")#нет решений
