FACTURACION EN FUNCION DE LOS RESTOS

CUADRATICOS , MODULO 144 n

ºFACTORIZACION EN FUNCION DE LOS RESTOS CUADRATICOS ,MODULO 144 n

====================================================================

Como sabemos, la factorización consiste en llegar a conocer los divisores de un número

dado.

La identificación de los números y de los factores primos de un número compuesto , jue-

ga un papel crucial de gran parte de los esquemas de la criptografía , sistemas creados para guardar en

secreto los secretos. (1)

En el siglo III antes de Cristo , Eratóstenes de Cirene descubrió la criba que se le conoce

con ese mismo nombre .

Hace dos o tres décadas, demostrar interés por la factorización, era síntoma de excentri-

cidad; únicamente un puñado de teóricos de los números se preocupaban de luchar con kilométricas se-

ries de dígitos.

Hoy día resulta de mucho más interés, debido a que la seguridad de varios sistemas im-

portantes de criptografía, depende de la dificultad de factorizar números de 100 ó más dígitos. (2)

En 1971 , John Brillhart y Mike Harrison , demostraron dando un rodeo ,en lugar de ,

con ataque directo, la factorización de un número “duro “. La idea está basada en hallar dos números

2 2

“x” e “y” que satisfazgan la ecuación x - y = N . En otras palabras , el matemático que trate

de descomponer un compuesto “duro” , habrá de encontrar 2 cuadrados, cuya diferencia sea el número a

factorizar. (3)

Este método se encuentra recogido , en carta sin fecha , aproximadamente año 1643 y

dirigida por Fermat al fraile Marin Mersenne , teólogo y filósofo ,amigo de Descartes, y que escribió

algunos trabajos de matemáticas. (4) .

En “Introducción a la Teoria de los números primos” (5) ,de Fernández-Asenjo y Tena

Ayuso, éste último cita algunas variantes al método de Fermat , como , “Factorización con cribas” (6) ,

“Algoritmo de Bases de Factores” (7).

El presente método de factorización , es una variante del “método de Fermat” , que

simplifica éste, en función de los restos cuadráticos módulo 144 n. Ello es que procede ,antes de nada,

exponer lo relacionado con dichos restos.

Restos cuadráticos de los factores de un número , módulo 144 n .

Dado un número impar , “N” , no múltiplo de 3 ni de 5 , y cuyos divisores son “x “ e

“ y “ , podemos conocer “a priori” el resto cuadrático , módulo 144 n ,de :

2

( x + y )

--------------  R ( módulo 144 n )

4

Nuestro punto de partida será :

2 2

( N + 1) ( x + y )

------------ - ------------ , y después del correspondiente desarrollo , llegamos a ,

4 4

2 2

( N + 1 ) ( x + y ) (x + 1) ( x- 1 ) ( y + 1 ) ( y - 1 )

----------- - ----------- = ---------------------------------------- = DIFERENCIA

4 4 4

En un principio hemos de precisar que “N” puede estar encuadrado en uno de estos tres Grupos :

Grupo nº 1 :

N  + ó - 3 ( módulo 8 )

Grupo nº 2 :

N  + ó - 1 ( módulo 8 ) x  + ó - 1 ( mod.8 ) y  + ó - 1 ( mod.8 )

Grupo nº 3 :

N  + ó - 1 ( módulo 8 ) x  + ó - 3 ( mod. 8 ) y  + ó - 3 ( mod.8 )

---------------------------------------------------------------

Si “N” pertenece al 3º Grupo :

Si (x+1) no es múltiplo de 4 ,lo será (x-1) , o viceversa .

Si (y+1) no es múltiplo de 4 ,lo será (y-1) , o viceversa .

DIFERENCIA  0 ( módulo 16 )

Si “ N ” pertenece al 1º Grupo :

Si ( x + 1 ) no es múltiplo de 8,lo será ( x - 1 ), o viceversa.

Si ( y + 1 ) no es múltiplo de 8,lo será ( y - 1 ), o viceversa.

DIFERENCIA  0 ( módulo 32 )

Si “ N ” pertenece al 2º Grupo :

DIFERENCIA  0 ( módulo 64 )

Por otra parte , como ni “ x ” ni “ y ” son múltiplos de “ 3 ” :

Si ( x + 1 )  0 ( mod. 3 ), implica que ( x - 1 ) no  0 ( mod.3 )

Si ( y + 1 )  0 ( mod. 3 ), implica que (y -1 ) no  0 ( mod. 3 )

o viceversa en ambas.

Conclusión :

Si “ N “ es del Grupo 3º .- DIFERENCIA  0 ( módulo 144 )

Si “ N “ es del Grupo 1º .- DIFERENCIA  0 ( módulo 288 )

Si “ N “ es del Grupo 2º.- DIFERENCIA  0 ( módulo 576 )

Con esto sabemos que ,

2 2

( N + 1 ) ( x + y )

