Inverso multiplicativo modular

En matemáticas, particularmente na área da aritmética, o inverso multiplicativo modular dun número enteiro $a$ é un número enteiro $x$ tal que o produto $ax$ é congruente con 1 en relación ao módulo $m$ .^[1] Na notación estándar da aritmética modular esta congruencia escríbese como

ax\equiv 1{\pmod {m}},

que é a forma abreviada de escribir a afirmación de que $m$ divide a cantidade $ax - 1$ ou, dito doutro xeito, o resto despois de dividir $ax$ polo número enteiro $m$ é 1. Se $a$ ten un inverso módulo $m$ , entón hai un número infinito de solucións desta congruencia, que forman unha clase de congruencia con respecto a este módulo. A maiores, calquera número enteiro que sexa congruente con $a$ (é dicir, $a$ clase de congruencia de a) ten calquera elemento da clase de congruencia de $x$ como inverso multiplicativo modular. Usando a notación de ${\overline {w}}$ para indicar a clase de congruencia que contén $w$ , isto pódese expresar dicindo que o inverso multiplicativo modular da clase de congruencia ${\overline {a}}$ é a clase de congruencia ${\overline {x}}$ tal que:

{\overline {a}}\cdot _{m}{\overline {x}}={\overline {1}},

onde o símbolo $\cdot _{m}$ denota a multiplicación de clases de equivalencia módulo $m$ .^[2] Escrito deste xeito, represéntase claramente a analoxía co concepto habitual de inverso multiplicativo no conxunto de números racionais ou reais, substituíndo os números por clases de congruencia e alterando axeitadamente a operación binaria.

Do mesmo xeito que coa operación análoga sobre os números reais, un uso fundamental desta operación é resolver, cando sexa posíbel, congruencias lineares da forma

ax\equiv b{\pmod {m}}.

Aritmética modular

Para un número enteiro positivo $m$ , dous enteiros, $a$ e $b$ , dise que son congruentes módulo $m$ se $m$ divide a súa diferenza. Esta relación binaria denótase como

a\equiv b{\pmod {m}}.

^[3]

Isto é unha relación de equivalencia no conxunto de enteiros, $\mathbb {Z}$ , e as clases de equivalencia chámanse clases de congruencia módulo $m$ ou clases de residuos módulo $m$ . Denotamos ${\overline {a}}$ como a clase de congruencia que contén o número enteiro $a$ ,^[4] daquela

{\overline {a}}=\{b\in \mathbb {Z} \mid a\equiv b{\pmod {m}}\}.

Unha congruencia linear é unha congruencia modular da forma

ax\equiv b{\pmod {m}}.

A diferenza das ecuacións lineares sobre os reais, as congruencias lineares poden ter cero, unha ou varias solucións. Se $x$ é unha solución dunha congruencia linear, todo elemento en ${\overline {x}}$ tamén é unha solución, polo que cando falamos do número de solucións dunha congruencia linear estamos a referirnos ao número de clases de congruencia diferentes que conteñen solucións.

Se $d$ é o máximo común divisor de $a$ e $m$ entón a congruencia linear $ax \equiv b (mod m)$ ten solucións se e só se $d$ divide a $b$ . Se $d$ divide a $b$ , entón hai exactamente $d$ solucións.^[5]

Un inverso multiplicativo modular dun número enteiro $a$ con respecto ao módulo $m$ é unha solución da congruencia linear

ax\equiv 1{\pmod {m}}.

O resultado anterior di que unha solución existe se e só se $gcd(a, m) = 1$ , é dicir, $a$ e $m$ deben ser primos relativos (é dicir, coprimos ou primos entre si). A maiores, cando se cumpre esta condición, hai exactamente unha solución, é dicir, cando existe, un inverso multiplicativo modular é único: Se $b$ e $b'$ son ambos os dous inversos multiplicativos modulares de $a$ en relación ao módulo $m$ , daquela

ab\equiv ab'\equiv 1{\pmod {m}},

polo tanto

