1.

ALGORITMO PARA ENCONTRAR EL MCD ENTRE 2 NMEROS

DEFINICION: DOS NUMEROS ENTEROS a Y b SON PRIMOS RELATIVOS ENTRE SI CUANDO NO TIENEN FACTORES PRIMOS COMUNES DEFINICION: MAXIMO COMUN DIVISOR DE DOS NUMEROS ENTEROS a Y b ES EL MAYOR NUMERO ENTERO QUE PUEDE DIVIDIR SIN RESIDUOS A a Y b. POR LO TANTO, DOS NUMEROS ENTEROS a Y b SON PRIMOS RELATIVOS ENTRE SI CUANDO: mcd (a, b) = 1 TEOREMA: TODO DIVISOR DE (a, b), INCLUYENDO EL MAXIMO, ES TAMBIEN DIVISOR DE r1, (r1, r2), . . . (rk 1, rk) mcd (b, r1) = mcd (ri, r i + 1) = rk PRUEBA: SEA c/a c DIVIDE A a, ES DECIR, a c EN FORMA ENTERA SI c/a Y c/b ENTONCES a = p1c Y b = p2c ES DECIR QUE: c/ r1

r1 = a bq1 = c (p1 q1p2) AHORA BIEN: c/ r1 y c/b

r1 = p i c Y b = p j c c/a
1

ENTONCES: a = r1 + bq1 ES DECIR QUE: a = (p i + p jq1)c Y ASI SUCESIVAMENTE

1. ALGORITMO PARA ENCONTRAR EL MCD ENTRE 2 NMEROS

ALGORITMO: CON BASE EN EL ANTERIOR TEOREMA SE PUEDE DESARROLLAR UN ALGORITMO PARA ENCONTRAR EL mcd DE DOS NUMEROS ENTEROS a Y b.

INICIO V TEMP a b a b TEMP I = 0 M = I + 1 I = I + 1 Q(M) = a / b R(M) = a - Q(M) x b a b b R(M) R = 0 MCD = b PARE 2 F

a< b

1. ALGORITMO PARA ENCONTRAR EL MCD ENTRE 2 NMEROS Ejercicio 1: Utilizando el algoritmo anterior encuentre el MCD de 296 y 814 (muestre cada una de las iteraciones del algoritmo) Ejercicio 2: Implemente el algoritmo anterior utilizando el lenguaje y herramienta de su preferencia

2. INVERSO DE UN NUMERO EN ARITMETICA MODULAR

DEFINICION: DEL INVERSO DE UN NUMERO EN ARITMETICA MODULAR SEAN A Y M DOS NUMEROS ENTEROS POSITIVOS (A, M) N, TAL QUE mcd(A, M) = 1, LO QUE SIGNIFICA QUE A Y M NO TIENEN FACTORES COMUNES, ES DECIR, SON PRIMOS RELATIVOS. SE DESEA ENCONTRAR UN NUMERO B N, TAL QUE: (B x A) mod M = 1. SI EXISTE ESTE NUMERO B SE DEFINE COMO B = A- 1 mod M PROCEDIMIENTO: SI A Y M SON NUMEROS PRIMOS RELATIVOS, ENTONCES mcd (A, M) = 1 Y

rn = 1 rn + 1 = 0 rn - 1 = rn qn + 1 + rn + 1 rn - 2 = rn - 1 q n + rn 1 = rn - 2 - r n - 1 q n
EN GENERAL, UNA ITERACION ESTA DADA POR:

1 =

rk - 1 +

rk
4

2. INVERSO DE UN NUMERO EN ARITMETICA MODULAR

r k = (1 r k 1)/ r k 2 = r k 1 q k + r k r k 2 = r k 1 q k + (1 r k 1)/ r k 1 ( q k ) + r k 2 = 1
ES DECIR, UNA COMBINACION LINEAL EN UNA DETERMINADA ITERACION IMPLICA QUE EN LA ITERACION ANTERIOR TAMBIEN PUEDE FORMARSE UNA COMBINACION LINEAL. EN PARTICULAR, UNA COMBINACION LINEAL SE PUEDE CONFORMAR DE LA SIGUIENTE FORMA:

