Autor Tema: Criterios matemáticos. Debate. Por Víctor Luis

0 Usuarios y 1 Visitante están viendo este tema.

27 Julio, 2019, 01:23 pm
Respuesta #40

feriva

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 9,173
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Buenos días, Victor Luis.

He estado mirando lo del test de Lucas-Lehmer, que es para primos de Mersenne, pero veo que antes está el test de Lucas, que es para primos en general; no me acordaba absolutamente nada de estos tests, los miré muy poco en su día cuando me hablaste de ellos.

Veo que la idea del test de Lucas tiene en común algo con una que yo te contaba un día para intentar factorizar los semiprimos; era a partir de intentar factorizar el semiprimo quitándole cifras, factorizando primero uno o varios números más pequeños. En el de Lucas, para saber si un número es primo o no, se han de conocer todos los factores de n-1 (factorizarlo completamente) siendo “n” el número a comprobar, lo cual para números grandes puede ser casi tan difícil como llegar a saber si “n” es primo.

Este método de Lucas, en detalle y según la Wiki, se trata de lo siguiente (supongo que lo conoces y mejor que yo):

Sea “n” el número del que queremos saber si es primo y sea “a” un número menor que “n”.

Sean \( q_{i}
  \) los factores primos de “n-1”; o sea, si “n-1” fuera 12, tendríamos \( q_{1}=2;\, q_{2}=3
  \); simplemente representa eso, los factores primos distintos.

Entonces, si existe un “a” para el que se cumplen estas dos condiciones (no sólo una)

\( a^{n-1}\equiv1\,(mod\: n)
  \)

y

\( a^{(n-1)/q}\not\equiv1\,(mod\: n)
  \) (para todos los factores q)

en ese caso es primo seguro; y, si no se cumple, es compuesto.

Pongo un ejemplo:

Queremos saber si es primo \( n=1105
  \).

Entonces, \( n-1=1104
  \)

Los factores primos distintos de 1104 son 2,3 y 23.

Al probar la primera condición

\( a^{n-1}\equiv1\,(mod\: n)
  \)

como 1105 es un número de Carmichael en este caso, la cumple para cualquier “a” coprimo con él, luego pasaría la primera prueba, que es la del pequeño teorema (aunque en este caso es claro que no es primo al acabar en 5, pero supongamos que no supiéramos eso).

Pero para todo “a” va a fallar la congruencia en la segunda condición \( a^{(n-1)/q}\not\equiv1\,(mod\: n)
  \)”; esto quiere decir que también habrá que probar distintas bases “a” en el método de Lucas; sin embargo, tiene esta ventaja (la de la segunda condición) de no ser vulnerable respecto de los pseudoprimos; si “n” no es primo, no va a existir ningún “a” que cumpla esas dos condiciones, si es primo, siempre va a existir alguno; que, normalmente, se encontrará sin recorrer demasiados valores (dependiendo de lo grande que sea “n”, claro).

Citar

°) Al respecto y sobre la explicación que expusiste, indicando 'a' como una base y que el teorema se cumple, como que todo primo debe cumplir la congruencia con resto (1) para toda base 'a' ... Lo que implicaría realizar varias, muchas, en sí demasiadas operacionalizaciones como evaluaciones.


En cuanto a las bases “a” a probar, existe una forma de ver si es primo pero no añade nada práctico al test (de hecho ya usa esto que digo).

Son lo que se llaman raíces primitivas.

Si “n” es primo, todos los números menores que “n” son coprimos con “n”; ninguno tiene un primo en común, como es obvio.

Para buscar una raíz primitiva del primo “n”, debemos buscar los restos de las potencias de un número “a” dadas por \( a^{n-1},a^{n-2}...a^{2}
  \) al ser divididas por “n”; si resulta que el conjunto de los restos es precisamente el formado por \( (n-1),(n-2)...2
  \) sin faltar ninguno, entonces “a” es una raíz primitiva módulo “n”; si falta alguno no es raíz primitiva del primo.

Por el ejemplo, el caso más sencillo de ver, con los números más pequeños, dejando el 2 aparte, es éste:

Si el primo es “n” es 5, entonces a=3 es una raíz primitiva; vamos a verlo sacando los restos

\( 3^{5-1}\equiv1(mod\,5)
  \)

\( 3^{5-2}\equiv2(mod\,5)
  \)

\( 3^{5-3}\equiv4(mod\,5)
  \)

\( 3^{5-4}\equiv3(mod\,5)
  \)

Y tenemos que el conjunto de restos es {1,2,4,3}, es decir, todos los restos posibles módulo 5 menos el cero; entonces esto quiere decir que es primo.

Precisamente es lo que hace que funcione el test de Lucas; si es primo existe al menos una raíz primitiva, y una raíz primitiva siempre va a cumplir la primera y segunda condición, puesto que si elevamos a las potencias (n-1)/q con q un divisor primo distinto de 1, tenemos que (n-1)/q siempre es distinto de (n-1), que es la potencia de “a” que deja resto 1 en la primera condición; de ahí que la segunda condición sea \( a^{(n-1)/q}\not\equiv1\,(mod\: n)
  \), o sea, distinto de resto 1; por eso, si es raíz primitiva de un primo, nunca deja resto 1 (deja resto 1 si q=1, que es el caso del Pequeño teorema de Fermat, el de la primera condición).

El en caso de los compuestos, las raíces primitivas, si existen, son las que dejan de restos la colección de todos los coprimos (coprimos con el compuesto que se está comprobando, se entiende) menores que él, sin faltar ningún coprimo; pero los coprimos no son  todos los números menores que el compuesto, como sí pasa con un primo, son sólo los que no tienen factores en común, con lo que la diferencia dada entre las raíces primitivas de los primos y los compuestos es suficiente para distinguir a los primos a partir de éstas.

El test de Lucas-Lehmer es distinto, es para los primos de Mersenne solamente; pero creo que el de Lucas también puede resultarte interesante para ver cosas.

Saludos.

27 Julio, 2019, 08:33 pm
Respuesta #41

feriva

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 9,173
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino

Hola otra vez, Víctor; he seguido leyendo y esto que dices aquí merece un comentario especial:

Citar

Pero les confronto a que lo demuestren, con algún método de primalidad, donde Fermat no nos sirve; peor aún Miller_Rabin, por no ser "métodos deterministas" ...


Eso que dices ahí no es cierto en cuanto a Fermat. No entro en Miller porque no lo conozco bien; me refiero al Pequeño Teorema de Fermat, donde existe el mito de que no detecta los pseudoprimos. Pues sí los detecta, pese a lo que hayas leído.

En Wiki, aquí, https://es.wikipedia.org/wiki/Test_de_primalidad lo califica de probabilístico debido a los números de Carmichael; pero no se puede considerar así:

Tomemos un número primo, en primer lugar, para ver una cosa. Usemos todas las bases “a” posibles hasta que lleguemos al valor del propio primo; a partir de ese momento, y por primera vez, la congruencia \( a^{(p-1)}\equiv1\,(mod\, p)
  \) falla; debido, obviamente, a que “a” entonces no es coprimo con “p”, por ser el propio “p”.

Igualmente, por la misma razón, pasa con los pseudoprimos, pero como son compuestos, fallan cuando toman el valor de cualquiera de sus factores, que son menores que el pseudoprimo. Por tanto, al fallar cuando “a” es igual al factor más pequeño del pseudoprimo, ya sabemos que no es primo (porque eso, ya digo, en los primos sólo pasa con números tan grandes como él o mayores, no con menores).

