Presentamos un novo artigo de Andrés Ventas.
Inverso multiplicativo modular
Resolver o inverso multiplicativo módulo é 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 é 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 da ecuación . Se temos o xeito máis sinxelo é substituír por . 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 , a congruencia linear terá solucións, é dicir, existirán inversos multiplicativos modulares de módulo . De feito, o satisfai esta congruencia (é dicir, ). Por tanto é un inverso modular de módulo .
Outros números enteiros tamén satisfán a congruencia, por exemplo e (é dicir, e ). En particular, cada número enteiro en satisfará a congruencia xa que estes enteiros teñen a forma para algún enteiro e
é divisíbel por .
Exemplo máis elaborado: Inverso multiplicativo modular
índice i | Cociente
| resto | | |
0 | | | 1 | 0 |
1 | | | 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 e os obtéñense coa mesma recorrencia que nas fraccións continuas, isto é e , comezando por e por . Maxicamente o inverso multiplicativo modular aparece na columna das .
Efectivamente e temos pois .
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 congruencia para a que procuramos o inverso multiplicativo.
1. Bucle principal.
1.1.Comezando con , aplicamos ata obtermos . Isto quere dicir que en cada división ficamos co divisor 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 .
.
(Note que o signo da recurrencia é o signo da operación previa ).
2. Paso final.
Se o número das operacións de truncado (función chan, símbolo ) é par daquela noutro caso .
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 ou restando dependendo de se o coeficiente anterior se obtivo con función chan (+) ou teito (-).
.
Comprobamos , temos pois .
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.
. Este é o mesmo exemplo que fixemos enriba.
E efectivamente temos outra vez e , só con 3 divisións en vez de 6.
Ningún comentario:
Publicar un comentario