1 = S1 A S2 M
OBSERVESE QUE SI SE CUMPLE QUE: S1 > 0, ENTONCES S = A 1 DADO QUE (BA) mod M = 1 BA = qM + 1 LO CUAL SUPONE QUE: 1 = BA qM, QUE ES SIMILAR A 1 = S1 A S2 M. 0 NOTESE QUE: ((M + A POR LO TANTO:

)A) mod M = (MA) mod M + (A M + S1 = M + A 1 = A 1

1

A) mod M = 0 + 1
5

2. INVERSO DE UN NUMERO EN ARITMETICA MODULAR

DEFINICION: ALGORITMO PARA EL CALCULO DEL INVERSO DE UN NUMERO EN ARIMETICA MODULAR

INICIE

i = N G = - Q(i) P = 1 Ti = G T = P G T - Q(i - 1) Ti P Ti i = i - 1 F V

A- 1 = M + G V G< 0 F
PARE

i = 1

A- 1 = G 6

2. INVERSO DE UN NUMERO EN ARITMETICA MODULAR

EJEMPLO DE APLICACIN DEL CALCULO DEL INVERSO DE UN NUMERO EN ARITMETICA MODULAR 1. SEAN M = 73; A = 16, COMO SE PUEDE VER mcd(73, 16) = 1. 2. SE INICIA CON LA APLICACIN DEL ALGORITMO DE EUCLIDES 73 (M) = 16 (B) = 9(R(1)) = 7(R(2)) = 2(R(3)) = 16 (B) * 4(Q(1)) + 9 (R(1)) 9(R(1)) * 1(Q(2)) + 7 (R(2)) 7(R(2)) * 1(Q(3)) + 2(R(3)) 2(R(3)) * 3(Q(4)) + 1(R(4)) 1(R(4)) * 2(Q(5)) + 0(R(5))

OBSERVESE QUE EN ESTE CASO N = 4 4 Q = 1 1 3 9 7 2 1

7

R =

2. INVERSO DE UN NUMERO EN ARITMETICA MODULAR

3. SE UTILIZA EL ALGORITMO PARA EL CALCULO DEL INVERSO DE UN NUMERO EN ARITMETICA MODULAR. i = 4 G = - Q(4) = - 3 P = 1 T4 <- G = -3 T <- P = 1 i = 3
G = T Q(3)T4 = 1 - 1* (- 3) = 4

i = i1=31=2 i = 1 ? RESP: NO T2 <- G = - 7 T <- P = 4 G <- T Q(1) T2 = 4 4*(- 7) = 32

i=i1=21=1 i = 1 ? RESP: SI

P <- T4 = - 3 i=i1=41=3 i = 1 ? RESP: NO T3 <- G = 4 T <- P = - 3 G <- T Q(2) T3 = - 3 -1*4 = - 7 P <- T3 = 4

G < 0 ? RESP: FALSO POR LO TANTO A-1 = G = 32

A- 1 = 32
8

COMPROBACION: (32 * 16) mod 73 = (512) mod 73 = (7 * 73 + 1) mod 73 = 1

2. INVERSO DE UN NUMERO EN ARITMETICA MODULAR

Ejercicio 3: Implemente el algoritmo anterior utilizando el lenguaje y herramienta de su preferencia

3. METODOS PARA DETERMINAR LA PRIMALIDAD DE UN NUMERO

