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)

Teorema de Hall: o teorema dos matrimonios

 Na entrada anterior presentaramos o seguinte resultado

Teorema do matrimonio de Hall. Dado un grafo bipartito $G=(X,Y)$, unha condición necesaria e suficiente para que $X$ teña un emparellamento perfecto (condición de Hall) é que  $\forall A\subset X$ se verifique que $ \left| A \right|\le \left| N\left( A \right) \right|$

Segundo a Wikipedia o teorema de Hall recibe o nome de teorema do matrimonio debido a un artigo do ano 1950 no que Halmos e Vaugan se refiren ao teorema para tratar a seguinte cuestión:

"Supoñamos que un grupo de mozos [...] coñece un conxunto finito de mozas. Baixo que condicións é posible que cada un deles se case cunha das súas coñecidas?"

Desde un punto de vista da sociedade actual o enunciado do problema fica algo desfasado. Con todo, o problema pode levarnos a unha ampliación do noso punto de vista matemático. Para iso seguiremos o libro de Gilbert Strang, Introduction to applied mathematics (Wellesley-Cambidge Press 1986).

Dadas $n$ señoritas , que por seren de xénero feminino identificaremos por $f_{1}, f_{2},..., f_{n}$ e outros tantos cabaleiros $c_{1}, c_{2},..., c_{n}$ estableceremos unha matriz $A=\left( a_{ij} \right)$ onde $a_{ij}=1$ se $f_{i}$ e $c_{j}$ están dispostos a casar. No caso contrario escribiremos $a_{ij}=0$. Se for posible establecer $n$ matrimonios significa que hai un emparellamento perfecto no grafo asociado. Vexamos un exemplo no que puidemos establecer $4$ matrimonios que son os que aparecen marcados nun recadro.

Porén no seguinte caso non é posible celebrar máis que tres bodas: $\left( f_{1},c_{3} \right), \left( f_{2},c_{4} \right)$ e $\left( f_{3},c_{2} \right)$:

Esta matriz dá lugar ao seguinte grafo no que resaltamos con arestas grosas os tres matrimonios:

Se escollo as tres últimas filas $\left\{ f_{2},f_{3},f_{4} \right\}$ comprobo inmediatamente que a súa veciñanza está formada por só dúas columnas $\left\{ c_{2},c_{4} \right\}$. Isto significa que non se verifica a condición de Hall. De aí que non poidan establecerse $4$ matrimonios.

Voulle chamar liña a unha fila ou columna. Comprobarás que marcando as tres liñas rodeadas en azul teño cubertos todos os $1s$ da matriz $A'$. Isto vén a conto do seguinte teorema que é equivalente ao de Hall:

Terorema de Köning-Egerváry. Nunha matriz de $0s$ e $1s$ o máxino número de matrimonios é igual ao mínimo número de liñas que cubren todos os $1s$

Todo isto podémolo relacionar con outras cousas coñecidas. Consideremos a matriz $A$ como un taboleiro de xadrez de dimensións $n\times n$ onde cada elemento é un escaque. Propoñemos o reto de colocar o maior número posible de torres sen que se ameacen entre sí coa restrición de que só está permitido colocalas nos escaques marcados con $1$. Evidentemente o xogo é esencialmente o mesmo problema que o do matrimonio.

Imos dar algo máis de terminoloxía para ampliar a perspectiva deste resultado. Unha cobertura $K$ dun grafo é un conxunto de vértices do grafo tal que todas as arestas do grafo teñen polo menos un vértice en $K$. Sempre será interesante obter unha cobertura mínima, isto é, aquela que teña o menor número de vértices posible. A seguinte figura pode aclararnos a situación. Nela están marcados en negro os vértices que forman a cobertura.

Os emparellamentos podemos consideralos como coberturas. Ademais dado calquera emparellamento $M$ e calquera cobertura $K$, verificarase claramente que $\left| M \right|\lt \left| K \right|$. Con estes vimbios podemos reescribir o

Teorema de Köning-Egerváry. Nun grafo bipartito o número de arestas dun emparellamento máximo é igual ao número de vértices dunha cobertura mínima.

Tamén podemos afrontar o problema desde un punto de vista alxébrico. Volvendo ás matrices, do que se trata é de obter o seu rango. Se hai unha fémina á que non lle guste ningún cabaleiro teremos unha fila só con $0s$. Neste caso xa sabemos que o determinante da matriz será nulo. Como todos os valores son $1s$ e $0s$ o teorema de Hall establece que para que poidan celebrarse $n$ matrimonios, ou o que é o mesmo, que a matriz dos matrimonios sexa regular,  vai ter que verificarse calquera das tres seguintes condicións equivalentes