Además, los números que se conocen de Carmichael son libres de cuadrados (los que he visto, supongo que serán todos así, no sé) y con muchos factores, con lo que están formados siempre por uno o varios primos mucho menores que el pseudoprimo.

De hecho, por esta razón, el Pequeño Teorema es perfecto para factorizar esos números. Basta poner la condición del teorema para cribar e ir desechando los que cumplan a la vez \( mcd(a,n)=1
  \) y \( a^{n-1}\not\not\not\equiv1(mod\, n)
  \); si pasa eso con alguna base no son de Carmichael. Y de los que van pasando esa criba miramos el “a” que divide “n” y nos van saliendo todos los factores del pseudoprimo “n”.

Aunque ahora no tienes ordenador, te pongo un programa que he hecho con esa idea usando sólo el Pequeño Teorema:

Código: [Seleccionar]

 from sympy import*


M=[]

def f(n):
global M

for b in range (2,m):

a= b**(n-1)

if gcd (b,n) == 1 and  a % n != 1:

M=[]

return

elif gcd (b,n)!= 1 and n % b ==0:

M.append (b)

for n in range (1, 3000, 2):

m= int (sqrt(n))

if M != []:

print M

M=[]

f(n)


En el rango que lo he puesto detecta los primeros cuatro números de Carmichael y da su factorización:

Escritorio/programs$ python Fermat.py

[3, 11, 17] [5, 13, 17] [7, 13, 19] [5, 17, 29] [7, 13, 31]

No tarda mucho; de hecho, para al menos los primeros pseudoprimos, creo que será más rápido que el test de Lucas, pues los factores son muy pequeños y da enseguida con el primero; y aquí sólo se usa la primera comprobación, Fermat tal cual.

En esta lista de números de Carmichael

https://primes.utm.edu/glossary/page.php?sort=CarmichaelNumber

el número que tiene su factor más pequeño, y que es más grande respecto de los factores pequeños de los otros números, es uno que tiene al 37 (creo, no sé si he mirado bien del todo, pero creo). Pero el más grande que sale en la lista, que es 7536,1 tiene por factor más pequeño el 11, luego tiene el 13 también... o sea, que pese al tamaño, siempre parece que van a tener factores comparativamente pequeños respecto del número.

El Pequeño Teorema de Fermat es un test determinista, por tanto, probando bases hasta la raíz de “n” tarde o temprano desenmascara al pseudoprimo. Otra cosa es que, en números de Carmichael muy grandes (que aún no se conocen, parece ser) el factor más pequeño pueda estar muy lejos como para decir en un tiempo razonable que no es primo; pero esto no implica que sea probabilístico, ni mucho menos, puede que el tiempo no sea polinomial o cualquier cosa así, pero sí es determinista. Si decimos que no lo es, por las mismas, ningún test sería determinista, porque hay números cuya primalidad no se puede conocer, de puro enormes, con ningún tipo de test.

Así que eso es un mito, no te lo creas, un mito debido a la consideración de que la relación sirve sólo para coprimos, pero es que, precisamente por eso, cuando no son coprimos... no pasan el test y canta la gallina.

Saludos.

28 Julio, 2019, 12:28 pm
Respuesta #42

Víctor Luis

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,164
  • País: bo
  • Karma: +0/-0
  • Sexo: Masculino
Buenas Feriva ...

°°°)  Me complace aprender de las clases magistrales que nos expones ... Lo de Python no lo puedo comprobar, más que todo ponerlo a prueba y confío y agradezco el desarrollo que hiciste ... Pero algo sin duda, es que ningún método de primalidad, por más demostrado y determinista que sea, no se compara con el de Lucas Lehmer y en esto ... No podemos meter en una sola bolsa a todos los métodos de primalidad; sino, diferenciar aparte para Números de Mersenne y aparte para el resto de naturales Impares no múltiplos de (3) es decir 'nb' Naturales Base.

   •) Es absurdo determinar la primalidad de un natural de Mersenne por Factorización, por lo que descartemos ese camino al tratar sobre Primalidad en estos naturales. Ahora bien, como indicas, en nuestra actualidad, no se cuenta con métodos de primalidad que garanticen y/o aseguren la primalidad de naturales grandes ... (en mi criterio, algo vergonzoso)  Imagínate la complejidad del mejor método de primalidad en determinar la primalidad de:  n=(2^(23209)-1) un natural de más de 7300 cifras ... Y probaste determinar com "Mathematica" la primalidad de: (2^(44497)-1) el 26° primo de Mersenne de más de 10000 cifras?

•) Por más la simplificación para el método de primalidad de Fermat que se dé, aplicarlo para determinar la primalidad de los Números de Mersenne, no es una opción práctica y es que hasta cuántas bases 'a' se deben operar para el  Mp[26°] ?  ... Con la PEM realizamos "un solo" proceso operacional y realizaremos "un solo proceso operacional" para determinar la primalidad de todos los 'Mn' en darse ... Qué opinas al respecto?


PSEUDOPRIMOS DE CARMICHAEL.
----------------------------------------------------------

   Agradeciendo a Feriva por la dirección web de la información, los Naturales Compuestos denominados como 'Pseudoprimos' de Carmichael, mismos que se consideran porque hacen fallar a los métodos de primalidad expuestos, donde pasarían por primos ... Compartiendo lo de "Pseudo" pero no así por considerarse que como no hay más criterios sobre Primalidad y métodos desarrollados expuestos en la literatura.

   mc = (561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041,46657,52633,62745,63973,75361)

   Estos son los compuestos de Carmichael, de la página web, indicándose (16) de los cuales descartamos (5) por ser múltiplos de (3) y múltiplos de (5) quedando (11) de los cuales el (91%) pertenecen a PIG(13) y uno solo a PIG(7) lo que en el Conjunto VL todos estarían en PG(7) lo que resume el origen de estos naturales, aparentemente ... Pero veamos algo más sobre estos Naturales Compuestos, mal llamados 'Pseudoprimos' me refiero a los (11) válidos, donde indicaremos su valor natural, su Grupo PIG y sus divisores específicos primos, veamos:

   1729     PIG (13)     (7,13,19)
   2821     PIG(13)      (7,13,31)
   6601     PIG(13)      (7,23,41)
   8911     PIG(7)        (7,19,67)
   15841   PIG(13)      (7,31,73)
   29341   PIG(13)      (13,37,61)
   41041   PIG(13)      (7,11,13,41)
   46657   PIG(13)      (13,37,97)
   52633   PIG(13)      (7,73,103)
   63973   PIG(13)      (7,13,19,37)
   75361   PIG(13)      (11,13,17,31)


