4

Об алгоритме удалось найти только статью на Википедии, но там написано всё непонятно для кого и непонятно кем. Поскольку я не очень силён в теории вычетов и дискретном логарифмировании, прошу помочь разобраться с реализацией, можно приводить примеры на языках c#, c, c++.

Сначала разбираемся с умножением.

Выдержки из статьи:

По данным целым числам a, b < n, r, НОД(r,n)=1 алгоритм Монтгомери вычисляет

MonPro(a,b) = a * b * r^-1 mod n

Алгоритм реализует умножение чисел по модулю (a*b) mod n.

Положим r=2^k.

Определим n-остаток (n-residue) числа a < n как a' = a * r mod n

Как я понял, нам нужно подобрать такое k, чтобы r > n.

MonPro вычисляет c' = a' * b' * r^-1 mod n

Как посчитать b'?

MonPro(a,b) = a * b * r^-1 mod n

Или это и есть алгоритм?

Вопрос буду дополнять по мере разбора.

3
  • По-моему, вопрос смысла не имеет. Это как написать a*b = a+a+a...+a b раз и спрашивать, что это за числа a и b и откуда их брать? Или - откуда брать a и b при решении уравнения ax=b? Применяется это все для вычисления произведения ab по модулю n.
    – Harry
    Commented 20 апр. 2016 в 5:31
  • По-моему, я ясно ответил - умножение a на b по модулю n. Не непосредственно, а как именно - описано там же, в Википедии.
    – Harry
    Commented 20 апр. 2016 в 5:45
  • Это я уже понял, кто-то написал уже в ответе, но потом удалил. У меня другой вопрос созрел.
    – Alex
    Commented 20 апр. 2016 в 5:46

1 ответ 1

4

Вот фотка из моего учебника (переписывать, честно, лень). Все понятно вроде (почти код на Паскале). Надеюсю, Вам поможет. Обоснование, думаю, не надо? введите сюда описание изображения

2
  • Что за учебник, если не секрет?
    – zed
    Commented 23 апр. 2016 в 8:41
  • @zed наш вузовский курс лекций. Commented 23 апр. 2016 в 11:48

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.