Amosando publicacións coa etiqueta aritmética modular. Amosar todas as publicacións
Amosando publicacións coa etiqueta aritmética modular. Amosar todas as publicacións

martes, 22 de xullo de 2025

Acurtar o cálculo da exponenciación modular

 por Andrés Ventas

Acurtar o cálculo da exponenciación modular

O cálculo do expoñente modular é un tema moi tratado debido ao seu uso en criptografía e evidentemente o seu uso nas claves de internet.

A exponenciación modular consiste en calcular unha expresión do tipo \[ b^e \equiv r \pmod{m},\] isto é, unha base $b$ elevada a un expoñente $e$ módulo $m$ onde temos que calcular o residuo $r$ que será un enteiro entre $0$ e $m-1$.

A cuestión problemática é que para criptografía úsase un expoñente moi grande.

Os métodos máis coñecidos son: método directo, o de memoria eficiente e o máis rápido sería o de expoñente binario. Aquí imos ver un novo método "de aproximación ao módulo" que nas probas realizadas resulta sempre máis curto que o do expoñente binario (non tanto como parecía a priori).

Os tres últimos métodos usan a propiedade modular de que o módulo do produto é igual ao produto dos módulos: \[ (b\cdot b_1) \mod{m} = (b \mod{m}) \cdot (b_1 \mod{m}) \] Imos mostrar os 4 métodos co exemplo da wikipedia Modular exponentiation \[ 4^{13} \equiv r \pmod{497}\]

Non esquezamos que se a base é maior que o módulo pódese aplicar primeiro o módulo á base, por exemplo: $501^{13} \equiv c \pmod{497} \text{ implica } 4^{13} \equiv c \pmod{497}$. Isto sería común para todos os métodos.

O método directo

O método directo sería obter $b^{e}$ e calcular o seu residuo, así \[ 4^{13}=67108864 \mod 497 = 445.\] Evidentemente para expoñentes grandes (veremos algún exemplo posterior) este método ten problemas coa capacidade da memoria e produce unha división longa computacionalmente para calcular o residuo.

Método de memoria eficiente

O método de memoria eficiente vai calculando o módulo paso a paso aumentando o expoñente nunha unidade, isto é, multiplicando pola base en cada paso: \begin{equation*} \begin{aligned} 4 & \mod 497 = 4 \\ 16 & \mod 497 = 16 \\ 64 & \mod 497 = 64 \\ 256 & \mod 497 = 256 \\ 1024 & \mod 497 = 30 \\ 30\cdot 4 = 120 & \mod 497 = 120 \\ & \text{e igualmente ata o último paso} \ldots \\ 484\cdot 4 = 1936 & \mod 497 = 445 \\ \end{aligned} \end{equation*}

Isto require 13 pasos que evidentemente para un expoñente máis grande dá un número de operacións non asumíbel.

Método de expoñente binario

Nos documentos consultados é o método actualmente considerado maís rápido. O método consiste en transformar o expoñente a binario e ir calculando en función dos 0 e 1 do expoñente en binario, temos dúas variábeis $x$ e $R$, en $x$ imos gardando o valor a calcular e en $R$ o resultado que se vai reseteando cada vez que temos un bit $1$. Ímolo ver co noso exemplo: \begin{equation*} \begin{aligned} &R \leftarrow 1 \, ( = b^0) \text{ e } x \leftarrow b = 4. \\ &\text{Paso 1) o bit 1 é 1, así que se estabelece } \\ &R \leftarrow R \cdot 4 \equiv 4 \pmod{497} ; \\ & \quad\quad \text{ agora } x \leftarrow x^2 \text{ }(= b^2) \equiv 4^2 \equiv 16 \pmod{497}.\\ &\text{ Paso 2) o bit 2 é 0, polo que non recalculamos ''R'';} \\ & \quad\quad \text{ así } x \leftarrow x^2 \ (= b^4) \equiv 16^2\equiv 256 \pmod{497}. \\ &\text{ Paso 3) o bit 3 é 1, así que recalculamos ''R''} \\ &R \leftarrow R \cdot x \text{ }(= b^5) \equiv 4 \cdot 256 \equiv 30 \pmod{497} ;\\ & \quad\quad \text{ agora } x \leftarrow x^2 \ (= b^8) \equiv 256^2 \equiv 429 \pmod{497}. \\ &\text{ Paso 4) o bit 4 é 1, así que recalculamos ''R''}\\ &R \leftarrow R \cdot x \text{ }(= b^{13}) \equiv 30 \cdot 429 \equiv 445 \pmod{497}; \end{aligned} \end{equation*} Algoritmo moi interesante, pasamos de 13 pasos a 4 e como a rebaixa de pasos é logarítmica con un expoñente máis grande a efectividade é enorme.

Método de aproximación modular

