Hacia la CENTRO 2010 : Hacia la CENTRO 2010 Teoría de números:
Wilson, Fermat y Euler
27 de febrero de 2010
Arturo Portnoy
Teorema de Wilson : Teorema de Wilson Si p es primo entonces (p-1)!=-1 (mod p).
Pequeño teorema de Fermat : Pequeño teorema de Fermat Si p es primo y a es entero, entonces
a^p=a (mod p).
Función de Euler : Función de Euler Sea f(n) la cantidad de números naturales menores o iguales que n que son primos relativos con n.
Teorema de Euler : Teorema de Euler Sea n un entero positivo y sea a un entero primo relativo con n. Entonces
a^(f(n))=1 (mod n).
Ejercicio : Ejercicio Encontrar el último dígito decimal de 7^222.
Ejercicio : Ejercicio Encontrar el entero positivo mas pequeño tal que 7x^25-10 es divisible entre 83.
Ejercicio : Ejercicio Calcular el residuo de la división entre 13 del número 7^44.
Ejercicio : Ejercicio Demostrar que 2^70 + 3^70 es divisible por 13.
Ejercicio : Ejercicio Si p es un número primo mayor que 5, demostrar que p^4-1 es divisible por 240.
Ejercicio : Ejercicio Demostrar que los posibles residuos de la división entre 7 de un cubo perfecto son 0, 1 ó 6.
Ejercicio : Ejercicio Calcular el residuo de la división de 2^98 entre 101.
Ejercicio : Ejercicio Si m es primo y a,b son dos números enteros positivos menores que m, demostrar que
a^(m-2)+a^(m-3)b+a^(m-4)b^2 +...+b^(m-2)
es múltiplo de m.
Encripción RSA : Encripción RSA p y q son dos primos grandes y N=pq
N puede hacerse público sin revelar p y q (factorización es difícil)
Sea T=(p-1)(q-1)=f(N) y sea e primo relativo con T y 0Encripción RSA : Encripción RSA Si alguien quiere encriptar MEjemplo : Ejemplo p=17, q=19, y el número que queremos encriptar es M=123.
Ejemplo : Ejemplo First, let's choose the primes that form the foundation of our scheme, p and q: p = 17 and q = 19
By multiplying p and q, we get our modulus, N: N = 17 × 19 = 323
Now, we find T by subtracting 1 from both p and q and multiplying: T = (p-1) × (q-1) = (16) × (18) = 288
Next, we can select the encryption key, the public key, e, so that it has no common factors with 288. Let's let e = 11.
To find the decryption key, d, we need a number that, multiplied by e, gives a product that is congruent to 1 mod 288. Expressed mathematically, we need to find a number d such that:
11 × d = 1 + n(288)
Using trial and error, we find that 131 works because 11 × 131 = 1 + 5(288).
So, our public key is N = 323 and e = 11.
The private key is d = 131.
If someone wants to send us the message "ABC" securely, using this scheme, we tell them N and e. They first convert "ABC" to "123" and then do the following arithmetic:
123e = (123)11 mod 323 = 81
The sender could then send the message, "81," over a public line of communication with confidence.
To decrypt the code, "81," we can use N and d as follows:
81d = (81)131 mod 323 = 123
The message "81" becomes "123" after decryption, which we can then easily convert to "ABC," which was the intended message.
Notice that in order to break this scheme, a hacker would have to find the two numbers that when multiplied together yield 323. The square root of 323 is a little less than 18, so they would have to try a maximum of 7 divisors before they would be guaranteed to break the modulus into the original primes that were used to find the public and private keys. Using a computer, this would not be difficult, so real RSA encryption uses numbers that are sufficiently large so that even the fastest computers would take longer than a human lifespan to factor them. It is upon this foundation, the difficulty of factoring products of two large prime numbers, that modern data encryption rests.