• Non existe unha submatriz de $0s$ de dimensión $r\times s$ con $r+s\gt n$
• A cada subconxunto de $1 \le r\le n$ mozas lles gustan polo menos $r$ mozos
• A cada subconxunto de $1 \le s\le n$ mozos lles gustan polo  menos $s$ mozas

Na seguinte entrada veremos máis aplicación do teorema de Hall.

O teorema de Hall. O caso dos trucos de maxia de Cheney

Na entrada "Criptografía e maxia no Losada", onde relataba algúns aspectos da charla que viñeron impartir á Estrada Nicanor Alonso e Miguel Mirás, expliquei o truco de maxia das 5 cartas de Cheney. Este truco xa fora tratado por Martin Gardner pois todo o interesante xa foi tratado antes por Martin Gardner. Efectivamente unha versión do truco aparece no libro  El ahorcamiento inesperado y otros entretenimientos matemáticos (Alianza Editorial, 1991). Neste caso o mérito é aínda maior porque esta versión foi presentada nun congreso de magos, isto é, diante dunha audiencia incómoda para quen realiza o truco pois esa audiencia non estaba disposta a deixarse enganar.

O (mate)mago que presentaba o xogo era Victor Eigen. Un espectador, que non era outro que Martin Gardner, ofreceu a súa propia baralla para que o mago non tivese posibilidade de marcar as cartas. O espectador escolleu 5 cartas e (isto é unha diferenza importante coa versión relatada aquí) escolleu tamén cal desas 5 cartas se debía adiviñar. O único que podía facer o mago era ordenar as outras $4$ cartas. Nesa orde leváronllas á muller de Eigen, que se hospedaba nunha habitación do hotel que albergaba o congreso. E a muller acertou a carta escollida! Como podía ser?  $4$ cartas só podemos ordenalas de $24$ formas distintas. Parecía imposible que Eigen e a súa muller poidesen elaborar un código para as 52 cartas.

A resposta é a seguinte. En primeiro lugar, como á señora Eigen lle entregaban $4$ cartas xa non tiña que buscar a carta escollida entre as $52$ da baralla. Quedábanlle $52-4=48$ pero os Eigen só podían elaborar un código para a metade deste montón, $24$. A trampa era que o matrimonio reservara dúas habitacións contiguas e Victor non desvelou o número da habitación ata que Gardner escolleu a carta que debía adiviñar a señora Eigen. Cando Gardner petou nunha das portas para entregar as $4$ cartas, a muller de Victor puido descartar $24$

O truco orixinal

Volvamos ao truco orixinal, que apareceu nun artigo do ano 1950 na revista Math Miracles e no que lle atribuían a invención a Fitch Cheney. Lembremos as condicións. O mago marcha da habitación. Un espectador escolle $5$ cartas e o axudante do mago dálle a volta a unha desas $5$ cartas e colócaa á dereita das outras $4$ que fican cara arriba. Como é o axudante quen escolle a carta a adiviñar, podemos usar este feito para dar máis información ao mago-vidente. Na experiencia que relatamos da adiviñación no IES Antón Losada o axudante escollía unha carta do mesmo pau que a oculta. Isto reduce as posibilidades nun factor $4$ pero pode facerse mellor e as $P_{4}=4!=24$ posibilidades de ordenación das cartas poden chegar a multiplicarse por un factor $5$ á hora codificar toda a información. Ademais, ao estaren á vista $4$ cartas o mago sabe que a oculta non pode ser ningunha desas. De aí que o truco das $5$ cartas permitiría realizar a adiviñación nun mazo de $5\cdot 4!+4= 5!+4=124$ cartas. Neste artigo, Using a card trick to teach discrete mathematics,  Shai Simonson e Thara S. Holm mostran como facelo. Daquela podemos considerar en xeneralizar o truco para un mazo de $m$ cartas do que extraemos $n$ e despois, de entre estas $n$ o axudante escolle unha para que sexa a carta oculta. Así o mazo podería ter $m=n\cdot (n-1)!+n-1=n!+n-1$ cartas [1]. Na seguinte táboa mostramos os primeiros valores.

$n$	$m=n!+n-1$
$1$	$1$
$2$	$3$
$3$	$8$
$4$	$27$
$5$	$124$
$6$	$725$

Claro que o valor de $m$ podería ser menor. Se podemos establecer unha codificación para os valores de $m$ dados na táboa anterior, é evidente que tamén se poderá facer se o tamaño do mazo é inferior a $m$. Por exemplo, no caso relatado cando presentamos o truco de Cheney, o mazo era normal, tiña $m=52$ cartas, cando para $n=5$, tal e como queda establecido nesta táboa, poderiamos facer o truco para un total de $m=124$ cartas. 