METODO DEL CRIBADO DEL GRIEGO ERATOSTENES ESCRIBIR TODOS LOS NUMEROS ENTEROS DESDE 2 HASTA k. ENCERRAR EN CIRCULO EL NUMERO 2 Y ELIMINAR TODOS SUS MULTIPLOS. ENCERRAR EN CIRCULO EL NUMERO 3 Y ELIMINAR TODOS SUS MULTIPLOS. ENCERRAR EN CIRCULO EL NUMERO 5 Y ELIMINAR TODOS SUS MULTIPLOS. CONTINUAR HASTA QUE NO SE PUEDAN ELIMINAR MAS NUMEROS. AL FINAL SOLO QUEDAN LOS NUMEROS PRIMOS. EL METODO ES APROPIADO PARA NUMEROS DE CIERTA LONGITUD, PERO CUANDO EL NUMERO a DEL CUAL SE QUIERE DETERMINAR SU PRIMALIDAD CUENTA CON UNA LONGITUD DE 20 O MAS CIFRAS EL METODO ANTERIOR NO ES EL MAS APROPIADO METODO DE SOLOVAY STRASSEN ES UN METODO PROBABILISTICO PARA DETERMINAR LA PRIMALIDAD DE UN NUMERO a DE LONGITUD MUY GRANDE, CON CIERTA PROBABILIDAD. EL METODO ES FUNDAMENTALMENTE UTILIZADO CUANDO EL METODO DE ERATOSTENES RESULTA INEFICIENTE (NUMEROS CON UNA GRAN CANTIDAD DE DIGITOS).

10

3. METODOS PARA DETERMINAR LA PRIMALIDAD DE UN NUMERO

DEFINICION: RESIDUOS CUADRATICOS. SI p ES UN NUMERO PRIMO Y a ES CUALQUIER ENTERO MENOR QUE p, ENTONCES a ES UN RESIDUO CUADRATICO EN mod p SI: X2 = a (mod p) PARA ALGUN x NO TODOS LOS VALORES DE a SATISFACEN ESTA PROPIEDAD EJEMPLO: SE p = 7 UN NUMERO PRIMO, ENTOCES SUS RESIDUOS CUADRATICOS SON 1, 2 Y 4: 12 = 1 = 1 (mod 7) 22 = 4 = 4 (mod 7) 32 = 9 = 2 (mod 7) 42 = 16 = 2 (mod 7) 52 = 25 = 4 (mod 7) 62 = 36 = 1 (mod 7) NOTESE QUE CADA RESIDUO CUADRATICO APARECE DOS VECES EN LA LISTA. NO EXISTEN VALORES PARA x QUE SATISFAGAN ESTAS ECUACIONES: x2 = 3 (mod 7) x2 = 5 (mod 7) x2 = 6 (mod 7) LOS RESIDUOS NO CUADRATICOS PARA p = 7 SON 3, 5 Y 6. 11

3. METODOS PARA DETERMINAR LA PRIMALIDAD DE UN NUMERO

EXISTEN EXACTAMENTE (p - 1)/2 RESIDUOS CUADRATICOS EN mod p. EXISTEN EXACTAMENTE (p - 1)/2 RESIDUOS NO CUADRATICOS EN mod p. SI a ES UN RESIDUO CUADRATICO EN mod p, ENTONCES a TIENE EXACTAMENTE DOS RAICES CUADRADAS: UNA DE ELLAS ENTRE 0 Y (p 1)/2 Y LA OTRA ENTRE (p - 1)/2 Y (p - 1). SI n ES EL PRODUCTO DE DOS NUMEROS PRIMOS, p Y q, ENTONCES EXISTEN EXACTAMENTE (p - 1)(q - 1)/4 RESIDUOS CUADRATICOS EN mod n. DEFINICION: EL SIMBOLO DE LEGENDRE, DENOTADO POR L(a, p), SE DEFINE CUANDO a ES CUALQUIER ENTERO Y p ES UN NUMERO PRIMO MAYOR A 2. L(a, p) ES IGUAL A 0, 1 -1. L(a, p) = 0 SI p DIVIDE A a. L(a, p) = 1 SI a ES UN RESIDUO CUADRATICO EN mod p. L(a, p) = - 1 SI a NO ES RESIDUO CUADRATICO EN mod p. UNA FORMA SENCILLA DE CALCULAR L(a, p) ES: L(a, p) = a(p - 1)/2 mod p
12

3. METODOS PARA DETERMINAR LA PRIMALIDAD DE UN NUMERO