•) Me atreví intentar factorizar:  mc(75361) teniendo:  cet(240) con lo que sería sencillo el determinar 'Kf' y con éste 'Ks' con el que como ya sabemos, determinamos 'X' específico y ya tenemos factorizado al compuesto ... Pero resulta que este compuesto 'no es semiprimo', por lo que saber de 'cet' no nos es específicamente útil, ya que:

   (11) = (2•5)
   (13) = (2•2•3)
   (17) = (2•2•2)
   (31) = (5)

   De aquí que:  (2^(3)) • (3) • (5)  =  (120)  no determinan el 'cet' de 'mc' que es (240) ... Pero si, cuando consideramos que mc(75361) sus divisores son:   (143,527)   la cosa es llegar a que:  (240) = (2^(4)) (3) (5)  desde el 'cet' de sus divisores primos, para dar gusto al [EN] "Enfoque Natural" ... Donde desde el Conjunto FV y los otros, todo 'nb' compuesto se conforma como producto de sólo dos naturales divisores (P,Q) mismos que son naturales base, sean estos primos, primo y compuesto ó ambos divisores Compuestos, lo que en algo contradice a que los compuestos se comprenden por la descomposición única en factores primos.

°••) Es por esto Feriva, la importancia de tu hilo: "Factorización de Semiprimos" ... Porque conjeturo y predigo, que a partir de los semiprimos, desde su análisis estructural, comprenderemos lo que es la Distribución de los Números Primos *** Superando con todo respeto a nuestro Riemann, en lo que se refiere a su criterio de primalidad universal.

°°)  Todos los Naturales de Carmichael, son superados por la "PEN" ... Y es que acaso no se dan Pseudoprimos de Carmichael que sean compuestos semiprimos ??


Saludos Cordiales .......

28 Julio, 2019, 12:56 pm
Respuesta #43

feriva

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 9,173
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino


°°)  Todos los Naturales de Carmichael, son superados por la "PEN" ... Y es que acaso no se dan Pseudoprimos de Carmichael que sean compuestos semiprimos ??


Saludos Cordiales .......

Hola, Víctor Luis, buenos días.

Creo que no se ha encontrado ninguno semiprimo; puedes pinchar en este enlace donde aparece una tabla de estos números con números más grandes que ésos de la lista preliminar; baja un poco en la página hasta la cuarta tabla, una que ocupa todo el ancho de la página. Ahí verás a la izquierda el número y a la derecha sus factores. Observa lo que te decía, son factores muy pequeños y aumentan en la medida que el número es grande, por eso en la tabla van formando una pirámide. Si esto es más o menos así para todos, al tener cada vez más factores y ser más pequeños, el propio test de Fermat los descartaría antes incluso que a otros que no son Carmichael (creo que pasaría eso, aunque no lo sé porque no lo he probado).

http://www.chalcedon.demon.co.uk/rgep/cartable.html

Saludos.

28 Julio, 2019, 03:04 pm
Respuesta #44

Víctor Luis

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,164
  • País: bo
  • Karma: +0/-0
  • Sexo: Masculino
 Buenas Feriva ...

°). Pues me llevaría más tiempo abordar la factorización de los demás Compuestos Pseudoprimos de Carmichael, ... primero para determinar su 'cet' y luego determinar su 'Kf' con éste su 'Ks' el cual nos da 'X' específico el cual nos permite factorizar al compuesto que sea.

••)  Más recordemos que estábamos en la Primalidad de Números de Mersenne, 'Mn', ... Métodos de primalidad dados a lo largo de la historia, que siendo eficientes para naturales base, no lo son para naturales Compuestos distintos a los que son 'Mn' Compuestos ... ... ... Reconozcan que analizar más allá de esto ... les afronta total incertidumbre, sobre el intento siquiera comprender algo más de lo que pudiera ser el absurdo de un criterio Estructural ... Sólo pierden menos de una decena de años ... Y acaso, esto repercute, en lograr un mejor destino?  ... ...

   ••• Sí a la CIA y al PENTÁGONO le diéramos nuestro conocimiento, ... Lo aprovecharían para eliminar a los engendros terroristas, algo bueno ... y qué después ??? ... A caso no sería mejor, que cada ser humano, decidiera la privacidad de su comunicación en que necesita realizar ???  Cuando con la criptografía actual no se nos garantiza la seguridad de una conversación,  entre dos individuos; cuyo 'multicifrado' es protegido por las claves privadas elegidas, no solo en cantidad; sino también en cuanto a las mejores disponibles ofrecidas al usuario para una óptima seguridad informática.

•••). Facebook y la Nube ... A caso disponen de seguridad informática como ésta, para seguir en el juego de resguardar la información que "muchos" ... ... Apuestan su "fe" en que así será, por lo menos en un lapso de (6) años ?? ... Guarda tú dinero en un colchón, antes de 2025, sí es que quieras disponer de algún efectivo, sin que la moneda virtual: "libra" se apodere, de lo que en verdad tienes, ... y es que tú permitiste que la data informática, te diga, lo que tienes, te diga lo que puedes acceder y con esto, ... lo que puedas ser ... ! Te están limitando!  ... "Mira que ya iniciaron con la destrucción de la "UEU" (Unión Europea) por parte de RUSIA = (URSS + CHINA + COREA DEL NORTE)

   ***) Se ha hecho un mal abuso de la información global que es 'Internet', ... Ya no vasta que fuentes informaticas como "CNN" se den la tarea de verificar una noticia, mientras las redes sociales clandestinas contradicen la información y peor que ésto, la tesgiversan, de lo que en realidad sucede.

  °°°) Ten en cuenta que podemos filtrar, identificar, marcar, hacer seguimiento indefinido del usuario y todo lo que en más de te ocurra, ... con la implementación del "Enfoque Estructural" sobre lo que consideran y valoran hasta ahora en esto que llaman, "seguridad informática" ... Aprovechando por los rusos, sin saber lo que en verdad debe considerarse como "seguridad cifromatica" ... Algo como que un usuario, compleje su cifrado, con el simple hecho de complejar su 'Multicifrado' en tiempo real ... Ni Putin  ni Trump, podrían saber lo que Feriva y Yo estemos charlando.

 •) Cuán seguro sería y cuán desastroso sería, ... Aplicar en estos tiempos mi absurda metodología ...!

Saludos Cordiales a Todos .......

28 Julio, 2019, 07:26 pm
Respuesta #45

feriva

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 9,173
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola, Víctor Luis.

Citar

••• Sí a la CIA y al PENTÁGONO le diéramos nuestro conocimiento, ... Lo aprovecharían para eliminar a los engendros terroristas


Si te refieres a conocimiento matemático, si les dieran el mío... me parece que iban a aprovechar muy poco :)

En cuanto a lo otro, no sé casi nada de criptografía, no sé decirte. Cuando oigo lo de las claves públicas y privadas y eso, sé lo que son por los primos, pero no sé exactamente cómo funcionan en la práctica.

Citar

Guarda tú dinero en un colchón, antes de 2025, sí es que quieras disponer de algún efectivo


¿Dinero?, ¿qué es eso? Creo recordar que un día tuve algo llamado así, sí, pero ahora lo mismo me da guardarlo en el banco que en el colchón :D

Citar

Ni Putin ni Trump, podrían saber lo que Feriva y Yo estemos charlando.


Ni feriva tampoco, menudo eres tú cifrando con siglas y nombres raros :D

Citar

°). Pues me llevaría más tiempo abordar la factorización de los demás Compuestos Pseudoprimos de Carmichael, ... primero para determinar su 'cet' y luego determinar su 'Kf' con éste su 'Ks' el cual nos da 'X' específico el cual nos permite factorizar al compuesto que sea.