Coa finalidade de afacernos ao problema, estudaremos os primeiros casos.  Para $n=2$ e $m=3$ a codificación é trivial.

12	13	23
1	3	2

As cartas ocultas son as que aparecen en branco con fondo negro. Así, se o espectador escolle o par $1,2$, o axudante dálle a volta á carta $2$ e o mago ao ver cara arriba a carta $1$ xa sabe que está oculto o $2$ 

Para o seguinte valor, $n=3$, $m=8$ as cousas xa se complican bastante. O espectador terá $C_{8,3}=\binom{8}{3}=56$ formas posibles de escoller 3 cartas. Agora o axudante debe deixar dúas delas cara arriba nunha determinada orde. Hai un total de $A_{8,2}=56$ arranxos, isto é, formas de escoller $2$ cartas ordenadas no mazo de $8$. Os valores coinciden, pero será posible establecer un código para cada caso? Teñamos presente que o código está formado por dúas cartas ordenadas, pero esas dúas cartas teñen que escollerse entre as $3$ determinadas polo  espectador. Neste caso pódese facer tal e como vemos na seguinte táboa. Se o espectador colleu as cartas $123$ o axudante tapa a última e deixa as outras na orde indicada na segunda fila $1,2$. Se a orde fose $2,1$ o mago sabería que a carta oculta tería que ser un $4$.

123	124	134	135	145	146	125	156
1,2	2,1	1,3	3,1	1,4	4,1	1,5	5.1
126	136	127	137	128	138	234	235
1,6	6,1	1,7	7,1	1,8	8,1	2,3	3,2
245	246	256	257	236	267	237	247
2,4	4,2	2,5	5,2	2,6	6,2	2,7	7,2
238	248	345	346	356	357	367	368
2,8	8,2	3,4	4.3	3,5	5,3	3,6	6,3
347	378	348	358	456	457	467	468
3,7	7,3	3,8	8,3	4,5	5,4	4,6	6,4
147	478	148	458	567	568	157	578
4,7	7,4	4,8	8,4	5,6	6,5	5,7	7,5
158	258	167	678	168	268	178	278
5,8	8,5	6,7	7,6	6,8	8,6	7,8	8,7

Poderemos establecer sempre un código? Ao escoller o código $(1,2)$ para 123 estamos imposibilitando que este código nos identifique os casos 124, 125,... 128 polo que todas estas escollas deben ser codificadas con outros pares ordenados de números que poderían ser $(1,4)$, $(1,5)$,..., $(1,8)$ pero estas novas escollas permitirán establecer un código distinto para as posibilidades que faltan? Haberá algunhas asignacións que nos impidan colocar as últimas identificacións. 

O seguinte caso, o de $n=4$ e $m=27$ xa daría lugar a unha táboa codificadora de $C_{27,4}=\binom{27}{4}=A_{17,3}=17550$ elementos.

En xeral o código poderá crearse se hai unha relación biunívoca entre todas as posibles escollas do espectador que suman un total de $C_{m,n}=\binom{m}{n}$ posibilidades, e as ordenación de $n-1$ cartas que faga o axudante. Este último valor contabilízase mediante os arranxos $A_{m,n-1}=m\cdot (m-1)\cdot ... \cdot (m-n+2)$. Se igualamos estas expresións:

$$C_{m,n}=\binom{m}{n}=\frac{m!}{n!(m-n)!}=A_{m,n-1}=\frac{m!}{(m-n+1)!}$$

Igualando denominadores e operando:

$$(m-n+1)!=n!(m-n)!$$ $$\frac{(m-n+1)!}{(m-n)!}=n!$$ $$m-n+1=n!$$ $$m=n!+n-1$$

Velaí que os dous conxuntos teñen o mesmo cardinal cando a cantidade de cartas do mazo é a que determinaramos previamente en [1]. A cuestión sería entón se se poderá establecer unha codificación da información dada polo protocolo do xogo para poder levalo a cabo en todos os casos. Unha opción sería a de elaborar un algoritmo que cree unha codificación para calquera caso. Esta sería a resposta escollida por un informático. Pero hai un achegamento máis bonito, o derivado do punto de vista matemático. Non nos dá a solución, pero hai un teorema da teoría de grafos que nos permite asegurar a existencia da codificación. O teorema é o seguinte.

Teorema de Hall. Dado un grafo bipartito $G=(X,Y)$, unha condición necesaria e suficiente para que $X$ teña un emparellamento perfecto (condición de Hall) é que  $\forall A\subset X$ se verifique que $ \left| A \right|\le \left| N\left( A \right) \right|$