DEFINICION: EL SIMBOLO DE JACOBI, DENOTADO POR J(a, n), ES UNA GENERALIZACION DEL SIMBOLO DE LEGENDRE Y SE DEFINE PARA CUALQUIER PAREJA DE ENTEROS a Y n. LA FUNCION DE JACOBI SE UTILIZA PRINCIPALMENTE EN PRUEBAS PARA DETERMINACION DE SI UN NUMERO ES PRIMO O NO CARACTERISTICAS: SI n ES PRIMO, ENTONCES J(a, n) = 1 SI a ES UN RESIDUO CUADRATICO EN mod n. SI n ES PRIMO, ENTONCES J(a,n) = - 1 SI a ES UN NO RESIDUO CUADRATICO EN mod n. SI n ES UN NUMERO COMPUESTO, ENTONCES J(a, n) = J(h, p1) x . . . . J(h, pm), DONDE p1 . . . pm SON LOS FACTORES PRIMOS DE n. ALGORITMO DE CALCULO DEL SIMBOLO DE JACOBI EN FORMA RECURSIVA. 1. J(1, k) = 1 2. J(a x b, k) = J(a; k) x J(b, k) 3. J(2, k) = 1 SI (k2 - 1)/8 PAR = -1 SI (k2 - 1)/8 IMPAR 4. 5. J(b, a ) = J((b mod a), a) SI mcd (a, b) = 1 5.1 J(a; b) x J(b, a) = 1 SI (a - 1)(b - 1)/4 PAR 5.2 J(a; b) x J(b, a) = - 1 SI (a - 1)(b - 1)/4 IMPAR
13

3. METODOS PARA DETERMINAR LA PRIMALIDAD DE UN NUMERO

METODO DE SOLOVAY - STRASSEN PARA DETERMINAR LA PRIMALIDAD DE UN NUMERO. SI a PERTENECE A {1, 2, 3, . . .b - 2, b - 1} SE DEBEN PROBAR LAS SIGUIENTES CONDICIONES: MCD (a, b) = 1. J(a, b) = L(a, b) = a(b - 1)/2 MOD b SI b ES UN NUMERO PRIMO LA SEGUNDA CONDICION SIEMPRE ES CIERTA. SI b ES UN NUMERO COMPUESTO (ES EL PRODUCTO DE FACTORES PRIMOS), LA SEGUNDA CONDICION SE CUMPLE CON PROBABILIDAD DE 1/2. POR TANTO, DESPUES DE CULMINAR CON XITO LA PRUEBA PARA 100 DIFERENTES VALORES DE a, LA PROBABILIDAD DE QUE EL NUMERO SEA COMPUESTO ES DE 2- 100 QUE PARA EFECTOS PRACTICOS ES 0. PARA FACILITAR EL CALCULO DEL SIMBOLO DE JACOBI SE HA DESARROLLADO UN ALGORITMO RECURSIVO QUE ES EL QUE SE PRESENTA A CONTINUACION.
14

3. METODOS PARA DETERMINAR LA PRIMALIDAD DE UN NUMERO

METODO DE SOLOVAY - STRASSEN PARA DETERMINAR LA PRIMALIDAD DE UN NUMERO.

INICIO

a = 1?

J(a, b) = 1

a ES PAR ?

J(a, b) = J(a/2, b) x (-1) ( b^2 - 1)/8

J(a, b) = J(b(mod a), a) x (-1) ( (a-1)(b-1))/4 15

3. METODOS PARA DETERMINAR LA PRIMALIDAD DE UN NUMERO