No entiendo. Al ser números con muchos factores “graduados” en tamaño, que empiezan por ser bastante pequeños y, por ende, parecen ser todos libres de cuadrados, resultan especialmente sencillos de factorizar. Lo que no puedes hacer es encerrarte sólo en tus métodos, a cada tipo de números les va bien un tipo de test. Aquí no se puede quitar el 3, hay que probar, porque pueden ser múltiplos de 3. Llama al 2 y al 3 como quieras, pero por lo menos considera que existen y que son factores de muchos números, no todo son Mersennes ni semiprimos de factores grandes.

*** En cuanto a la cita del otro hilo que he traído aquí:

Citar

°) En tú criterio natural, primero, partes en considerar y validar al conjunto de naturales primos, como tal que si fueran, Números Primos, conocibles y comprensibles y por supuesto, demostrables como darles a comprender y más que todo, "convencer" sobre un criterio que desconocen ahora y pronto, aglomeraran en tratar de comprender lo que ya les hube dicho desde hace meses atrás ......

°°) Carmichael aspiró a mucho, ... Supuso que sus compuestos, eran naturales algo así místicos, que pasarían externamente como primos divisores, algo que es absolutamente cierto y con certidumby_Parcial respecto a todos los naturales Impares y todos los números de Mersenne.

•) Consideremos primalidad como factorización, ante los casos de análisis en la Factorización Estructural.

Saludos Cordiales .....


Pues esperaremos a cuando quieras dar a conocer ese criterio; nada qué decir a eso.

...

No pasan como primos divisores por lo que te dije, porque tienen factores que se delatan, tanto por el método de Fermat como por el método de conteo corriente, probando los números; es obvio, si un número es múltiplo de 3 ó de 11 ó de 13 ó de 17... o cualquier otro, como lo son los Carmichael y cualquier compuesto, pues cualquier criba (aunque pueda tardar varias vidas, eso sí) dará con esos factores.

Carmichael encuentra que hay números que cumplen esto siempre:

si \( n,a
  \) son coprimos, entonces \( a^{n-1}\equiv1\,(mod\, n)
  \) para todo “a” (para todo coprimo con “n”, como ya se ha dicho).

Pero cuando “a” es factor de “n”, entonces no es verdad; como ejemplo, el más sencillo, \( 11^{561-1}\not\equiv1\,(mod\,561)
  \) (puedes comporbarlo con Wolfram si puedes acceder con el teléfono; y también probar que falla con los otros dos factores de 561, que son 3 y 17).

Entonces, como falla para un número menor que de 561, esto es \( a<561
  \), cuando lleguemos a ese “a” ya sabemos que no es primo (y “a” va a ser menor o igual que la razí de 561).

Por las mismas, si es primo, falla a partir de a=n, nunca antes, porque “n” no tiene más divisores que “n” y 1 y la congruencia sí se cumple para todo a<n al ser coprimos hasta ahí. Tambien puedes comporbarlo; por ejemplo, 127 es primo, \( 127^{127-1}\not\equiv1\,(mod\,127)
  \); lo cual es obvio, directo, pues 127 elevado a cualquier potencia es divisible por 127 y el resto es cero, no 1.

Y cuando son compuestos es igual de obvio, pues la congruencia inicial de Fermat es ésta \( a^{n}\equiv a\,(mod\, n)
  \) y al dividir entre “a” queda la otra; o sea \( a^{n}-a=ka
  \) nos lleva a \( a^{n-1}-1=k
  \); lo que evidentemente quiere decir que, despejando, k+1 es divisible entre “a”; ahora bien, que pasa si “k” es múltiplos de “a”, pasa que entonces \( k=ta
  \), para algún entero “t”, y en ese caso k+1 es \( ta+1
  \), que al dividir entre “a” los sumandos nos da un entero “t”, más un número menor que uno \( \dfrac{1}{a}
  \) por ser “a” mayor que 1; así pues, tenemos que es “t” más una parte no entera; no se cumple nunca con ningún factor que sea común con un factor de “n”; nunca, y ya se trate de un compuesto de Carmichael o de quien sea.

Saludos.



31 Julio, 2019, 10:56 am
Respuesta #46

Víctor Luis

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,164
  • País: bo
  • Karma: +0/-0
  • Sexo: Masculino
Buenas Feriva ...

••)  Comprendo lo que me explicas con el ejemplo de (561) donde la base 'a' al ser comprimo con 'n' el resto de la congruencia es (1) y de no darse esto, se daría que 'n' es compuesto ... Pero si 'n' es primo, los naturales menores a este y mayor a (1) son coprimos con este, serían bases 'a' que con el resto (1) corroborarian su primalidad, lo que es complejo, simplemente para determinar su primalidad ... Y es que con la PEN no se realizarían tantos procesos operacionales para determinar la primalidad de naturales tan grandes como los mismísimos Números de Mersenne.

°) Es más, con la PEM, solo realizamos "un solo proceso operacional" para determinar la primalidad de todo Número de Mersenne ... Una Consulta:  cuán complejo es aplicar Fermat:  2^(Mn-1) mod Mn como único proceso operacional para un solo proceso de evaluación, en la determinación de primalidad de los 'Mn' dados, después del último 'Mp' Primo de Mersenne encontrado?   ... En sí, aplicando Fermat, con solo la base a(2)  Cuál sería el tiempo de proceso operacional?


Saludos Cordiales .......

31 Julio, 2019, 01:12 pm
Respuesta #47

feriva

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 9,173
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Buenas Feriva ...

••)  Comprendo lo que me explicas con el ejemplo de (561) donde la base 'a' al ser comprimo con 'n' el resto de la congruencia es (1) y de no darse esto, se daría que 'n' es compuesto ... Pero si 'n' es primo, los naturales menores a este y mayor a (1) son coprimos con este, serían bases 'a' que con el resto (1) corroborarian su primalidad, lo que es complejo, simplemente para determinar su primalidad ... Y es que con la PEN no se realizarían tantos procesos operacionales para determinar la primalidad de naturales tan grandes como los mismísimos Números de Mersenne.

°) Es más, con la PEM, solo realizamos "un solo proceso operacional" para determinar la primalidad de todo Número de Mersenne ... Una Consulta:  cuán complejo es aplicar Fermat:  2^(Mn-1) mod Mn como único proceso operacional para un solo proceso de evaluación, en la determinación de primalidad de los 'Mn' dados, después del último 'Mp' Primo de Mersenne encontrado?   ... En sí, aplicando Fermat, con solo la base a(2)  Cuál sería el tiempo de proceso operacional?


Saludos Cordiales .......

Hola, Víctor Luis, buenos días.

Eso ya es harina de otro saco (o costal, que se dice más habitualmente). Nadie dice que el método sea rápido en general para determinar si un número es primo; yo sólo digo que si se prueban todas las bases necesarias (como mucho hasta la raíz del número) se podrá decir con toda seguridad si el número es primo o no.

Esto podría llegar a ser muy lento si existen pseudoprimos semiprimos o compuestos por pocos factores y grandes; podría tardarse mucho en descartarlos.

Como siempre, todo depende del tamaño del número y de sus factores. Porbar todas las bases para un número muy grande es imposible en un tiempo “humano”, por eso sólo se prueban algunas y, lógicamente, en ese caso no se termina el proceso y puede que no determine la primalidad; pero esto ocurre con cualquier método cuando no se prueba todo lo necesario. Por eso, el Pequeño Teorema sirve normalmente como método previo; la mayoría de los números no son primos ni pseudoprimos, con los que no son así se descartan fácilmente (normalmente enseguida fallan para alguna de las primeras bases que se prueban). Si se ve que, probadas unas cuantas bases, no falla, lo lógico es pasar a otro método más rápido.

