¿Es el pequeño teorema de Fermat una función unidireccional?

Answer 1

El pequeño teorema de Fermat es un teorema, no una función. Un teorema en matemáticas es una afirmación probada.

El pequeño teorema de Fermat establece que para cualquier primo [matemático] p [/ matemático] y cualquier entero [matemático] a [/ matemático] obtenemos que [matemático] a ^ p \ equiv a \ mod p [/ matemático], que es equivalente decir que [math] a ^ pa [/ math] es un múltiplo de [math] p [/ math].

Una función unidireccional se define como una función que se considera difícil de invertir. En el pequeño teorema de Fermat se nos presentan dos operaciones.

La operación de módulo [math] a \ mod p [/ math] simplemente significa: encontrar el entero más grande [math] k [/ math] donde [math] a> kp [/ math] y devolver el resto [math] r = a -kp [/ matemáticas].
Observe aquí que hay un número infinito de elementos que resultarán en la misma salida, por ejemplo, let [math] p = 7 [/ math] y let [math] a \ equiv 2 \ mod p [/ math], luego [math ] a \ in 2 + 7 \ mathbb {Z} [/ math], es decir [math] a \ in \ {2, 9, 16, 23, \ cdots \}. [/ math]

Sin embargo , no ser una función inyectiva (uno a uno) no es suficiente para considerarse una función unidireccional. Pero, ¿qué sucede cuando combinamos la exponenciación con la operación de módulo? Obtenemos lo que se conoce como el problema de logaritmo discreto (DLP). El problema es el siguiente: para un primo conocido [matemático] p [/ matemático] y enteros conocidos [matemático] a, b [/ matemático] encuentre un entero [matemático] k [/ matemático] tal que [matemático] a ^ k \ equiv b \ mod p. [/ math] Este es un problema (aparentemente) muy difícil, sin una solución eficiente (es decir, tiempo polinomial) descubierta. Esta podría ser una función unidireccional.

Varios esquemas en criptología se basan en el DLP , entre estos están el intercambio de claves Diffie-Hellman, el cifrado ElGamal y el algoritmo de firma digital, ¡ todos los cuales debe buscar si está interesado en este tema!

Answer 2

Esta no es una pregunta bien definida.

El pequeño teorema de Fermat es una afirmación matemática: dice que si arreglamos un primo [matemático] p [/ matemático], para cualquier número entero [matemático] a [/ matemático] tenemos que [matemático] a ^ p \ equiv a \ ( \ text {mod} \ p) [/ math].

Una función unidireccional es una función [matemática] f [/ matemática] tal que dado [matemática] x [/ matemática], [matemática] f (x) [/ matemática] es fácil de calcular. Sin embargo, no es fácil calcular [matemáticas] x [/ matemáticas] dado [matemáticas] f (x) [/ matemáticas].

Aproximadamente, las funciones unidireccionales son funciones que son fáciles de calcular pero difíciles de invertir. Obviamente, estos son deseables en campos como la criptografía. Si [math] f [/ math] es mi función de encriptación, quiero que sea fácil encriptar mensajes pero difícil de desencriptarlos.

Desafortunadamente, la existencia de funciones unidireccionales es un problema abierto en informática. De hecho, si existieran funciones unidireccionales esto implicaría [matemática] P \ neq NP [/ matemática], respondiendo posiblemente la conjetura más grande en informática.

Answer 3

Es un teorema, no una función … Si quieres decir si tiene un inverso, entonces más o menos.

No tiene una conversación estricta en el sentido de que si podemos encontrar un tal que sea [matemática] a ^ {p} = a [/ matemática] mod [matemática] p [/ matemática] entonces p es primo.

De hecho, existe una noción general de un número charmichael que puede caracterizarse diciendo que n es charmichael si para todo b coprime to n [math] b ^ {n} = b [/ math] mod n. El ejemplo más pequeño es 561.

Sin embargo, hay un resultado ligeramente más fuerte que dice que si [math] \ existe a [/ math] tal que [math] a ^ {p-1} = 1 [/ math] mod p y [math] a ^ {\ frac {p-1} {q}} \ neq 1 [/ math] para todos los q primos dividiendo p-1, entonces p es primo. Esto, creo, se llama teorema de Lehmer y es una conversación parcial.