------------- - ---------------  0 ( módulos 144 ó 288 ó 576 )

4 4

( En la práctica no podemos emplear el módulo 576 ,puesto que en un principio ,no sabemos diferen-

ciar , si un número pertenece al Grupo 3 ó 2 )

Creemos haber justificado el siguiente :

TEOREMA

---------------

“ Dado un número N , impar , no múltiplo de 3 , ni de 5 , congruente ± 1 , módulo 8 ,

cuyos factores “x” e “y” son congruentes ± 3 , módulo 8 , la congruencia de la semisuma de sus

factores , elevada al cuadrado , módulo 144 , es la misma que [ ( N+1) / 2 ] ,igualmente elevado al

cuadrado, y mismo módulo. “

“ Si el número N , impar , no múltiplo de 3 , ni de 5 , también congruente ± 1 , módulo 8

y sus factores “x “ e “y” son congruentes ± 1 , módulo 8 , la congruencia de la semisuma de sus

factores , elevada al cuadrado , módulo 576 , es la misma que [ ( N+1) / 2 ] igualmente elevado al

cuadrado,y mismo módulo”.

“ Por último , cuando N , impar , no múltiplo de 3 , ni de 5 , es congruente ± 3 , módulo

8 , la congruencia de la semisuma de sus factores , elevada al cuadrado , módulo 288 , es la misma

que la de [ ( N + 1 ) / 2 ] elevado al cuadrado , y mismo módulo”.

METODO DE FACTORIZACION

----------------------------------------------

Tiene su fundamento en el citado “teorema” . Se trata de un número “ N “ , impar , no

múltiplo de 3 , ni de 5 , y cuyos factores son

“ x “ e “ y “ . 2 2

( x + y ) ( N + 1 )

-------------  R ( módulo 144 n ) ; -------------  R ( mód. 144 n )

4 4

Como quiera que conocemos el valor de “ N “ ,calculamos el de “R”.- Se trata

de hallar los “cuadrados de Fermat” ,en función de :

a).- El valor de “R.

b).-De los cuadrados que lo puedan generar.

c).-De la congruencia de “N” ,módulo 100.

-------------------------------

CUADRO “A “

--------------------------------------------------------------------------------------------------------------------------

Restos Módulo 144 :

cuadráticos Cuadrados

0 ........ 12-24-36-48-60-72-84-96-108-120-132-144

1 ......... 1-17-55-71-73-89-127-143

4 ......... 2-34-38-70-74-106-110-142

9 ......... 3-21-27-45-51-69-75-93-99-117-123-141

16 ......... 4-32-40-68-76-104-112-140

25.......... 5-13-59-67-77-85-131-139

36 .......... 6-18-30-42-54-66-78-90-102-114-126-138

49........... 7-25-47-65-79-97-119-137

52........... 14-22-50-58-86-94-122-130

64........... 8-28-44-64-80-100-116-136

73........... 19-35-37-53-91-107-109-125

81............ 9-15-33-39-57-63-81-87-105-111-129-135

97........... 23-31-41-49-95-103-113-121

100 .......... 10-26-46-62-82-98-118-134

112 .......... 16-20-52-56-88-92-124-128

121........... 11-29-43-61-83-101-115-133

CUADRO “B”

-------------------------------------------------------------------------------------------------------------------------

Restos cuadráticos y cuadrados , módulo 288 :

• .......... 24-48-72-96-120-144-168-192-216-240-264

• .......... 1-17-127-143-145-161-271-287

• .......... 2-34-38-70-74-106-110-142-146-178-182-214-218-250-254-286

• .......... 3-45-51-93-99-141-147-189-195-237-243-285

• .......... 4-68-76-140-148-212-220-284

• .......... 5-59-85-139-149-203-229-283

36 ........... 6-18-30-42-54-66-78-90-102-114-126-138-150-162-174-186-198-210-222-234-246-258

-270-282

• ........... 7-25-119-137-151-169-263-281

• ............ 8-64-80-136-152-208-224-280

• ............ 19-35-109-125-163-179-253-269

81 ............... 9-39-57-87-105-135-153-183-201-231-249-279

• .............. 31-49-95-113-175-193-239-257

100 .............. 10-26-46-62-82-98-118-134-154-170-190-206-226-242-262-278

112 .............. 20-52-92-124-164-196-236-268

121............... 11-43-101-133-155-187-245-277

144 .............. 12-36-60-84-108-132-156-180-204-228-252-276

145............... 55-71-73-89-199-215-217-233

153................ 21-27-69-75-117123-165-171-213-219-261-267

160 .............. 32-40-104-112-176-184-248-256

169 .............. 13-67-77-131-157-211-221-275

193 ............... 47-65-79-97-191-209-223-241

196 ............... 14-22-50-58-86-94-122-130-158-166-194-202-230-238-266-274

208 ............... 28-44-100-116-172-188-244-260

217 .............. 37-53-91-107-181-197-235-251

225 .............. 15-33-63-81-111-129-159-177-207-225-255-273