No sé en detalle qué haces con el método que llamas la PEM, seguramente será rápido, pero según entiendo es especial para números de Mersenne.

Como te decía, la cosa depende del tipo de números y de lo que queramos llegar a determinar; no es exactamente lo mismo factorizar un número que decir si es primo o no (aunque lo primero implique lo segundo).

Para demostrar lo que digo, te voy a confiar el resultado de mis últimas investigaciones.

Tú sabes que con el método de factorización de Fermat (no el pequeño teorema, el otro) cuanto más cercan están los factores de la raíz antes se encuentran los factores; pues bien, yo he encontrado una fórmula con la que ocurre lo contrario, cuanto más lejos están, más fácil es determinarlos. Sin embargo, esto es relativo a la cantidad de cifras, si existe diferencia entre la cantidad de cifras de los factores no funciona igual. Te explico.

Esto del spoiler son preliminares

Spoiler

Vamos a poner un ejemplo cualquiera, sea el primo 5, entonces

estos son los números anteriores 1,2,3,4, que, en general, escribiríamos como (n-1), (n-2)... siendo en este caso particular n=5.

Son los restos posibles que encontramos al dividir cualquier número entre 5 (salvo el cero).

Ocurre que ese grupo formado por los números menores que un primo, forman un conjunto tal que para cada uno de los elementos sólo existe un inverso modular; que quiere decir lo siguiente:

Si tomamos de aquí {1,2,3,4} el 2, por ejemplo, y lo multiplicamos por otro número del conjunto, solamente el 3 nos va a dar un producto de la forma 5k+1; o sea, resto 1 módulo 5. Fíjate que es cierto \( 2*3=6=5+1
  \); y si buscas no hay otro que multiplicado por el 2 dé resto 1; entonces 3 es el inverso modular de 2 y en este caso no hay otro, es único. Si tomamos el 4, sólo se puede multiplicar por él mismo para que dé resto 1 módulo 5; \( 4*4=16=(3*5)+1
  \); y si tomamos el 1, entonces también el inverso es el propio 1; pues contamos desde cero, que es múltiplo de cinco y de todos:

\( 0\cdot5+1=5k+1
  \) con k=0.

Esto pasa para todos los primos, es una propiedad para esos restos de los primos. Si haces lo mismo con 6 en vez de 5, que es compuesto, tienes los restos {1,2,3,4,5} (dejando el cero aparte). Ahora intenta hacer lo mismo; necesitamos multiplicar dos números y que nos dé un 6k+1; los posibles son:

6+1=7; 12+1=13; 18+1=19; 24+1=25...

Multiplicando dos números no podemos obtener un primo salvo que sea por 1, y el primo más pequeño aquí {1,2,3,4,5} es 5, no siete; luego tenemos que considerar a partir de 25. El único producto que da 25 con esos números es el 5 consigo mismo.

si seguimos buscando los posibles tenemos

30+1, es primo mayor que 5, no lo podemos obtener multiplicando dos de esos restos

36+1 es primo, tampoco

42+1, tampoco

48+1=9; este no es primo, pero es 7*7, tampoco

54+1=55: es 11*5, tenemos en el conjunto 5, pero no 11...

Total, que parece ser que el único para el que existe inverso es 5; y su inverso es el propio 5.

Esto sí es general, para cualquier “n” tenemos que (n-1) tiene de inverso al propio (n-1):

\( (n-1)(n-1)=(n-1)^{2}=n^{2}+1-2n
  \); es un múltiplo de “n” más 1. Por tanto, aquí también ocurre aunque no sea primo.

[cerrar]

Entonces, restando 1, \( (n-1)^{2}
  \) tenemos un \( kn
  \), un múltiplo de “n”.

Por tanto, si tenemos un número compuesto por dos factores (aunque no sean primos o no lo sean los dos, y entonces cualquier compuesto cumple esto) lo podemos expresar siempre así

\( ((p-1)^{2}-1)*((q-1)^{2}-1)=kpq=kR
  \); donde llamo R al compuesto; o sea, ese producto, por la ya dicho, tiene que ser múltiplo de “p” y de “q”, y por tanto de “pq”. También operado se ve que \( k=(p-2)(q-2)
  \).

Haciendo \( q=\dfrac{R}{p}
  \) y despejando (no me entretengo en explicar operaciones, créetelo o, si te interesa, ya me preguntas) obtenemos esta ecuación

\( -p=\dfrac{-R(-k+R+4)\pm\sqrt{R^{2}(-k+R+4)^{2}-16R^{3}}}{4R}
  \)

Como ves, tenemos dos soluciones posibles debido al \( \pm
  \); si tomamos el signo “+” nos da un factor y si tomamos “-” el otro.

De aquí no sabemos “k”, pero sí sabemos, como decía, que es igual a \( (p-2)(q-2)
  \); por tanto, tiene que ser un valor parecido al cuadrado de la parte entera de la raíz de R (y lo es, de hecho).

La parte entera de la raíz se denota por \( \lfloor\sqrt{R}\rfloor
  \).

Bien, pues probando semiprimos con factores de las mismas cifras pero muy separados, resultó que en los casos observados \( \lfloor\sqrt{R}\rfloor^{2}
  \) coincidía en la mitad de las primeras cifras (la mitad menos dos ellas exactamente) con el valor de \( (p-2)(q-2)
  \). Ya digo, en varios casos.

Sin embargo, al tomar semiprimos con primos muy parecidos (iguales en las primeras cifras) la cantidad de cifras en las que coincidían era menor; en una cifra, no mucho, pero tampoco lo he investigado del todo, tengo que probar más.

Esto quiere decir, evidentemente, que usando esta fórmula y el argumento dicho vamos a factorizar antes semiprimos con los factores más alejados que semiprimos con factores más cercanos entre sí (si en ambos cosas los factores tienen las mismas cifras, ya digo).

Si hecha una prueba más exahustiva veo que, en efecto, esta observación no es una mera casualidad, entonces tenemos algo que puede ser útil: usando un algoritmo que vaya probando por Fermat a la vez que por éste.

En fin, que hay que compaginar siempre varios métodos para atacar la factorización. Piensa que un número compuesto por dos factores es como la sábana de una cama; si tiras mucho de un lado se sale del otro, hay que ir tirando de los dos para aproximarnos a los factores o al menos para cribar de una forma eficiente, porque es cosa de dos, no de uno.

En cuanto a saber si es primo o no, si determinar otros factores, sí es más cosa de uno, pero entre comillas. No obstante, no olvides que si se encontrara un método de factorización por acercamiento y que fuera rápido, también diría, lógicamente, si es primo o no; por lo investigar la factorización es muchísimo más interesante que la mera primalidad.

Saludos.

03 Agosto, 2019, 10:06 am
Respuesta #48

Víctor Luis

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,164
  • País: bo
  • Karma: +0/-0
  • Sexo: Masculino
Buenas Feriva ...

