Алгоритм Корначчи для простых m:
def AlgoKornacci(integer): # m = x*x + d*y*y
m = MelleeHighPrime(integer)
for d in range(1,257):
x = modular_sqrt(m-d,m)
if x == -1 or x == 0:
continue
if not(x<=m/2):
x = m-x
r1,r0 = m,x
while True:
r1 = r1%r0
if min(r1,r0)*min(r1,r0)<m:
x = min(r1,r0)
break
r0 = r0%r1
if min(r1,r0)*min(r1,r0)<m:
x = min(r1,r0)
break
s = m-x*x
if s%d == 0:
y, remain = isqrt(s//d)
if remain == 0:
return x,y,d,integer-m
elif d == 256:
ans = AlgoKornacci(m-1)
return ans[0],ans[1],ans[2],ans[3]+integer-m
else:
continue
elif d == 256:
ans = AlgoKornacci(m-1)
return ans[0],ans[1],ans[2],ans[3]+integer-m
else:
continue
modular_sqrt() - алгоритм Тонелли-Шенкса
MelleeHighPrime(integer) - алгоритм, который находит меньшее наибольшее простое число ( так например, для числа 15 это будет число 13 )
P.S. последний аргумент, который возвращает функция это разность между входным числом и наибольшим меньшим простым числом
