Páginas

mércores, 18 de setembro de 2024

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 ax1(modb), a<b. Se temos a>b o xeito máis sinxelo é substituír a por amodb. 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 3x1(mod10) terá solucións, é dicir, existirán inversos multiplicativos modulares de 3 módulo 10. De feito, o 7 satisfai esta congruencia (é dicir, 211=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 7 satisfará a congruencia xa que estes enteiros teñen a forma 7+10r para algún enteiro r e

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

é divisíbel por 10.

Exemplo máis elaborado: Inverso multiplicativo modular

91x1(mod254) Mediante o algoritmo de Euclides estendido.

índice

i

Cociente

qi+1

ri/ri+1

resto

ri

si ti
025410
19101
227212
311913
4315411
514514
6331953
71124 x=67
83091254

Os si e os ti obtéñense coa mesma recorrencia que nas fraccións continuas, isto é si+1=qi+1si+si1 e ti+1=qi+1ti+ti1, si comezando por (1,0) e ti por (0,1). Maxicamente o inverso multiplicativo modular aparece na columna das ti.

Efectivamente x=67 e temos 9167=60971(mod254) pois 25424=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 ax1(modb),a<b, a congruencia para a que procuramos o inverso multiplicativo.

1. Bucle principal.

1.1.Comezando con a0=a, b0=b, aplicamos biai=(ki,±) ata obtermos bn=knan±1. Isto quere dicir que en cada división ficamos co divisor ki 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 "+" e se a función usada foi a teito marcamos o coeficiente cun signo "-".

1.2. Ao mesmo tempo, obtemos a1(modb). x1=1, x0=k0; xi:kixi1±xi2.

(Note que o signo da recurrencia i é o signo da operación previa kii,±).

2. Paso final.

Se o número das operacións de truncado (función chan, símbolo +) é par daquela a1(modb)=xn noutro caso a1(modb)=bxn.

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 ti+1=qi+1ti+ti1 ou restando ti+1=qi+1titi1 dependendo de se o coeficiente anterior se obtivo con función chan (+) ou teito (-).

61x1(mod2114).

qi 35310+
ri1 2114612121
ti 135104 1005 x=21141005=1109

Comprobamos x=1109, temos 611109=676491(mod2114) pois 322114=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.

91x1(mod254). Este é o mesmo exemplo que fixemos enriba.

qi 355
ri1 254911941
ti 1314 67 x=67

E efectivamente temos outra vez 9167=6097 e 25424=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

Ningún comentario:

Publicar un comentario