мат.модель шифра Шамира , кое-что непонятно с тз математики

[FasterHarder]

Всем хай! Сходу к делу.

Есть пару небольших вопросов по алгоритму "шифр Шамира".

Выбирают простое число p (пишут, что побольше желательно, лол, хотя в примерах дают до 50)
Затем надо выбрать таких 2 числа (например, обозначим их a, b), чтобы они были обратными друг другу по модулю (p - 1).
То есть математически имеем:
a * b mod (p - 1) = 1

Вот тут кое-что непонятно.
Например, по условию известно, что p = 17 - это простое число, тут все ок; a = 5.
И надо рассчитать b.
То есть a * b mod (p - 1) = (5 * b) mod 16 = 1

Из теории арифметики известно, что: делимое : делитель = частное (остаток) ---> за остаток отвечает как раз таки оператор mod
Перепишем так: частное * делитель + остаток = делимое
делимое = 5*b
делитель - 16
частное - НЕИЗВЕСТНО (пусть x)
остаток = 1

Итого: 16 * x + 1 = 5 * b
В уравнении 2 неизвестных (b, x). Как бы это, того, не решить стандартным способом) Вроде как известно, что b, x = N (натуральные числа)

Перебирать остается подстановкой значения х??? Т е однозначно нельзя получить b, зная на входе p и а?
А может быть вариант, когда несколько пар значений {b, x} удовлетворяют уравнению?

p.s. возможно, я здесь оч.жестко прогнал и все гораздо проще), но, построив мат. модель получилось такое
А сам по себе алгоритм несложен, зная p, a, b, a2, b2 там уже по формулам легко можно высчитать x1, x2, x3, x4...

спс за внимание

[scrambrella]

Цитата FasterHarder @ 22.05.21, 10:57

Всем хай! Сходу к делу.

Есть пару небольших вопросов по алгоритму "шифр Шамира".

По-человечески это называется шифр RSA. Ривест-Шамир-Адлеман.
Число ваше ищется по расширенному алгоритму Евклида.

[FasterHarder]

Цитата scrambrella @ 22.05.21, 19:46

По-человечески это называется шифр RSA. Ривест-Шамир-Адлеман.

не факт!
по РСА есть описание - они чем-то похожи

возможно, что РСА усовершенствовал шифр Шамира
имхо, это НЕ одно и то же

[amk]

FasterHarder, тебе что, непонятно, как искать обратное по модулю? Если так, смотри расширенный алгоритм Эвклида - он находит не только общий делитель, но и линейную комбинацию заданных чисел, дающий этот общий делитель. Для взаимно простых чисел коэффициенты равны обратным.

gcd(a,b) = c (c получается обычным алгоритмом Эыклида)
d*a + e*b = c (c. d, e получается расширенным алгоритмом Эвклида)

если c = 1, то
d*a ≡ 1 (mod b) (d является обратным к a по модулю b)
e*b ≡ 1 (mod a) (e является обратным к b по модулю a)
если обратное при этом получается отрицательным, надо просто добавлять к нему модуль.