••) Disculpa que insista, pero en mi consulta me refería a que siendo:

      mp(48)=(2^(57885161)-1)   un natural primo de más de 17 millones de cifras

   Entonces con:   'np'=(mp-1)  operaremos en obtener el resto de dividir:

      3^(np)   mod mp  =  'rt'

   Te lo explico con palabras, el dividendo 3^(np)  dividimos entre (mp) tomando el resto final en 'rt'

   ••• Mi pregunta es el tiempo que con Python llegas a operar está división ... Solo está única división... Y si no fuera mucho pedir, tú criterio de en qué parte del proceso se daría la complejidad.


Saludos Cordiales y Muchas Gracias .......

03 Agosto, 2019, 01:12 pm
Respuesta #49

feriva

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 9,173
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Buenos días, Víctor Luis.

Voy a centrarme más en lo que planteas, no me regañes :)

Sabiendo que mp es primo entonces sólo puede ser

\( 3^{mp-1}\equiv1(mod\, mp)
  \)

por el pequeño teorema.

Si no sabemos si es primo, el Python tarda mucho (no sé porque no ha terminado) para un número tan grande en hallar el resto sin más implementaciones tal cual; si es a eso a lo que te refieres. No obstante, más adelante te digo una cosa sobre esto.

Me he estado documentando sobre el test de Miller-Rabin; ya hace años que preguntaste cosas sobre él varias veces, una de ellas era que hasta dónde había que llegar en los valores de la potencia para terminar el test, otra cosa que preguntaste varias veces era que de qué manera estaba relacionado con la hipótesis de Riemann. Creo que Luis te contestó a algunas cosas de éstas para que pudieras crear el código en Python y, finalmente, adoptaste un código ya hecho que venía en internet y que no entendías muy bien.

Como te digo, me he documentado y, además, he observado o conjeturado una cosa acerca del test de Miller-Rabin que te mencionaré al final; supongo que esto sí te interesará.

Este test nació debido precisamente a los números de Carmichael, como sabrás mejor que yo, los cuales podrían tardar en detectarse casi infinitamente para números muy grandes mediante el pequeño Teorema de Fermat; hasta encontrar una base que no fuera un coprimo con la potencia, como te comentaba en las últimas respuestas.

En este enlace puedes ver que hay números de Carmichael con sólo tres factores bastante grandes, de cuatro o cinco cifras cada uno; como éste, por ejemplo 2199733160881 = 6037 * 12073 * 30181. El enlace lo tienes aquí y viene una lista bastante larga de lso primeros

https://de.wikibooks.org/wiki/Pseudoprimzahlen:_Tabelle_Carmichael-Zahlen

Por otro lado, en este otro enlace de Gaussianos...

https://www.gaussianos.com/los-numeros-de-carmichael/

Puedes ver que se dice que está demostrado que son libres de cuadrados (tal como yo sospechaba) y también se dice que al menos tienen tres factores, nunca son semiprimos, como también imaginaba.

En cuanto al test de Miller, hice un programa a mi modo para probarlo; estuve todo el día, porque en algunos sitios se explica mal el test o de forma incompleta; tuve que mirar varios vídeos (todos en inglés, que no me enteraba casi de nada, me enteraba más que nada por lo que se escribía en la pizarra) y varias páginas hasta que ya vi del todo cómo era.

Mi programa es algo especial, busca los números “m” contenidos en un intervalo (n,2n) tales que estos números son de la forma \( 2n-p
  \), donde “p” es primo y está contenido en (0,n); ya sabes, lo de la conjetura del Goldbach, tendremos \( p+m=2n \).

De esta forma analizo la primalidad de ese tipo de compuestos cuando “p” y “m” son coprimos.

Uso en todo caso base 2 para el test (en el de los resultados no, ahí uso base 2 para Fermat pero al pasar a Miller uso de base "p", el primo compañero de "m" porque probé varias cosas) y, primeramente, lo hago con el test de Fermat; si el resto no es 1, no es primo y no pasa a la rutina donde analiza según el test de Miller (curiosamente, y ésta es la conjetura que te decía, se observa que los “m” compuestos coprimos con “p” tales que “p+m=2n” nunca son números de Carmichael; si esto se demostrara, se podría usar para el test de primalidad; de momento, también se puede usar, pero sin seguridad de si es cierto o no).

Siendo “y” el candidato a primo, la rutina que hago para Miller comienza así

Código: [Seleccionar]

k=0

while m % 2**k == 0:

k=k+1

b = (m)/ (2**(k-1))


Como también sabrás, aquí se está buscando la potencia de 2 tal que \( y-1=2^{k-1}*b
  \); es “k-1” debido a que k se inicia con el valor cero y el bucle devuelve una unidad más grane del que es; pero eso es igual.
Y “b” es un número impar con el que si el resto de \( 2^{b}\equiv r(mod\, y)  \) resulta r=1 ó r=-1 entonces “y” es primo seguro (en este caso es seguro, no simplemente probable).

Ahora vuelvo a tu Mersenne; resulta que, si intentamos aplicar Miller, la potencia de 2 es 1, con lo que el impar “b” sigue siendo un número grandísimo; porque con esto no podríamos ir más deprisa; hay métodos para correr más que hallando las potencias tal cual, pero, no obstante, va a tardar porque el número es enorme. Cuando preguntas “cuánto tarda Python”, no es Python, depende de cómo se programe, porque hay muchas cosas para atajar.
Y usar Lehmer, por lo que he visto y si entiendo bien como va... me parece un método inviable para los Merseenes de hoy en día, quizá en su época serviría para algo; el número correspondiente de la secuencia para esa potencia creo que, lo mismo, no lo podría ni manejar un futuro ordenador cuántico de lo gigantesco que sería; estamos hablando de un número cuyo resultado se va  elevando al cuadrado iterativamente más de 50 millones de veces (se le va quitando 2 al resultado, pero eso poco quita). Eso no es lo que usa el GIMP, como decías o decías creer por ahí; no sé lo que usará, pero un número así es imposible de manejar y lo será durante quizá muchos siglos. Si puede que aprovechen algo del test de Lehmer, pero, vamos, muy modificado tendrá que ser.

Sigamos con Miller.
Después, el programa, si el resto de la congruencia dicha no es 1 ó -1, eleva al cuadrado y comprueba el resto módulo “y”; si es 1, no es primo, y esto con seguridad, si es -1, entonces es probablemente primo.
Acabado este último paso, supongamos que el resto no ha sido 1 ni-1. Se vuelve a elevar al cuadrado y si es 1 ó -1, entonces es primo (es como el primer paso)... y así sigue.

Según he visto en vídeos, parece ser suficiente con que el que bucle corra de 1 hasta “k”; aunque, a partir de la hipótesis de Riemann se demuestra (según he leído y creo entender) que tiene que ser algo mayor; el valor se halla con un simple logaritmo, pero ahora no sé dónde lo vi.

En este spoiler te pongo los resultados que fue arrojando para las parejas “p,m” donde el número a comprobar es “m” (parejas Goldbach o no Goldbach).

Si el número no es primo y lo detecta simplemente con Fermat, lo indica; si detecta que es primo cuando ocurre después, para la rutina de Miller, que el resto es 1 ó -1 (segunda comprobación) pone segunda. Si detecta que es primo para después, al elevar al cuadrado, con el resto -1, entonces pone pri resto -1. Lo mismo para cuando no es primo y entonces pri resto 1; pero esto no aparece nunca en la pantalla porque ya te digo que si “p” y “m” coprimos entonces “m” nunca es Carmichael (para los primeros, que es lo que yo he comprobado) 

