2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Алгоритмы вычисления обратного элемента в поле Zp
Сообщение25.04.2009, 20:28 
Аватара пользователя
Рассмотрим поле $\mathbb{Z}_p$. Какие существуют алгоритмы для вычисления обратного элемента к некоторому элементу $x \in \mathbb{Z}_p,\,x \ne 0$? Меня интересуют алгоритмы, которые можно легко реализовать на компьютере. Алгоритм Евклида мне кажется довольно неудобным. Но других алгоритмов я не знаю.

 
 
 
 Re: Алгоритмы вычисления обратного элемента в поле
Сообщение25.04.2009, 20:47 
AndreyXYZ писал(а):
Рассмотрим поле $\mathbb{Z}_p$. Какие существуют алгоритмы для вычисления обратного элемента к некоторому элементу $x \in \mathbb{Z}_p,\,x \ne 0$? Меня интересуют алгоритмы, которые можно легко реализовать на компьютере. Алгоритм Евклида мне кажется довольно неудобным. Но других алгоритмов я не знаю.

Возведение бинарным алгоритмом в степень $p-2$.

 
 
 
 
Сообщение26.04.2009, 06:22 
Аватара пользователя
AndreyXYZ в сообщении #208153 писал(а):
Алгоритм Евклида мне кажется довольно неудобным.

А чем он неудобен? Фактически это то же самое, что раскладываем $p/x$ в цепную дробь. Тогда числитель предпоследней подходящей дроби с точностью до знака (определяемого чётностью/нечётностью номера) и есть обратный.

Бинарный алгоритм - это как я догадываюсь несколько возведений в квадрат (исходя из двоичного кода числа p-2) с последующим перемножением?

Можно просто тупо вычислять степени $x, x^2, x^3, ... $ по модулю p. Если в этой последовательности встретится $x^k\equiv 1$ при $k<p-1$, то $x^{k-1}$ обратный. В противном случае придётся дойти до $x^{p-2}$, хотя и в этом случае можно минимизировать процесс за счёт пропуска вычислений некоторых степеней, используя делимость $p-1$ на порядок элемента $x$ - но это скорее для хьюмена, чем для компьютера.

 
 
 
 
Сообщение26.04.2009, 08:08 
bot писал(а):
Бинарный алгоритм - это как я догадываюсь несколько возведений в квадрат (исходя из двоичного кода числа p-2) с последующим перемножением?
Угу.
Цитата:
Можно просто тупо вычислять степени $x, x^2, x^3, ... $ по модулю p. Если в этой последовательности встретится $x^k\equiv 1$ при $k<p-1$, то $x^{k-1}$ обратный.

Можно, конечно. Только тогда вместо $O(\log(n ))$ получим сложность $O(n )$. А это не есть хорошо. :)
Например для поиска обратного к $5$ по модулю $1000000007$ бинарным агоритмом потребуется 45 умножений, а тупым возведением - 1000000006.

 
 
 
 
Сообщение26.04.2009, 11:48 
Код:
int mod(int a, int m){
    a %= m;
    if (a < 0) a += m;
    return a;
}
int inverse(int a, int m){
    a = mod(a, m);
    if (a == 1) return 1;
    return mod((1 - m * inverse(m % a, a)) / a, m);
}   

 
 
 
 
Сообщение26.04.2009, 20:24 
Аватара пользователя
bot в сообщении #208233 писал(а):
Можно просто тупо вычислять степени $x, x^2, x^3, ... $ по модулю p. Если в этой последовательности встретится $x^k\equiv 1$ при $k<p-1$, то $x^{k-1}$ обратный. В противном случае придётся дойти до $x^{p-2}$, хотя и в этом случае можно минимизировать процесс за счёт пропуска вычислений некоторых степеней, используя делимость $p-1$ на порядок элемента $x$ - но это скорее для хьюмена, чем для компьютера.

Обратным элементом всегда будет являться $x^{p-1}$, т.к. $\mathbb{Z}_p\backslash\{0\}$ - циклическая группа порядка $p$, где $p$ - простое.

Добавлено спустя 2 минуты 22 секунды:

Dandan писал(а):
Код:
int mod(int a, int m){
    a %= m;
    if (a < 0) a += m;
    return a;
}
int inverse(int a, int m){
    a = mod(a, m);
    if (a == 1) return 1;
    return mod((1 - m * inverse(m % a, a)) / a, m);
}   


Можете пояснить работу второй функции?

 
 
 
 
Сообщение26.04.2009, 20:24 
AndreyXYZ в сообщении #208452 писал(а):
$\mathbb{Z}_p\backslash\{0\}$ - циклическая группа порядка $p$, где $p$ - простое.


Порядка $p-1$, поэтому $x^{p-2}$.

 
 
 
 
Сообщение27.04.2009, 02:28 
AndreyXYZ писал(а):
Можете пояснить работу второй функции?

ну это по сути алгоритм Евклида

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group