a(b-b')\equiv 0{\pmod {m}}.

Se $a \equiv 0 (mod m)$ , entón $gcd(a, m) = a$ , e $a$ non terá un inverso multiplicativo modular. Polo tanto, $b \equiv b' (mod m)$ .

Cando $ax \equiv 1 (mod m)$ ten unha solución, a miúdo denótase coa notación habitual de inversos, expoñente $-1$

x\equiv a^{-1}{\pmod {m}}.

Números enteiros módulo $m$

A relación de congruencia, módulo $m$ , estabelece unha partición do conxunto de enteiros en $m$ clases de congruencia. As operacións de suma e multiplicación pódense definir nestes $m$ obxectos do seguinte xeito: Para sumar ou multiplicar dúas clases de congruencia, primeiro escolla un representante de cada clase e despois realice a operación habitual para os enteiros dos dous representantes. Finalmente, tome a clase de congruencia na que se atopa o resultado da operación enteira como resultado da operación sobre as clases de congruencia. En símbolos, con $+_{m}$ e $\cdot _{m}$ representando as operacións sobre clases de congruencia, estas definicións son

{\overline {a}}+_{m}{\overline {b}}={\overline {a+b}}

e

{\overline {a}}\cdot _{m}{\overline {b}}={\overline {ab}}.

Estas operacións están ben definidas, o que significa que o resultado final non depende das eleccións dos representantes que se fixeron para obter o resultado.

As $m$ clases de congruencia con estas dúas operacións definidas forman un anel, chamado anel de enteiros módulo $m$ . Hai varias notacións utilizadas para estes obxectos alxébricos, a maioría das veces $\mathbb {Z} /m\mathbb {Z}$ ou $\mathbb {Z} /m$ (conxunto cociente), mais tamén $\mathbb {Z} _{m}$ cando é improbábel a confusión con outros obxectos alxébricos.

As clases de congruencia dos enteiros módulo $m$ coñecíanse tradicionalmente como clases de residuos módulo m, o que reflicte o feito de que todos os elementos dunha clase de congruencia teñen o mesmo resto (é dicir, "residuo") ao seren divididos por $m$ . O algoritmo de división para números enteiros mostra que o conxunto de números enteiros, ${0, 1, 2, ..., m - 1$ } forma un sistema completo de residuos módulo $m$ , coñecido como o sistema de mínimos residuos módulo $m$ .^[6]

Grupo multiplicativo de enteiros módulo $m$

Non todos os elementos dun sistema de residuos completo módulo $m$ teñen un inverso multiplicativo modular, por exemplo, cero nunca o ten. Despois de eliminar os elementos dun sistema de residuos completo que non son coprimos con $m$ , o que fica denomínase sistema reducido de residuos, cuxos elementos teñen todos un inverso multiplicativo modular. O número de elementos nun sistema reducido de residuos é $\phi (m)$ , onde $\phi$ é a función totiente de Euler, é dicir, o número de enteiros positivos inferiores a $m$ que son coprimos con $m$ .

Nun anel xeral con unidade non todos os elementos teñen un inverso multiplicativo e os que o teñen denomínanse unidades. Como o produto de dúas unidades é unha unidade, as unidades dun anel forman un grupo, o grupo de unidades do anel e moitas veces denótase como $R \times$ se $R$ é o nome do anel. O grupo de unidades do anel de enteiros módulo $m$ chámase grupo multiplicativo de enteiros módulo $m$ , e é isomorfo a un sistema de residuos reducido. En particular, ten orde (tamaño), $\phi (m)$ .

No caso de que $m$ sexa primo, digamos $p$ , daquela $\phi (p)=p-1$ e todos os elementos distintos de cero de $\mathbb {Z} /p\mathbb {Z}$ teñen inversos multiplicativos, polo tanto $\mathbb {Z} /p\mathbb {Z}$ é un corpo finito. Neste caso, o grupo multiplicativo de enteiros módulo $p$ forma un grupo cíclico de orde $p - 1$ .

Exemplos

Para todo número enteiro $n>1$ , sempre acontece que $n^{2}-n+1$ é o inverso multiplicativo modular de $n+1$ módulo $n^{2}$ , xa que $(n+1)(n^{2}-n+1)=n^{3}+1$ . Os exemplos son $3\times 3\equiv 1{\pmod {4}}$ , $4\times 7\equiv 1{\pmod {9}}$ , $5\times 13\equiv 1{\pmod {16}}$ , etc.

Dous números enteiros son congruentes mod 10 se e só se a súa diferenza é divisíbel por 10, por exemplo

32\equiv 2{\pmod {10}}

xa que 10 divide 32 − 2 = 30, e

111\equiv 1{\pmod {10}}

xa que 10 divide 111 − 1 = 110.

A congruencia linear $4 x \equiv 5 (mod 10)$ non ten solucións xa que os enteiros que son congruentes con 5 (é dicir, os de ${\overline {5}}$ ) son todos impares mentres que $4 x$ sempre é par. No entanto, a congruencia linear $4 x \equiv 6 (mod 10)$ ten dúas solucións, a saber, $x = 4$ e $x = 9$ . O $gcd(4, 10) = 2$ e temos que 2 non divide 5, mais si divide 6.

Dado que $gcd(3, 10) = 1$ , a congruencia linear $3 x \equiv 1 (mod 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 multiplicativo 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 + 10 r

para algún enteiro

r

e

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

é divisíbel por 10.

O produto das clases de congruencia ${\overline {5}}$ e ${\overline {8}}$ pódese obter seleccionando un elemento de ${\overline {5}}$ , digamos 25, e un elemento de ${\overline {8}}$ , digamos −2, e observando que o seu produto (25)(−2) = −50 está na clase de congruencia ${\overline {0}}$ . Así, ${\overline {5}}\cdot _{10}{\overline {8}}={\overline {0}}$ . A suma defínese dun xeito similar. As dez clases de congruencia xunto con estas operacións de suma e multiplicación de clases de congruencia forman o anel de enteiros módulo 10, é dicir, $\mathbb {Z} /10\mathbb {Z}$ .

Cálculo

Algoritmo de Euclides estendido

Pódese atopar un inverso multiplicativo modular $a$ módulo $m$ usando o algoritmo de Euclides estendido.

O algoritmo de Euclides determina números enteiros $x$ e $y$ que satisfán a identidade de Bézout,

ax+my=\gcd(a,m)=1.

Reescrito, isto é

ax-1=(-y)m,

é dicir,

ax\equiv 1{\pmod {m}},

e polo tanto temos o inverso multiplicativo modular de $a$ . Unha versión máis eficiente do algoritmo é o algoritmo de Euclides estendido.

En notación O grande, este algoritmo corre en tempo $O(log 2 (m))$ , asumindo $| a | < m$ , e considérase moi rápido e xeralmente máis eficiente que a súa alternativa, a exponenciación.

Usando o teorema de Euler

Como alternativa ao algoritmo de Euclides estendido, o teorema de Euler pódese usar para calcular inversos modulares.^[7]

Segundo o teorema de Euler, se $a$ é coprimo con $m$ , é dicir, $gcd(a, m) = 1$ , daquela

a^{\phi (m)}\equiv 1{\pmod {m}},

onde $\phi$ é a función total de Euler. Isto débese ao feito de que $a$ pertence ao grupo multiplicativo $(\mathbb {Z} /m\mathbb {Z} )$ ^× se e só se $a$ é coprimo con $m$ . Polo tanto, pódese atopar directamente un inverso multiplicativo modular mediante:

a^{\phi (m)-1}\equiv a^{-1}{\pmod {m}}.

No caso especial onde $m$ é primo, $\phi (m)=m-1$ e o inverso modular vén dada por

a^{-1}\equiv a^{m-2}{\pmod {m}}.

Este método é xeralmente máis lento que o algoritmo de Euclides estendido.

Múltiples inversos

É posíbel calcular a inversa de múltiples números $a i$ , módulo un $m$ común, cunha única invocación do algoritmo de Euclides e tres multiplicacións por entrada adicional.^[8]A idea básica é formar o produto de todos os $a i$ , calcular a inversa e, a continuación, multiplica por $a j$ para todo $j \neq i$ e así conseguir o desexado $a -1 i$ .

En pseudocódigo, o algoritmo é (toda a aritmética realizada módulo $m$ ):

Calcular os produtos prefixo ${\textstyle b_{i}=\prod _{j=1}^{i}a_{j}=a_{i}b_{i-1}}$ para todo $i \leq n$ .
Calcula $b -1 n$ usando calquera algoritmo coñecido.
Para i desde n ata 2, calcuar
- $a -1 i = b -1 i b i -1$ .
- $b -1 i -1 = b -1 i a i$ .
Finalmente, $a -1 1 = b -1 1$ .

É posíbel realizar as multiplicacións nunha estrutura en árbore en lugar de utilizar de forma linear a computación paralela.

Aplicacións

No algoritmo RSA, o cifrado e descifrado dunha mensaxe realízase mediante un par de números que son inversos multiplicativos con respecto a un módulo coidadosamente seleccionado. Un destes números faise público e pódese utilizar nun procedemento de cifrado rápido, mentres que o outro, usado no procedemento de descifrado, manténse oculto. Determinar o número oculto a partir do número público considérase computacionalmente inviábel e isto é o que fai que o sistema funcione para garantir a privacidade.^[9]

Os inversos multiplicativos modulares utilízanse para obter unha solución dun sistema de congruencias lineares que está garantido polo teorema chinés do resto.

Por exemplo, o sistema

X

≡ 4 (mod 5)

X

≡ 4 (mod 7)

X

≡ 6 (mod 11)

ten solucións comúns xa que 5,7 e 11 son coprimos por parellas. Unha solución vén dada por

X

=

t 1

(7 × 11) × 4 +

t 2

(5 × 11) × 4 +

t 3

(5 × 7) × 6

onde

t 1

= 3 é o inverso multiplicativo modular de 7 × 11 (mod 5),

t 2

= 6 é o inverso multiplicativo modular de 5 × 11 (mod 7),

t 3

= 6 é o inverso multiplicativo modular de 5 × 7 (mod 11).

Por tanto,

X

= 3 × (7 × 11) × 4 + 6 × (5 × 11) × 4 + 6 × (5 × 7) × 6 = 3504

e na súa forma reducida

X

≡ 3504 ≡ 39 (mod 385)

xa que 385 é o mcm de 5,7 e 11.

Outro uso do inverso multiplicativo modular ocupa un lugar destacado na definición da suma de Kloosterman.

Notas

↑ Rosen 1993.
↑ Schumacher 1996, p. 88.
↑ Terence Tao usa habitualmente a notación sen a palabra "mod", $a\equiv b\ (m).$
↑ Úsanse moitas veces outras notacións, incluíndo $[a]$ e $[a] m$ .
↑ Ireland & Rosen 1990
↑ Ireland & Rosen 1990
↑ Thomas Koshy. Elementary number theory with applications, 2nd edition. ISBN 978-0-12-372487-8. P. 346.
↑ Brent, Richard P.; Zimmermann, Paul (December 2010). "§2.5.1 Several inversions at once" (PDF). Modern Computer Arithmetic. Cambridge Monographs on Computational and Applied Mathematics 18. Cambridge University Press. pp. 67–68. ISBN 978-0-521-19469-3.
↑ Trappe & Washington 2006

Véxase tamén

Bibliografía

Ireland, Kenneth; Rosen, Michael (1990). A Classical Introduction to Modern Number Theory (2nd ed.). Springer-Verlag. ISBN 0-387-97329-X.
Rosen, Kenneth H. (1993). Elementary Number Theory and its Applications (3rd ed.). Addison-Wesley. ISBN 978-0-201-57889-8.
Schumacher, Carol (1996). Chapter Zero: Fundamental Notions of Abstract Mathematics. Addison-Wesley. ISBN 0-201-82653-4.
Trappe, Wade; Washington, Lawrence C. (2006). Introduction to Cryptography with Coding Theory (2nd ed.). Prentice-Hall. ISBN 978-0-13-186239-5.

Outros artigos

Ligazóns externas

[Rosen132-1] Rosen 1993.

[:1-2] Schumacher 1996, p. 88.

[3] Terence Tao usa habitualmente a notación sen a palabra "mod", $a\equiv b\ (m).$

[4] Úsanse moitas veces outras notacións, incluíndo $[a]$ e $[a] m$ .

[5] Ireland & Rosen 1990

[6] Ireland & Rosen 1990

[7] Thomas Koshy. Elementary number theory with applications, 2nd edition. ISBN 978-0-12-372487-8. P. 346.

[8] Brent, Richard P.; Zimmermann, Paul (December 2010). "§2.5.1 Several inversions at once" (PDF). Modern Computer Arithmetic. Cambridge Monographs on Computational and Applied Mathematics 18. Cambridge University Press. pp. 67–68. ISBN 978-0-521-19469-3.

[9] Trappe & Washington 2006

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]