Consiste en procurar a potencia $e_1$ de $b$ máis próxima ao módulo $m$ (sería válido superiormente ou inferiormente), calcular o módulo con este resultado $b^{e_1} \equiv c_1 \pmod{m}$ e calculando a división enteira dos espoñentes $\frac{e}{e_{1}} \text{ con } e= e_1 \cdot d + r$ transformamos a expresión orixinal con cifras moito menores. Para o noso exemplo: \begin{equation*} \begin{aligned} & 4^5=1024 \text{ e } 13 = 2 \cdot 5 + 3 \\ & \quad\quad 1024 \equiv 30 \pmod{497}. \quad R=30, x=30^2\cdot 4^3 \\ & \quad\quad 30^2 \equiv -94 \pmod{497}. \\ & \quad\quad -94\cdot 64 = 6016 \equiv -52 \pmod{497}. \\ & R = 497 - 52 = 445. \end{aligned} \end{equation*} Este método sen usar o algoritmo dá moitas posibilidades de reorganizalo para acurtar e isto sería un tema de estudo para estabelecer esas melloras metodicamente, imos ver o anterior módulo $7$: \begin{equation*} \begin{aligned} &4^{13} = 2^{26} \equiv c \pmod{7} \\ &2^{3} \equiv -1 \pmod{7} \text{ e } 26 = 8\cdot 3 + 2 \\ &(-1)^8 \cdot 4\equiv 4 \pmod{7}. \end{aligned} \end{equation*} E mellor aínda, aplicando directamente Fermat: Se $a$ é un enteiro e $p$ é un primo que non divide $a$, daquela $a^{p-1} \equiv 1 \pmod{p}.$ (Emanuel Lazar) notes06-3.pdf Temos: \begin{equation*} \begin{aligned} &2^{6} \equiv 1 \pmod{7} \text{ e } 26 = 6\cdot 4 + 2 \\ &(1)^4 \cdot 4\equiv 4 \pmod{7}. \end{aligned} \end{equation*} Imos comparar con algúns exemplos vistos na rede: fast modular exponentiation (Khan Academy) \begin{equation*} \begin{aligned} &7^{256} \equiv c \pmod{13} \text{ daquela } 7^{12} \equiv 1 \pmod{13} \text{ e } 256 \equiv 4 \pmod{12} \\ &7^4 \pmod{13} \equiv (-3)^2 \pmod{13} = 9 \pmod{13}. \end{aligned} \end{equation*} Por último temos o teorema de Fermat-Euler: Se $a$ e $n$ son enteiros positivos coprimos daquela $a^{\phi(n)} \equiv 1 \pmod{n}.$ Teorema de Euler (Galipedia) Onde $\phi(n)$ é a función totiente de Euler. Sen usar ese teorema, pois a función totiente non é fácil de calcular salvo para números primos, e para números grandes é difícil saber se un número é primo, imos calcular o exemplo que aparece no artigo do teorema de Euler (ou Fermat-Euler) da Galipedia: \begin{equation*} \begin{aligned} &7^{222} \equiv c \pmod{10} \text{ así temos } 7^{2} = 49 \equiv -1 \pmod{10} \text{ e } 222= 2\cdot 111 +0. \\ &(-1)^{111} \pmod{10} \equiv -1 \pmod{10} \equiv 9 \pmod{10}. \end{aligned} \end{equation*}

Bibliografia

  1. Modular exponentiation (Wikipedia)
  2. Exponenciación amodular (Galipedia)
  3. (Emanuel Lazar) notes06-3.pdf
  4. fast modular exponentiation (Khan Academy)
  5. Teorema de Euler (Galipedia)

mércores, 28 de maio de 2025

Criptografía e maxia no Losada

Algún día tería que relatar as miñas desventuras no CAP (Curso de Adaptación Pedagóxiga), un curso que xogaba aproximadamente o mesmo papel que o Máster de Profesorado actual. Só comentarei que, cando me faltaba só unha sesión para rematalo, abandoneino, farto.  Efectivamente, estaba farto de ver como quen presumiblemente tiña que dar directrices sobre orientacións didácticas actuaba como un terrorista pedagóxico. Recordo unha materia levada por dous profesores, un home gordo e unha muller fraca. Impartían clase xuntos. Pasaban todo o tempo discutindo. Iso podería estar ben se fose algo pensado e preparado. Non era o caso.  Nunha ocasión pasaran toda a sesión dándolle voltas a como tratar aos rapaces zurdos. Se conviña, ou non, forzalos a escribir coa man dereita. Non era esta un tema que houbese que tratar no CAP, só foi unha ocorrencia máis desa parella infame de profesores. Desde aquela quedoume a impresión que unha clase levada en parella tiña que ser necesariamente un fracaso. Non é así. Isto demostráronolo Nicanor Alonso e Miguel Mirás o pasado venres 16/05/2025 na charla que viñeron impartir ao IES Antón Losada Diéguez ao alumnado de 1º de Bacharelato. O segredo do éxito dunha clase en tándem? O mesmo que o dunha clase impartida por unha persoa soa: traballo e preparación. 

O título da charla era "Historias e segredos da criptografía". Trataron temas como o da escritura xeroglífica, a reixa de Cardano, os acrósticos, a escítala espartana, o cifrado César ou o máis sofisticado de Vigenére,  sempre solicitando a participación e complidade do alumnado. Nicanor e Miguel repartiron unha roda como a da imaxe, que nos permitiu encriptar unha mensaxe seguindo as directrices dos dous últimos sistemas de cifrado. 