241 .............. 23-41-103-121-167-185-247-265

256 ............... 16-56-88-128-160-200-232-272

265 ............... 29-61-83-115-173-205-227-259

CUADRO “C”

----------------------------------------------------------------------------------------------------------------------------

N  Ultima cifra de Dos últimas cifras N  Ultima cifra de Dos últimas cifras

mód.100 base cuadrado base cuadrado mód.100 base cuadrado base cuadrado

----------- -------------------- ---------------------- ----------- ------------------ -----------------------

01 5 01-49-51-99 51 0 24-26-74-76

03 2 ú 8 --------------- 53 3 ó 7 ---------------

05 1 ó 3 ó 7 ó 9 --------------- 55 2 ó 4 ó 6 ú 8 ---------------

07 4 ó 6 --------------- 57 1 ó 9 ---------------

09 5 03-47-53-97 59 0 22-28-72-78

11 0 06-44-56-94 61 5 19-31-69-81

13 3 ó 7 --------------- 63 2 ú 8 ---------------

15 2 ó 4 ó 6 ú 8 --------------- 65 1 ó 3 ó 7 ó 9 ---------------

17 1 ó 9 --------------- 67 4 ó 6 ---------------

19 0 12-38-62-88 69 5 13-37-63-87

21 5 11-39-61-89 71 0 14-36-64-86

23 2 ú 8 --------------- 73 3 ó 7 --------------

25 1 ó 3 ó 5 ó 7 ó 9 ---------------- 75 0 ó 2 ó 4 ó 6 ú 8 ---------------

27 4 ó 6 ---------------- 77 1 ó 9 ---------------

29 5 23-27-73-77 79 0 02-48-52-98

31 0 16-34-64-84 81 5 09-41-59-91

33 3 ó 7 --------------- 83 2 ú 8 ---------------

35 2 ó 4 ó 6 ú 8 ---------------- 85 1 ó 3 ó 7 ó 9 ---------------

37 1 ó 9 ---------------- 87 4 ó 6 ---------------

39 0 08-42-58-92 89 5 17-33-67-83

41 5 21-29-71-79 91 0 04-46-54-96

43 2 ú 8 --------------- 93 3 ó 7 --------------

45 1 ó 3 ó 7 ó 9 --------------- 95 2 ó 4 ó 6 ú 8 ---------------

47 4 ó 6 --------------- 97 1 ó 9 ---------------

49 5 07-43-57-93 99 0 18-32-68-82

EMPLEO DE MULTIPLICADORES

-----------------------------------------------

Cuando la diferencia de los diversos factores es elevada ,al objeto de simpli-

ficar el proceso , se pueden emplear multiplicadores , y hallar la factorización , en un principio , sobre

“ N “ , y más tarde sobre “7 N “ , “ 11 N “ ó “17 N” etc..

___________________________________________

EJEMPLO DE FACTORIZACION:

Factorizar el número 3.972.361

2

( N + 1 )

-----------  121 ( módulo 144 ) .-Los cuadrados congruentes + 121 ,módulo 144 son :

4

11 - 29 - 43 - 61 - 83 - 101 - 115 - 133 . (Cuadro A )

Cuando “N” termina en 61 ,las unidades del cuadrado incognita han de terminar en “5” , o las dece-

nas en 19 - 31 - 69 - 81.- ( Cuadro C ) . El punto de partida , será por aproximación la raíz cuadrada de “ N “ .

2 2

( 13 x 144 ) + 133 = 2.005 2005 - N no  0 ( módulo b )

2 2

( 14 x 144 ) + 29 = 2.045 2045 - N no  0 ( módulo b )

seguiríamos probando con las bases,

( 14 x 144 ) + 115 = 2.131

( 15 x 144 ) + 115 = 2.275

( 16 x 144) + 11 = 2.325

( 16 x 144 ) + 61 = 2.365

( 16 x 144 ) + 101 = 2.405

( 16 x 144 ) + 115 = 2.419

2 2

( 17 x 144 ) + 83 = 2.531 2.531 - N  0 ( módulo 1560 )

2.531 ± 1.560 = 4.091 y 971

N = 3.972.361 = 4091 x 971

BIBLIOGRAFIA

Ivars Peterson.- El Turista matemático .-Alianza Editorial .- (pag.29 )

Ivars Peterson.- El Turista matemático.- Alianza Editorial.- ( pag. 53 )

Ivars Peterson.-El Turista matemático .- Alianza Editorial.- ( pag.55 )

Blas Torrecillas Jover.- Fermat,el mago de los números.- Editorial Nivola ( pag. 33 )

Félix López Fernández-Asenjo y Juan Tena Ayuso.- Introducción a la Teoría de los números

primos.

D.E.Knuth.-The Art of Computer Programming,Vol,2. (Addison-Wesley,1981 )

N.Koblitz.-A course in Number Theory and Cryptography (Springer,1987)

2

1

2