Перейти к содержанию

Академические реквесты


Рекомендуемые сообщения

1 час назад, Аюпа сказал:

При каких значениях x и p можно вычислять y=(1/x)mod p  с помощью расширенного алгоритма Евклида?

Помню, что вроде бы не всегда, и помню, что точно можно если p - простое. Но, скажем, при умножении Монтгомери и генерации ключей RSA операция выполняется с составными модулями.

Что же там за условие?

 

По-моему, p - простое, и 1 <= x < p. Вроде больше нет условий :)

 

Но я RSA уже очень давно не трогаю и этот алгоритм в частности, поэтому могу ошибаться. p может и не быть простым, но это связано с тем, что для очень больших чисел нельзя быть на 100% уверенным, что данное число является простым, если есть ограниченные временные рамки.

Ссылка на комментарий
Поделиться на другие сайты

  • Ответов 40
  • Created
  • Последний ответ

Top Posters In This Topic

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Гость
Ответить в этой теме...

×   Вставлено с форматированием.   Вставить как обычный текст

  Разрешено использовать не более 75 смайлов.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

  • Последние посетители   0 пользователей онлайн

    • Ни одного зарегистрированного пользователя не просматривает данную страницу
×
×
  • Создать...