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

[Daniel5555]

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

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

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

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

 

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

 

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