Cómpre aclarar notación e conceptos para entendermos o teorema. Un grafo $G$ dise bipartito se pode descompoñerse na unión disxunta de dous conxuntos de vértices $X$ e $Y$ tales que os vértices de $X$ só se conectan con vértices de $Y$ (e viceversa). $N\left( A \right)$ fai referencia á veciñanza de $A$, isto é, o conxunto de vértices que están conectados con algún elemento de $A$. As barras verticais indican o cardinal. Un emparellamento $M$ dun grafo $G$ é unha colección de arestas que non teñen ningún vértice en común. Dise que un emparellamento SMS é perfecto se todos os vértices do grafo son extremo dalgunha aresta de $M$.

Consideremos o caso xeral. Temos $m=n!+n-1$ cartas distintas, o espectador escolle $n$ e o axudante dálle a volta a unha delas e ordena as restantes. Imos ver que poderemos establecer unha relación biunívoca (ou emparellamento perfecto) entre as $C_{m,n}$ escollas e as $A_{m,n-1}$ codificacións. Para iso consideramos o grafo bipartito $G=(X,Y)$ onde os vértices de $X$ serán cada unha das posibles combinacións e os de $Y$ cada un dos posibles arranxos. As arestas conectan cada combinación de $n$ elementos de $X$ con todas as posibles ordenacións de $n-1$ elementos desa combinación. Por exemplo na codificación anteriormente estudada para $n=3$ e $m=8$, a combinación 1-2-3 estaría conectada coas permutacións de dous elementos escollidos en {1,2,3}:  (1,2), (2,1), (1,3), (3,1), (2,3) e (3,2). Son un total de $n!=3!=6$ elementos. Da mesma maneira se consideramos un arranxo calquera, como (1,2) veremos que estará conectado coas  6 combinacións 1-2-3, 1-2-4, 1-2-5, 1-2-6, 1-2-7 e  1-2-8. Todos os vértices do grafo terán o mesmo grao, $6$. No caso xeral todos os vértices terán grao $n|$. Este tipo de grafos, nos que todos os vértices teñen o mesmo grao, chámanse grafos regulares. Vexamos que este grafo verifica a condición de Hall.

Efectivamente. Supoñamos que non a verifica, isto é, que existe un subconxunto $A\subset X$ de $k$ vértices que está conectado cun subconxunto de arranxos que ten menos de $k$ vértices. Como o grao de cada elemento é $n!$ a este subconxunto de arranxos, $N\left( A \right)$, deben chegar $n!\cdot k$ arestas. Velaí que polo principio do pombal ten que haber un arranxo ao que cheguen polo menos $n!+1$ arestas, o que entra en contradición con que todos os vértices tiñan grao $n!$.

Conviña decatarse de que non só demostramos a existencia de codificación para calquera truco estilo Cheney senón que acabamos de dar a proba do seguinte resultado:

Corolario. Sexa $G=(X,Y)$ un grafo bipartito regular. Daquela $G$ ten un emparellamento perfecto.

De querermos establecer un código completo para o truco de Cheney orixinal deberiamos cubrir unha táboa con $\binom{53}{5}=2.869.685$ celas!. Xa comprobáramos que para esta viaxe non cómpren tales alforxas. Con todo, como para unha escolla de $5$ cartas por parte do espectador temos asegurada a existencia dun código incluso cando o mazo ten $124$ cartas, a cantidade de emparellamentos codificadores para este valor tan baixo ($5$) xa subiría ata un total de $\binom{124}{5}=225.150.024$. Pode parecer sorprendente, pero neste pequeno traballo de Michael Kebler establécese un atallo para evitar tremenda tarefa.

O teorema de Hall recibe tamén o nome do teorema do matrimonio.  Na seguinte entrada centrarémonos neste aspecto, na súa relación co problema dos matrimonios. O resultado foi  demostrado polo matemático inglés Philip Hall (1904-1982), gran impulsor da teoría de grupos. Foi un dos participantes en Blettchley  Park no traballo de descodificación de mensaxes durante a II Guerra Mundial. 

Explícoche matemáticas 2025

O concurso Explícoche Matemáticas do SNL da Facultade de Matemáticas da USC pon en evidencia a radicalidade ultra da prohibición do ensino das matemáticas en galego. Xa vai pola súa 13ª edición.

Na edición deste ano do Explícoche Matemáticas o vídeo gañador foi o de Antía Fernández Paulos do IES Castro Alobre (Vilagarcía de Arousa) cun traballo titulado Xogando a aproximar pi:

 

 O segundo premio foi para Adrián Arnoso Bermúdez, Manuel Díaz Sánchez, Saúl López Souto do IES Díaz Pardo (Sada) cun vídeo titulado A tartaruga Fleury