LA UTILIDAD DEL ALGORITMO RESIDE EN LOS SIGUIENTES ASPECTOS: CUANDO mcd (a, b) = 1 ; a < b Y J(a, b) = - 1 ENTONCES EL NUMERO NO ES PRIMO. CUANDO mcd (a, b) = 1 ; a < b Y J(a, b) = 1 ENTONCES EL NUMERO ES COMPUESTO CON UNA PROBABILIDAD DE 1/2. EJEMPLO: PRUEBE SI EL NUMERO 3781 ES PRIMO. SE ELIGEN DIFERENTES VALORES PARA a COMPRENDIDOS EN EL RANGO (1, 2, . . . 3780), V. G. a1 = 422, a2 = 123, a3 = 3560, a4 = 552. MCD (3781, 422) = 1 J(422, 3781) = - J(211, 3781) - { J(211, 3781)} = - {J(194, 211)} - { J(194, 211)} = - {J(97, 211)} (-1) = J(97, 211) J(97, 211) = J(17, 97) = J(12, 17) = J(6, 17) (6, 17) = J(3, 17) = J(2, 3) = { J(1, 3)} (- 1) (- 1){ J(1, 3)} = = - 1 POR LO TANTO, EL NUMERO 3781 CON ABSOLUTA SEGURIDAD NO ES PRIMO, EN EFECTO: 3781 = 19 X 199
16

3. METODOS PARA DETERMINAR LA PRIMALIDAD DE UN NUMERO

EJEMPLO: PRUEBE SI EL NUMERO 181 ES PRIMO. SE ELIGEN DIFERENTES VALORES PARA a COMPRENDIDOS EN EL RANGO (1, 2, . . . 180), V. G. a1 = 60, a2 = 75, a3 = 25, a4 = 29. MCD (60, 181) = 1 COMPROBACION CON a1 = 60. J(60, 181) = - J(30, 181) = - {J(15, 181)} (- 1) J(15, 181)} = J(1, 15) J(1, 15) = 1 COMPROBACION CON a2 = 75 MCD (75, 181) = 1 J(75, 181)} = {J(31, 75)} = {J(13, 31)} (- 1) (- 1)J(13, 31) = (- 1) {J(5, 13)} = (- 1){J(3, 5)} (- 1){J(3, 5)} = (- 1){J(2, 3)} = (- 1){J(1, 3)} (- 1) J(1, 3) = 1 COMPROBACION CON a3 = 25 MCD (25, 181) = 1 J(25, 181)} = J(6, 25) = J(3, 25) J(3, 25) = J(1, 3)} = 1 LUEGO 181 ES UN NUMERO PRIMO CON PROBABILIDAD 0.875
17

3. METODOS PARA DETERMINAR LA PRIMALIDAD DE UN NUMERO

DEFINICION: LA FUNCION TOTIENT ( DEL LATIN TOTUS = COMPLETO) DE EULER TAMBIEN DENOMINADA FUNCION PHI Y DENOTADA POR (p) ES EL NUMERO DE ENTEROS POSITIVOS MENORES QUE p QUE SON PRIMOS RELATIVOS CON p, ES DECIR, CUMPLEN LA PROPIEDAD DE QUE: MCD (ri, p) = 1 PARA TODO ri < = p. PRUEBA:DADO QUE UN NUMERO PRIMO TAN SOLO ES DIVISIBLE POR SI MISMO O LA UNIDAD, ENTONCES SE CUMPLE QUE: ri = { 1, 2, 3, . . . (p - 1)} SON PRIMOS RELATIVOS CON p Y mcd (ri , p) = 1 POR LO TANTO (p) = p - 1. TEOREMA: SI p ES UN NUMERO PRIMO (pe) = p e - 1 (p - 1). PRUEBA: SI p ES UN NUMERO PRIMO, LOS UNICOS NUMEROS QUE TIENEN FACTORES COMUNES CON pe SON: p1, p2, p3,. . . pe, POR LO TANTO: (pe) = p e - p e - 1 = p e - 1 (p - 1) = p e (1 - 1/p)
18

3. METODOS PARA DETERMINAR LA PRIMALIDAD DE UN NUMERO

