Если у меня есть x= 11
и y = 6
и я хочу рассчитать (w*x)mod(y) = 1
. Другими словами, как я могу вычислить число, которое, если умножить на 11, а затем на модуль 6 результат 1. В этом случае w должно быть равно 5. Есть ли все-таки я могу вычислить w в методе с использованием евклидова алгоритма в java? Спасибо!Использование евклидова алгоритма в java
ответ
Существует теорема, которая утверждает, что линейная конгруэнтность 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.
- 1. Сложность времени евклидова алгоритма
- 2. Решение расширенного евклидова алгоритма
- 3. Как написать код расширенного евклидова алгоритма в Java?
- 4. счетные шаги Программа евклидова алгоритма в python
- 5. Использование алгоритма сортировки в Java
- 6. Что именно происходит в рекурсии расширенного евклидова алгоритма в C++?
- 7. Алгоритм расширенного евклидова JAVA RSA
- 8. Почему моя реализация расширенного евклидова алгоритма выдает исключения?
- 9. Самый большой общий делитель с использованием евклидова алгоритма?
- 10. Использование алгоритма Рида-Соломона в java
- 11. Java - Рекурсивная функция алгоритма Евклида
- 12. Использование расширенного евклидова алгоритма для нахождения числа пересечений отрезка линии с точками на двумерной сетке
- 13. вычисление евклидова расстояния 2 байтовых массива java
- 14. Использование алгоритма алгоритма Latex для оператора switch?
- 15. Использование алгоритма поиска в поиске
- 16. Использование алгоритма сравнения в STL
- 17. Евклидова алгоритм/GCD в Python
- 18. Евклидова алгоритм (вычитание) в питоне
- 19. Использование алгоритма бинарного поиска
- 20. Практическое использование эволюционного алгоритма
- 21. Perl: Использование алгоритма :: Loops
- 22. Использование алгоритма FFT
- 23. Использование алгоритма сортировки C++
- 24. Расчет квадратного евклидова расстояния
- 25. евклидова расстояния с весами
- 26. Weka евклидова расстояние
- 27. Использование алгоритма поиска
- 28. Использование алгоритма круга Bresenham для генерации эллипса в Java
- 29. Slow евклидова расстояния
- 30. Реализация алгоритма LZ78 в Java
Возможный дубликат [Оператор обратного модуля] (http://stackoverflow.com/questions/10133194/reverse-modulus-operator) – TreyE