Использование евклидова алгоритма в java

Question

Если у меня есть x= 11 и y = 6 и я хочу рассчитать (w*x)mod(y) = 1. Другими словами, как я могу вычислить число, которое, если умножить на 11, а затем на модуль 6 результат 1. В этом случае w должно быть равно 5. Есть ли все-таки я могу вычислить w в методе с использованием евклидова алгоритма в java? Спасибо!

Answer 1

Существует теорема, которая утверждает, что линейная конгруэнтность a * x = b (mod n), где a, b и n являются целыми числами, имеет решение тогда и только тогда, когдаgcd(a, n) = 1.

С gcd(11,6) = 1, что просто потому, что 11 - простое число, ваше уравнение действительно разрешимо.

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

После того как вы нашли это gcd(a,n)=1, вы вычислили решение как x = b*r mod n, где r = a^-1 (mod n). Чтобы вычислить обратный номер a, который здесь мы обозначили r, вы можете использовать расширенный алгоритм Евклида (сокращенно EEA).

Если gcd(a,n)=1, то EEA, учитывая a и n, вычисляет r и s таким образом, что a*r + n*s = 1. Мы утверждаем, что r является обратным для a по модулю n. Когда у вас есть r, вы вычисляете x = b * r mod n.

Эти алгоритмы хорошо описаны в книге Введение в алгоритм от Cormen et al.