TEOREMA : SI mcd (p, q) = 1 ENTONCES O(p x q) = O(p) x O(q). PRUEBA: LA PRUEBA A ESTE TEOREMA SE ENCUENTRA COMO UN ANEXO A ESTE CURSO. TEOREMA: SI n = p x q SIENDO n Y q NUMEROS PRIMOS, ENTONCES O(n) = (p - 1)(q - 1). PRUEBA: O(n) = O(p x q) Y O(P) = p - 1 MIENTRAS QUE O(q) = q - 1 ENTONCES O(n) = (p - 1)(q - 1). TEOREMA: SI n = p1e1 x p2e2 x . . . pkek SIENDO pi = PRIMO V i < k Y ENTONCES: O(N) = n(1 - 1/ p1) x (1 - 1/ p2) x . . . (1 - 1/ pk) SI TODOS LOS pis SON DIFERENTES. PRUEBA: O(n) = O(p1e1 x p2e2 x . . . pkek ) = O (p1e1 ) x O (p2e2) . . . O( pkek ) DADO QUE pi ES PRIMO, ENTONCES piei ES PRIMO CON RELACION A pkek O(n) = p1e1 (1 - 1/p1)) x p2e2 (1 - 1/p2) x . . . . pkek(1 - 1/ pk) O(n) = p1e1 x. . . pkek (1 - 1/p1)) x (1 - 1/p2) x . . .(1 - 1/ pk) = n x (1 - 1/p1)) x. . .(1 - 1/ pk)
19

3. METODOS PARA DETERMINAR LA PRIMALIDAD DE UN NUMERO

TEOREMA DE EULER: SI X ES UN NUMERO PRIMO RELATIVO CON m , ES DECIR, mcd (x. m) = 1 ENTONCES: X O(m) = 1 (mod m) PRUEBA: SEAN a1, a2, . . . a O(m) LOS NUMEROS INFERIORES A m Y PRIMOS CON m Y x UNO CUALQUIERA DE ELLOS. lOS PRODUCTOS a1x, a2x, . . . a O(m)x SON ENTONCES PRIMOS CON m Y LA DIFERENCIA DE CUALQUIER PAREJA DE ELLOS NO ES DIVISIBLE POR m. POR LO TANTO, ESTOS PRODUCTOS SON DIFERENTES AL MODULO m Y RESPECTIVAMENTE CONGRUENTES CON LOS O(m) NUMEROS DE LA SERIE. a1, a2, . . . a O(m) = a1, a2, . . . a O(m) X O(m) (mod m) Y DIVIDIENDO A AMBOS LADOS POR a1, a2, . . . a O(m) X O(m) = 1 (mod m)
20

3. METODOS PARA DETERMINAR LA PRIMALIDAD DE UN NUMERO

EJEMPLO : SEAN m = 12 Y x = 7. ENTONCES:

O(m) = 4 = {1, 5, 7, 11}

a1x, a2x, . . . a O(m)x = 7, 35, 49, 77 a1 a2 ... a O(m) = a1 a2 ... a O(m) X O(m) (mod m) SIGNIFICA QUE: 1x 5 x 7 x 11 = 7 x 35 x 49 x 77 {74} (mod 12) Y DIVIDIENDO POR LA SERIE 1x 5 x 7x 11 1 = {74} (mod 12)

EN RESUMEN O(m) = 4 Y 74 = 2401 = 1 (mod 12)

COROLARIO DE FERMAT: SI m ES UN NUMERO PRIMO Y x ES UN NUMERO TAL QUE mcd (m, x) = 1 ENTONCES SE TIENE QUE: x m - 1 = 1 (mod m)
21

3. METODOS PARA DETERMINAR LA PRIMALIDAD DE UN NUMERO

TEOREMA : SEA m UN PRODUCTO DE NUMEROS PRIMOS NO REPETIDOS:

m = p1 p2 ... p n
B UN ENTERO QUE NO DIVIDE A O(m) A UN ENTERO MENOR QUE m. ENTONCES:

AB = AB mod O(m) (mod m) PRUEBA: SEA z = B mod O(m) ENTOCES B = K O(m) + z. SE SUPONE QUE
z > 0. SEA pk UNO DE LOS FACTORES DE m. SI A NO DIVIDE A pk ENTONCES POR EL TEOREMA DE FERMAT ES POSIBLE ESCRIBIR: A Y COMO pk - 1
pk - 1 = 1 (mod pk)

DIVIDE A O(m), ENTONCES A kO(m) = 1 (mod pk)

Y MULTIPLICANDO POR AZ SE TIENE: A kO(m) + Z = AZ (mod pk)

