Алгоритмы вычисления обратного элемента в поле Zp

[AndreyXYZ]

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

[VAL]

AndreyXYZ писал(а):

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

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

[bot]

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$ - но это скорее для хьюмена, чем для компьютера.

[VAL]

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.

[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);
}   

[AndreyXYZ]

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);
}   

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

[Jnrty]

AndreyXYZ в сообщении #208452 писал(а):

$\mathbb{Z}_p\backslash\{0\}$ - циклическая группа порядка $p$, где $p$ - простое.

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

[Dandan]

AndreyXYZ писал(а):

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

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