PrimosReport as inadecuate




Primos - Download this document for free, or read online. Document in PDF available to download.



Source: http://www.libroteca.net/


Teaser



Teorı́a de Números a ≡ b(mod n) si a = b kn para algún entero k.
b se llama el resı́duo de a, módulo n.
a es congruente a b, módulo n.
Los enteros 0 .
n − 1 forman el conjunto completo de resı́duos módulo n.
(Nota: la función de librerı́a mod(), o el operador % en el lenguaje C, no siempre siguen la definición precisa.) Aritmética modular es conmutativa, asociativa y distributiva. Además: (a b) mod n (a − b) mod n ab mod n (a(b c)) mod n = = = = ((a mod n) (b mod n)) mod n ((a mod n) − (b mod n)) mod n ((a mod n)(b mod n)) mod n ((ab mod n) (ac mod n)) mod n Una operación criptográfica común es la exponenciación modular, ax mod n, ej.: a9 mod n = (((a2) mod n)2 mod n)2 mod n)a mod n February 1, 2000 Teorı́a de Números-1 Números Primos Un número primo es un entero mayor que 1 cuyos únicos factores son 1 y él mismo.
Hay una cantidad infinita de primos.
Los de interés para la criptografı́a son números grandes (512 bits o más). a y n son relativamente primos si no tienen factores en común sino “1”, o sea que gcd(a, n) = 1.
Calcular gcd(a, n) es fácil usando el conocido Algoritmo de Euclı́des. a y b son inversos multiplicativos si ab mod n = 1 (o ab ≡ 1(mod n)).
El inverso de a se escribe a−1.
No siempre existe. En general: si a y n no son relativamente primos, entonces a−1 ≡ x(mod n) no tiene solución.
Si lo son, puede haber más de una solución.
Para garantizar una solución única, basta que n sea primo.
En general, encontrar un inverso es más costoso que gcd, pero todavı́a es tratable. February 1, 2000 Teorı́a de Números-2 Misceláneos . • Los números n mod p, cuando p es primo o una potencia de un primo forman un cuerpo finito, tambien llamado un cuerpo de Galois, y denotado GF(p).
Estan definidos los operadores de suma, resta, multiplicación, y división por un factor distinto a 0.
Existe una identidad aditiva (0) y otra multiplicati...





Related documents