Examinaron moitos máis tópicos e sempre dunha forma clara e coordinada. Claro que, no canto de ser explicados en parella, tal e como o fixeron eles, case todos podían ter sido tratados por un só conferenciante. Comento isto porque un dos capítulos necesitaba de dúas persoas para poder desenvolvelo. A min foi o que máis me sorprendeu e agradou. Trátase do truco das 5 cartas de Cheney, asunto do que, por certo, xa se ocupara no seu día Jota nesta entrada, O mellor truco de cartas. O enunciado promete. Vexamos como se desenvolveu.

As cinco cartas de Cheney

Un dos dous conferenciantes marchou da sala; chamémoslle  mago. O outro, chamémoslle axudante,  pediu a un voluntario que escollera cinco cartas dunha baralla francesa completa (52 cartas, 13 de cada un dos paus, a saber: corazóns ♡ , diamantes ♢, picas ♠ e trevos ♣). Entón o axudante colocou catro desas cartas sobre unha mesa e deixou a quinta ao final, virada cara abaixo.



Cando volveu o mago e veu esas cartas sobre a mesa, concentrouse un momento e adiviñou cal era a carta que estaba boca abaixo.

Estaba claro que elaboraran un código para identificar as cartas pois diso trataba a conferencia. Pero teñamos presente que non poden saber previamente cales son as cartas que se van escoller polo que o código debería estar montado sobre a ordenación das cartas. Está claro que podemos establecer unha orde entre todas elas. En primeiro lugar, os números (do 1 ao 13) axudan moito. E que pasa se dúas cartas teñen o mesmo valor numérico? Daquela basta con que o mago e o seu axudante establezan unha orde dos paus. Podería ser, por exemplo, a orde do abecedario pola primeira letra: corazóns ♡ < diamantes ♢< picas ♠ < trevos ♣. Con todo, hai un problema, as $4$ cartas que quedan visibles só poden ordenarse de $4!=24$ formas distintas. 

Para salvar esta dificultade hai que aproveitar todas as vantaxes que nos dá o desenvolvemento do truco. Teñamos presente que é o axudante quen escolle a carta que se coloca boca abaixo. Polo principio do pombal, dadas $5$ cartas, é seguro que vai haber polo menos dúas do mesmo pau. Isto permite que o axudante escolla dúas cartas do mesmo pau e coloque unha cara abaixo e a outra pode colocala na primeira posición. No noso exemplo a primeira carta era o rei de trevos, velaí que a carta a adiviñar será tamén un trevo. Agora quédannos outras tres cartas visibles que nos deben permitir identificar o número da carta oculta. Outra vez, se ordenamos esas tres cartas termos un total de só $3!=6$ posibilidades e nós necesitamos 13. Aquí é onde entra en xogo a aritmética modular. 


Facemos unha identificación do valor da carta cos números das congruencias de $\mathbb{Z}_{13}$. A diferenza entre dous destes valores nunca é maior que $6$. As cartas que escolleu o axudante eran a $J$ e o $2$ de trevos. A súa diferenza é de $4$ unidades. Ocultando o $2$ só lle ten que dicir ao seu compañeiro que debe sumarlle $4$ unidades á $J$. En aritmética modular $11+4\equiv 2 (mód 13)$. O código utilizado para indicar o número a sumar é o que explicamos de seguido. Vou identificar o $1$ co valor máis baixo das tres cartas, o $2$ co intermedio e o $3$ co maior. Daquela establezo a seguinte relación entre as $6$ ordenacións e o $6$ números que debo sumar (módulo 13) ao valor da primeira carta:

$$\begin{pmatrix} 1,2,3 & \longrightarrow 1 \\ 1,3,2 &\longrightarrow 2 \\ 2,1,3& \longrightarrow 3 \\ 2,3,1 & \longrightarrow 4 \\ 3,1,2& \longrightarrow 5 \\ 3,2,1 & \longrightarrow 6 \\ \end{pmatrix}$$
Como as tres cartas centrais son: $J$♢, $3$♠, $5$♠ vemos que a orde das cartas é: maior,  menor, intermedia que identificamos coa permutación $3,2,1$, de aí que o número a sumar é o $4$. Polo tanto o mago adiviña a carta oculta:

Principio do pombal, combinatoria e aritmética modular, todo dentro dun truco de maxia. 

Charlas científico-divulgativas
A Universidade de Vigo ofrece cada ano charlas científico-divulgativas. No seu folleto divulgativo acharemos epígrafes como os de "Ciencias da natureza", "Física e Química" ou "Economía". Aparentemente non se oferta ningunha charla de "Matemáticas". Eu aconsellaría aos centros de ensino de Secundaria buscar nese folleto os nomes de Nicanor Alonso e Miguel A. Mirás e concertar con eles unha actividade.

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 $ 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$10
1$91$01
227212
311913
4315411
514514
6331953
71124 x=67
83091254

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}$ 254911941
$t_{i}$ 1314 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