@AlexanderLyakh
Python

В чём ошибка в реализации алгоритма Корначчи?

Алгоритм Корначчи для простых 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. последний аргумент, который возвращает функция это разность между входным числом и наибольшим меньшим простым числом
  • Вопрос задан
  • 52 просмотра
Пригласить эксперта
Ваш ответ на вопрос

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

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