Разные реализации расширенного евклидова алгоритма дают разные результаты? - PullRequest
Новая
       21

Разные реализации расширенного евклидова алгоритма дают разные результаты?

3 голосов
/ 24 апреля 2019

Я пытаюсь реализовать алгоритм RSA. Я читал о расширенном евклидовом алгоритме и пытался внедрить код на разных сайтах. Это не дало мне правильных результатов для некоторых из моих расшифровок, поэтому я отлаживал и заметил, что разные реализации алгоритма дают разные результаты. Первый от Brilliant.org, а второй от https://www.rookieslab.com/posts/extended-euclid-algorithm-to-find-gcd-bezouts-coefficients-python-cpp-code.

def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
    gcd = b
    return gcd, x, y


def extended_euclid_gcd(a, b):
"""
Returns a list `result` of size 3 where:
Referring to the equation ax + by = gcd(a, b)
    result[0] is gcd(a, b)
    result[1] is x
    result[2] is y
"""
    s = 0; old_s = 1
    t = 1; old_t = 0
    r = b; old_r = a
    while r != 0:
        quotient = old_r/r
        old_r, r = r, old_r - quotient*r
        old_s, s = s, old_s - quotient*s
        old_t, t = t, old_t - quotient*t
    return old_r, old_s, old_t

Для a = 3, b = 25456 (следуя из чуть менее простого примера на https://www.di -mgt.com.au / rsa_alg.html ) У меня есть эти результаты для двух реализаций, соответственно: 

gcd:  1 x:  -8485 y:  1
gcd:  25456 x:  0 y:  1

Почему они разные? Почему для второй реализации gcd не равен 1? Последующий вопрос заключается в том, что, поскольку я пытаюсь следовать примеру по ссылке, я получил отрицательное значение для x. Их ответ был 16971. Я прочитал здесь https://math.stackexchange.com/questions/1001199/uniqueness-of-extended-euclidean-algorithm, что расширенный евклидов алгоритм использует ответ, ближайший к источнику. Есть ли способ указать ближайший к источнику и положительный?

1 Ответ

0 голосов
/ 02 мая 2019

Автор поста со ссылкой на Лабораторию новичка здесь.

Джеймс К Полк прав, код действительно написан на Python 2 и не совместим с Python 3.

Мы должныобновите quotient = old_r/r до quotient = old_r//r, чтобы сделать его совместимым с Python 3.

Я обновлю исходный пост, чтобы отразить этот вывод.Спасибо, Ло Ран.

...