En todas las entradas aparece el número “m” y entre corchetes los primos diferentes de los que se compone

Spoiler

python miller.py

pri resto -1 5 [5]
pri segunda 7 [7]
pri segunda 7 [7]
pri segunda 11 [11]
pri segunda 13 [13]
pri resto -1 13 [13]
pri segunda 17 [17]
pri segunda 19 [19]
pri segunda 19 [19]
pri segunda 23 [23]
Fermat; no pri 25 [5]
pri segunda 23 [23]
pri resto -1 29 [29]
pri segunda 31 [31]
pri segunda 31 [31]
Fermat; no pri 35 [5, 7]
pri segunda 37 [37]
pri resto -1 37 [37]
pri resto -1 41 [41]
pri segunda 43 [43]
pri segunda 43 [43]
pri segunda 47 [47]
Fermat; no pri 49 [7]
Fermat; no pri 49 [7]
pri resto -1 53 [53]
Fermat; no pri 55 [5, 11]
pri segunda 53 [53]
pri segunda 59 [59]
pri segunda 61 [61]
pri segunda 61 [61]
Fermat; no pri 65 [5, 13]
pri segunda 67 [67]
pri segunda 67 [67]
pri segunda 71 [71]
pri resto -1 73 [73]
pri resto -1 73 [73]
Fermat; no pri 77 [7, 11]
pri segunda 79 [79]
pri segunda 79 [79]
pri segunda 83 [83]
Fermat; no pri 85 [5, 17]
pri segunda 83 [83]
pri resto -1 89 [89]
Fermat; no pri 91 [7, 13]
Fermat; no pri 91 [7, 13]
Fermat; no pri 95 [5, 19]
pri segunda 97 [97]
pri resto -1 97 [97]
pri resto -1 101 [101]
pri segunda 103 [103]
pri segunda 103 [103]
pri segunda 107 [107]
pri segunda 109 [109]
pri segunda 109 [109]
pri segunda 113 [113]
Fermat; no pri 115 [5, 23]
pri segunda 113 [113]
Fermat; no pri 119 [7, 17]
Fermat; no pri 121 [11]
Fermat; no pri 121 [11]
Fermat; no pri 125 [5]
pri segunda 127 [127]
pri segunda 127 [127]
pri segunda 131 [131]
Fermat; no pri 133 [7, 19]
Fermat; no pri 133 [7, 19]
pri resto -1 137 [137]
pri segunda 139 [139]
pri segunda 139 [139]
Fermat; no pri 143 [11, 13]
Fermat; no pri 145 [5, 29]
Fermat; no pri 143 [11, 13]
pri resto -1 149 [149]
pri segunda 151 [151]
pri segunda 151 [151]
Fermat; no pri 155 [5, 31]
pri segunda 157 [157]
pri resto -1 157 [157]
Fermat; no pri 161 [7, 23]
pri segunda 163 [163]
pri segunda 163 [163]
pri segunda 167 [167]
Fermat; no pri 169 [13]
Fermat; no pri 169 [13]
pri resto -1 173 [173]
Fermat; no pri 175 [5, 7]
pri resto -1 173 [173]
pri segunda 179 [179]
pri segunda 181 [181]
pri segunda 181 [181]
Fermat; no pri 185 [5, 37]
Fermat; no pri 187 [11, 17]
Fermat; no pri 187 [11, 17]
pri segunda 191 [191]
pri segunda 193 [193]
pri segunda 193 [193]
pri resto -1 197 [197]
pri segunda 199 [199]
pri segunda 199 [199]
Fermat; no pri 203 [7, 29]
Fermat; no pri 205 [5, 41]
pri segunda 199 [199]
Fermat; no pri 209 [11, 19]
pri segunda 211 [211]
pri segunda 211 [211]
Fermat; no pri 215 [5, 43]
Fermat; no pri 217 [7, 31]
Fermat; no pri 217 [7, 31]
Fermat; no pri 221 [13, 17]
pri segunda 223 [223]
pri segunda 223 [223]
pri segunda 227 [227]
pri segunda 229 [229]
pri segunda 229 [229]
pri resto -1 233 [233]
Fermat; no pri 235 [5, 47]
pri resto -1 233 [233]
pri segunda 239 [239]
pri resto -1 241 [241]
pri resto -1 241 [241]
Fermat; no pri 245 [5, 7]
Fermat; no pri 247 [13, 19]
Fermat; no pri 247 [13, 19]
pri segunda 251 [251]
Fermat; no pri 253 [11, 23]
Fermat; no pri 253 [11, 23]
pri resto -1 257 [257]
Fermat; no pri 259 [7, 37]
Fermat; no pri 259 [7, 37]
pri segunda 263 [263]
Fermat; no pri 265 [5, 53]
pri segunda 263 [263]
pri resto -1 269 [269]
pri segunda 271 [271]
pri segunda 271 [271]
Fermat; no pri 275 [5, 11]
pri segunda 277 [277]
pri resto -1 277 [277]
pri resto -1 281 [281]
pri segunda 283 [283]
pri segunda 283 [283]
Fermat; no pri 287 [7, 41]
Fermat; no pri 289 [17]
Fermat; no pri 289 [17]
pri resto -1 293 [293]
Fermat; no pri 295 [5, 59]
pri resto -1 293 [293]
Fermat; no pri 299 [13, 23]
Fermat; no pri 301 [7, 43]
Fermat; no pri 301 [7, 43]
Fermat; no pri 305 [5, 61]
pri segunda 307 [307]
pri segunda 307 [307]
pri segunda 311 [311]
pri segunda 313 [313]
pri resto -1 313 [313]
pri resto -1 317 [317]
Fermat; no pri 319 [11, 29]
Fermat; no pri 319 [11, 29]
Fermat; no pri 323 [17, 19]
Fermat; no pri 325 [5, 13]
Fermat; no pri 323 [17, 19]
Fermat; no pri 329 [7, 47]
pri segunda 331 [331]
pri segunda 331 [331]
Fermat; no pri 335 [5, 67]
pri resto -1 337 [337]
pri segunda 337 [337]
Fermat; no pri 339 [3, 113]
Fermat; no pri 343 [7]
Fermat; no pri 343 [7]
pri segunda 347 [347]
pri segunda 349 [349]
pri segunda 349 [349]
pri resto -1 353 [353]
Fermat; no pri 355 [5, 71]
pri resto -1 353 [353]
pri segunda 359 [359]
Fermat; no pri 361 [19]
Fermat; no pri 361 [19]
Fermat; no pri 365 [5, 73]
pri segunda 367 [367]
pri segunda 367 [367]
Fermat; no pri 371 [7, 53]
pri segunda 373 [373]
pri resto -1 373 [373]
Fermat; no pri 377 [13, 29]
pri segunda 379 [379]
pri segunda 379 [379]
pri segunda 383 [383]
Fermat; no pri 385 [5, 7, 11]
pri segunda 383 [383]
pri resto -1 389 [389]
Fermat; no pri 391 [17, 23]
Fermat; no pri 391 [17, 23]
Fermat; no pri 395 [5, 79]
pri segunda 397 [397]
pri resto -1 397 [397]
pri segunda 401 [401]
Fermat; no pri 403 [13, 31]
Fermat; no pri 403 [13, 31]
Fermat; no pri 407 [11, 37]
pri resto -1 409 [409]
pri segunda 409 [409]
Fermat; no pri 413 [7, 59]
Fermat; no pri 415 [5, 83]
pri resto -1 409 [409]
pri segunda 419 [419]
pri segunda 421 [421]
pri segunda 421 [421]
Fermat; no pri 425 [5, 17]
Fermat; no pri 427 [7, 61]
Fermat; no pri 427 [7, 61]
pri segunda 431 [431]
pri segunda 433 [433]
pri segunda 433 [433]
Fermat; no pri 437 [19, 23]
pri segunda 439 [439]
pri segunda 439 [439]
pri segunda 443 [443]
Fermat; no pri 445 [5, 89]
pri segunda 443 [443]
pri segunda 449 [449]
Fermat; no pri 451 [11, 41]
Fermat; no pri 451 [11, 41]
Fermat; no pri 455 [5, 7, 13]
pri resto -1 457 [457]
pri resto -1 457 [457]
pri resto -1 461 [461]
pri segunda 463 [463]
pri segunda 463 [463]
pri segunda 467 [467]
Fermat; no pri 469 [7, 67]
Fermat; no pri 469 [7, 67]
Fermat; no pri 473 [11, 43]
Fermat; no pri 475 [5, 19]
Fermat; no pri 473 [11, 43]
pri segunda 479 [479]
Fermat; no pri 481 [13, 37]
Fermat; no pri 481 [13, 37]
Fermat; no pri 485 [5, 97]
pri segunda 487 [487]
pri segunda 487 [487]
pri segunda 491 [491]
Fermat; no pri 493 [17, 29]
Fermat; no pri 493 [17, 29]
Fermat; no pri 497 [7, 71]
pri segunda 499 [499]
pri segunda 499 [499]
pri segunda 503 [503]
Fermat; no pri 505 [5, 101]
pri segunda 503 [503]
pri resto -1 509 [509]
Fermat; no pri 511 [7, 73]
Fermat; no pri 511 [7, 73]
Fermat; no pri 515 [5, 103]
Fermat; no pri 517 [11, 47]
Fermat; no pri 517 [11, 47]
pri resto -1 521 [521]
pri segunda 523 [523]
pri segunda 523 [523]
Fermat; no pri 527 [17, 31]
Fermat; no pri 529 [23]
Fermat; no pri 529 [23]
Fermat; no pri 533 [13, 41]
Fermat; no pri 535 [5, 107]
Fermat; no pri 533 [13, 41]
Fermat; no pri 539 [7, 11]
pri segunda 541 [541]
pri segunda 541 [541]
Fermat; no pri 545 [5, 109]
pri segunda 547 [547]
pri segunda 547 [547]
Fermat; no pri 551 [19, 29]
Fermat; no pri 553 [7, 79]
Fermat; no pri 553 [7, 79]
pri resto -1 557 [557]
Fermat; no pri 559 [13, 43]
Fermat; no pri 559 [13, 43]
pri segunda 563 [563]
Fermat; no pri 565 [5, 113]
pri segunda 563 [563]
pri resto -1 569 [569]
pri segunda 571 [571]
pri segunda 571 [571]
Fermat; no pri 575 [5, 23]
pri segunda 577 [577]
pri segunda 577 [577]
Fermat; no pri 581 [7, 83]
Fermat; no pri 583 [11, 53]
Fermat; no pri 583 [11, 53]
pri segunda 587 [587]
Fermat; no pri 589 [19, 31]
Fermat; no pri 589 [19, 31]
pri segunda 593 [593]
Fermat; no pri 595 [5, 7, 17]
pri segunda 593 [593]
pri segunda 599 [599]
pri segunda 601 [601]
pri resto -1 601 [601]
Fermat; no pri 605 [5, 11]
pri segunda 607 [607]
pri segunda 607 [607]
Fermat; no pri 611 [13, 47]
pri segunda 613 [613]
pri resto -1 613 [613]
pri resto -1 617 [617]
pri segunda 619 [619]
pri segunda 619 [619]
Fermat; no pri 623 [7, 89]
Fermat; no pri 625 [5]
pri segunda 619 [619]
Fermat; no pri 629 [17, 37]
pri segunda 631 [631]
pri segunda 631 [631]
Fermat; no pri 635 [5, 127]
Fermat; no pri 637 [7, 13]
Fermat; no pri 637 [7, 13]
pri segunda 641 [641]
pri segunda 643 [643]
pri segunda 643 [643]
pri segunda 647 [647]
Fermat; no pri 649 [11, 59]
Fermat; no pri 649 [11, 59]
pri resto -1 653 [653]
Fermat; no pri 655 [5, 131]
pri segunda 653 [653]
pri segunda 659 [659]
pri segunda 661 [661]
pri segunda 661 [661]
Fermat; no pri 665 [5, 7, 19]
Fermat; no pri 667 [23, 29]
Fermat; no pri 667 [23, 29]
Fermat; no pri 671 [11, 61]
pri resto -1 673 [673]
pri resto -1 673 [673]
pri resto -1 677 [677]
Fermat; no pri 679 [7, 97]
Fermat; no pri 679 [7, 97]
pri segunda 683 [683]
Fermat; no pri 685 [5, 137]
pri segunda 683 [683]
Fermat; no pri 689 [13, 53]
pri segunda 691 [691]
pri segunda 691 [691]
Fermat; no pri 695 [5, 139]
Fermat; no pri 697 [17, 41]
Fermat; no pri 697 [17, 41]
pri resto -1 701 [701]
Fermat; no pri 703 [19, 37]
Fermat; no pri 703 [19, 37]
Fermat; no pri 707 [7, 101]
pri segunda 709 [709]
pri segunda 709 [709]
Fermat; no pri 713 [23, 31]
Fermat; no pri 715 [5, 11, 13]
Fermat; no pri 713 [23, 31]
pri segunda 719 [719]
Fermat; no pri 721 [7, 103]
Fermat; no pri 721 [7, 103]
Fermat; no pri 725 [5, 29]
pri segunda 727 [727]
pri segunda 727 [727]
Fermat; no pri 731 [17, 43]
pri segunda 733 [733]
pri resto -1 733 [733]
Fermat; no pri 737 [11, 67]
pri segunda 739 [739]
pri segunda 739 [739]
pri segunda 743 [743]
Fermat; no pri 745 [5, 149]
pri segunda 743 [743]
Fermat; no pri 749 [7, 107]
pri segunda 751 [751]
pri segunda 751 [751]
Fermat; no pri 755 [5, 151]
pri segunda 757 [757]
pri resto -1 757 [757]
pri resto -1 761 [761]
Fermat; no pri 763 [7, 109]
Fermat; no pri 763 [7, 109]
Fermat; no pri 767 [13, 59]
pri segunda 769 [769]
pri segunda 769 [769]
pri resto -1 773 [773]
Fermat; no pri 775 [5, 31]
pri resto -1 773 [773]
Fermat; no pri 779 [19, 41]
Fermat; no pri 781 [11, 71]
Fermat; no pri 781 [11, 71]
Fermat; no pri 785 [5, 157]
pri segunda 787 [787]
pri segunda 787 [787]
Fermat; no pri 791 [7, 113]
Fermat; no pri 793 [13, 61]
Fermat; no pri 793 [13, 61]


[cerrar]

Saludos.