Acurtar o cálculo do inverso multiplicativo modular

Presentamos un novo artigo de Andrés Ventas.

Inverso multiplicativo modular

Resolver o inverso multiplicativo módulo $b$ é unha tarefa común na teoría de números. Aparece a miúdo na solución de sistemas de congruencias.

A forma estándar de atopar un inverso multiplicativo módulo $b$ é usar o algoritmo de Euclides estendido. Nun artigo de 1999, Glasby compara os dous métodos máis usados actualmente para o algoritmo euclidiano estendido: recorrencia cara atrás e recorrencia cara adiante. O método aquí presentado é máis curto en ambos os casos.

O problema que temos que resolver é atopar o $x$ da ecuación $ a x \equiv{1} \pmod{b}, \ a \lt b$. Se temos $a \gt b$ o xeito máis sinxelo é substituír $a$ por $a \bmod b$. O noso algoritmo usa as propiedades das fraccións continuas mixtas, que traducido ao algoritmo de Euclides sería usar a función teito ou a función chan dependendo do menor residuo.

Necesitamos que os dous números implicados sexan coprimos, e aquí podemos ver un exempliño que se saca a ollo:

Dado que $\gcd(3, 10) = 1$, a congruencia linear $3x \equiv{1} \pmod{10} $ terá solucións, é dicir, existirán inversos multiplicativos modulares de $3$ módulo $10$. De feito, o $7$ satisfai esta congruencia (é dicir, $21 - 1 =20$). Por tanto $7$ é un inverso modular de $3$ módulo $10$.

Outros números enteiros tamén satisfán a congruencia, por exemplo $17$ e $-3$ (é dicir, $3(17) - 1 = 50$ e $3(-3) - 1 = -10$). En particular, cada número enteiro en $\overline{7}$ satisfará a congruencia xa que estes enteiros teñen a forma $7 + 10r$ para algún enteiro $r$ e

$$3(7 + 10 r) - 1 = 21 + 30 r -1 = 20 + 30 r = 10(2 + 3r), $$

é divisíbel por $10$.

Exemplo máis elaborado: Inverso multiplicativo modular

$91 x \equiv{1} \pmod{254}$ $\textbf{Mediante o algoritmo de Euclides estendido.}$

índice i	Cociente $q_{i+1}$ $\lfloor r_{i}/r_{i+1} \rfloor$	resto $r_i$	$s_i$	$t_i$
0		$254$	1	0
1		$91$	0	1
2	2	72	1	2
3	1	19	1	3
4	3	15	4	11
5	1	4	5	14
6	3	3	19	53
7	1	1	24	x=67
8	3	0	91	254

Os $s_i$ e os $t_i$ obtéñense coa mesma recorrencia que nas fraccións continuas, isto é $s_{i+1} = q_{i+1}s_{i}+s_{i-1}$ e $t_{i+1} = q_{i+1}t_{i}+t_{i-1}$, $s_i$ comezando por $(1, 0)$ e $t_i$ por $(0, 1)$. Maxicamente o inverso multiplicativo modular aparece na columna das $t_i$.

Efectivamente $x=67$ e temos $91 \cdot 67 = 6097 \equiv{1} \pmod{254}$ pois $254 \cdot 24 = 6096$.

Completamente máxico non o é, pois existen varias probas e está tamén relacionado coa identidade de Bézout.

Algoritmo mixto para obter o inverso multiplicativo modular

Sexa $a x \equiv{1} \pmod{b}, \quad a \lt b$, a congruencia para a que procuramos o inverso multiplicativo.

1. Bucle principal.

$\quad$ 1.1.Comezando con $a_0=a, \ b_0=b$, aplicamos $\Big\lceil \dfrac{b_i}{a_i} \Big\rfloor =(k_i, \pm) $ ata obtermos $b_n = k_n a_n \pm 1$. Isto quere dicir que en cada división ficamos co divisor $k_i$ que teña menor resto ao aplicar a función chan ou a función teito e no caso de ser chan anotamos ese coeficiente cun signo $\textbf{"+"}$ e se a función usada foi a teito marcamos o coeficiente cun signo $\textbf{"-"}$.

$\quad$ 1.2. Ao mesmo tempo, obtemos $a^{-1} \pmod{b}$. $x_{-1}=1, \ x_{0}=k_0; \ x_i: k_i \cdot x_{i-1} \pm x_{i-2}$.

(Note que o signo da recurrencia $i$ é o signo da operación previa $\lceil k_{i-i} \rfloor, \pm$).

2. Paso final.

Se o número das operacións de truncado (función chan, símbolo $+$) é par daquela $a^{-1} \pmod{b} =x_n$ noutro caso $a^{-1} \pmod{b} = b - x_n$.

Exemplos co algoritmo mixto

Nunha notación compacta podemos escribir tres filas. A fila superior contén os coeficientes da división enteira mixta, a segunda fila contén os residuos da operación e a terceira a recorrencia coa que obtemos a inversa multiplicativa modular. A recorrencia no algoritmo mixto pode ser sumando $t_{i+1} = q_{i+1}t_{i}+t_{i-1}$ ou restando $t_{i+1} = q_{i+1}t_{i}-t_{i-1}$ dependendo de se o coeficiente anterior se obtivo con función chan (+) ou teito (-).

$61 x \equiv{1} \pmod{2114}$.

$q_i$		$35^{-}$	$3^{-}$	$10^{+}$
$r_{i-1}$	2114	$61$	$21$	$2$	$1$
$t_{i}$	1	$35$	$104$	$1005$	$x=2114-1005=1109$

Comprobamos $x=1109$, temos $61 \cdot 1109 = 67649 \equiv{1} \pmod{2114}$ pois $32 \cdot 2114 = 67648$.

Nota: no exemplo de enriba non chegamos a utilizar a recorrencia positiva pois só temos función chan no último coeficiente que non chegamos a usar pois o signo da recorrencia vai dependendo do coeficiente anterior.

$91 x \equiv{1} \pmod{254}$. Este é o mesmo exemplo que fixemos enriba.

$q_i$		$3^{-}$	$5^{-}$	$5^{-}$
$r_{i-1}$	254	91	19	4	1
$t_{i}$	1	3	14	67	$x=67$

E efectivamente temos outra vez $91 \cdot 67 = 6097 $ e $254 \cdot 24 = 6096$, só con 3 divisións en vez de 6.

Bibliografia

1. S. P. Glasby, Extended Euclid’s algorithm via backward recurrence relations, Mathematics Magazine, 72(3)(1999), 228–230.
2. Galipedia, Algoritmo de Euclides estendido
3. Galipedia, Inverso multiplicativo modular
4. Cálculos online do inverso multiplicativo modular
5. Galipedia, Identidade de Bézout