22

3. METODOS PARA DETERMINAR LA PRIMALIDAD DE UN NUMERO

SI A DIVIDE A pk LA CONGRUENCIA SE SATISFACE TRIVIALMENTE YA QUE z > 0. POR LO TANTO LA CONGRUENCIA ES VALIDA PARA TODO VALOR DE A. SI SE APLICA ESTE MISMO PROCEDIMIENTO PARA TODOS pk SE CONCLUYE QUE: A kO(m) + Z = AZ (mod p1 p2 . . . pn) ES DECIR QUE: AB = AB mod O(m) (mod m) UTILIZACION DE LA FUNCION TOTIENT LA FUNCION O(n) ES DE UNA GRAN UTILIDAD EN CRIPTOGRAFIA POR LAS SIGUIENTES RAZONES: SE PUEDE POSTULAR LA SIGUIENTE IGUALDAD CON BASE EN EL TEOREMA ANTERIOR: (AB) mod C = (AB mod O(C)) mod C SI O(C) < B SE REDUCE LA COMPLEJIDAD EN EL CALCULO DE EXPRESIONES EXPONENCIALES

23

3. METODOS PARA DETERMINAR LA PRIMALIDAD DE UN NUMERO

EJEMPLO (129) mod 7 = (129 mod O(7)) mod 7 = (129 mod 6)) mod 7 = (123) mod 7 = 6 (256121) mod 124 = (256 121 mod O(124)) mod 124 O(124) = O(31 x 4) = O(31) x O(4) = 30 x 2 = 60 (256 121 mod 60) mod 124 = (256 1) mod 124 = 8 TEOREMA : (AB x CD) mod E = {(AB) mod E x (CD) mod E} PRUEBA : ASUMASE LO SIGUIENTE: (AB) mod E = s1 (CD) mod E = s2 AB = q1 E + s1 Y CD = q2 E + s2 AB x CD = (q1 E + s1 )(q2 E + s2 ) = q1 q2 E2 + (s1 q2 + s2 q1)E + s1 s2 (AB x CD) mod E = (s1 s2 ) mod E = {(AB) mod E x (CD) mod E} mod E EJEMPLO DE APLICACIN: {(128)343} mod 527
:\FIGUERED\POWER\UDIS\SEGUREDES\CURSO

24

3. METODOS PARA DETERMINAR LA PRIMALIDAD DE UN NUMERO

DESARROLLO (128343) mod 527 343 = 256 + 64 + 16 + 4 + 2 + 1 (128343) mod 527 = (128 256 12864 12816 1284 1282 128) mod 527 (128343) mod 527 = (128 256 mod 527 x 128 64 mod 527 x 128 16 mod 527 x 128 4 mod 527 x 128 2 mod 527 x 128 mod 527) mod 527

128 mod 527 = 128 (128 2 mod 527) mod 527 = (128 mod 527)2 mod 527 = 47 (128 4 mod 527) mod 527 = ((128 2 mod 527) mod 527)2 = 472 mod 527 = 101 (128 16 mod 527) mod 527 = ((128 4 mod 527) mod 527)4 mod 527 = 1014 mod 527 = 35 (128 64 mod 527) mod 527 = ((128 16 mod 527) mod 527)4 mod 527 = 354 mod 527 = 256 (128 256 mod 527) mod 527 = ((128 64 mod 527) mod 527)4 mod 527 = 2564 mod 527 = 35 128 mod 527 x (128 2 mod 527) mod 527 = 128 x 47 mod 527 = 219
:\FIGUERED\POWER\UDIS\SEGUREDES\CURSO

25

3. METODOS PARA DETERMINAR LA PRIMALIDAD DE UN NUMERO

DESARROLLO (128 4 mod 527) mod 527 x (128 16 mod 527) mod 527 = 101 x 35 mod 527

= 373 (128 64 mod 527) mod 527 x (128 256 mod 527) mod 527 = 256 x 35 mod 527 = 1 (128343) mod 527 = (219 x 373 x 1) mod 527 = 2

26