Факторизация. Правильно ли?

Решил разобраться с RSA. Есть некоторое недопонимание.
Вот допустим есть числа:
q=11, p=7
Перемножим - 77.
Применим функцию Эйлера для m, (11-1)*(7-1)=60
Найдем e взаимно простое с ним, но меньше, допустим e=19
Найдем, такое, что - d (19*79) mod 60=1.
т.е. d=79.

И вот тут вопрос первый: d может быть больше 77?
Получим:
Открытый ключ (77, 19) = 1463
Закрытый ключ (77, 79) = 6083

Факторизуем методом Ферма открытый ключ, получим:
77*19
133*11
209*7
1463*1
И вот вопрос второй. Существенно ли нам определять, каким из 4-х вариантов был получен открытый ключ? Ладно, отбросим тривиальный вариант и остальные и возьмем первый.
77*19
Нам надо найти вторую часть закрытого ключа, т.е. 79,
вроде бы логично, что для этого надо найти m=60,
Посмотрим на 77, станет понятно, что m < 77, так вроде бы следует из самого описания алгоритма. Получим 60
И вот надо вычислить d, но d может быть равно не 79, а например: 2059.
Т.е. надо все варианты перебирать? Или все же, возвращаясь к вопросу номер 1 , d не должно быть больше 77?

(Отредактировано автором: 30 Июня, 2015 - 16:30:04)

-----
Март 2021. Бросил программирование

dcc0, mod это ж остаток от целочисленного деления?

IllusionMH, ну да
т.е.

19*79mod60=1
19*2059mod60=1

(Отредактировано автором: 30 Июня, 2015 - 16:25:08)

-----
Март 2021. Бросил программирование

Интересно еще, если знать открытый ключ, можно ли определить диапазон, в котором лежит закрытый ключ?

-----
Март 2021. Бросил программирование