| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > нахождение обратного элемента |
| Автор: 31416 18.4.2007, 18:07 |
| Нужно реализовать поиск обратного элемента для простого числа по операции mod N Обратный это такой элемент Y для числа X по mod N при котором X*Y mod N =1 так вот я собственно перебором их искал начиная с 1 и проверял на выполнимость X*Y mod N =1 - но при больших числах - например 2305843009213693951 или 618970019642690137449562111 такой метод не очень прокатывает - комп начинает задуууумываться  ))Кто что может подсказать по этому поводу? как быстренько найти обратный элемент простому числу? |
| Автор: maxim1000 18.4.2007, 19:38 |
| хм... непомню, вроде где-то описывал, но не нашёл... есть такая теорема, что для любых целых q и w есть два числа a,b: a*q+b*w=НОД(q,w) идея в том, чтобы выбрать в качестве q выбрать X, а в качестве w - N тогда a*X+b*N=НОД(X,N) если НОД(X,N)=1, получаем: a*X+b*N=1 если это всять по модулю N: (a*X)mod N=1 т.е. здача нахождения обратного свелась к нахождению коэффециента a тут смысл такой - использовать идею алгоритма Евклида для нахождения НОД, но "встроить" туда вычисление нужных коэффициентов: есть у нас два числа q и w будем считать, что q<w (иначе - поменять местами) нам известно, что есть a и b: a*q+b*w=1 дальше делаем преобразование: a*q+b*(w-q+q)=1 a*q+b*(w-q)+b*q=1 (a+b)*q+b*(w-q)=1 мы получили другую задачу: q1=q w1=(w-q) a1=a+b b1=b т.е. стоит нам решить задачу для q и (w-q), и мы найдём a1,b1, по которым можно найти a,b в остальном алгоритм не отличается от исходного алгоритма Евклида: просто продолжаем, а аргументы постепенно уменьшаются, пока один из них не станет равен 1, для этого случая задача тривиальна: a*qn+b*1=1 =>a=0, b=1 |
| Автор: Artemios 21.4.2007, 17:47 | ||
И в более "программном" виде, тот же расширенный алгоритм Евклида:
|