[Richard R Richard]

   


De nuevo con las condiciones del teorema citado


Si $$\operatorname{mcd}{(a^{(N-1)/p} - 1, N)}= 1$$  esto significa que tengo que hacer el mcd de los valores separados por comas, ok, uno es $$a^{(N-1)/p} - 1$$  y el otro es $$N$$? ¿Ehhhh?¿Pero cómo es esto posible? , si yo puedo conocer todos los divisores de $$N$$ para calcular su mcd con cualquier otro número con que lo testee, entonces  yo ya sabría de antemano si $$N$$ es primo o no, me pregunto ¿cómo esto va a ser la base para analizar la primalidad de $$N$$? , estoy medio loco o ya no sé que pensar  ...

Dado $$N$$, si se pueden encontrar $$p$$ y $$a$$ que satisfagan las condiciones del teorema, entonces $$N$$ es primo. 

Para eso tengo que satisfacer  la condición (3) que es la antes mencionada , hacer un mcd con $$N$$ , que si  ese resultado lo tuviera ya sabría que es $$N$$ primo o no .... evidentemente algo me pierdo... me suena a chiste, pero no debe serlo.

Gracias, por un aliento para continuar.

[Juan Pablo Sancho]

https://es.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm
Editado
https://foro.rinconmatematico.com/index.php?topic=114473.msg453611#msg453611

[Richard R Richard]

https://es.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm
Editado
https://foro.rinconmatematico.com/index.php?topic=114473.msg453611#msg453611

Con el primer link me dejaste boquiabierto (no sabía ni de su existencia, y si es de la época de Euclides....que mas decir) y con el segundo maravillado...


Veamos
Sigo la idea del algoritmo de Pocklington  la condición uno exige buscar un numero $$a$$  que cumpla $$a^{N-1}\equiv 1 \mod N$$  entonces se me ocurre buscar $$a$$ como

$$a=\sqrt[N-1]{Nx+1}$$  donde $$x$$ es un entero .... Si $$N$$ es un número de $$k$$ cifras donde $$k$$ no es muy pequeño , no veo fácil  hacer alguna  iteración aumentado $$x$$ y pues  averiguar la raíz enésima menos 1 para hallar $$a$$ y que resulte entero sería toda una casualidad...  Pero existir debe existir solo pide que confiemos existe eso se pide como hipótesis.

La condición 2   entiendo dice que debe existir un $$y$$ tal que con un primo $$p_y$$  cumple que $$p_y\cdot y=N-1$$    (que fácil sería saber lo mismo para otro primo $$p_z\cdot z=N$$ y listo, no? $$N$$ es compuesto y a otra cosa)  , pero de movida sabemos $$N-1$$ es par por lo que $$p=2$$... esto no cumple $$p>\sqrt N - 1$$ debería buscar otro primo que lo cumpla... pero que me queda la duda con casos como $$N=257$$ pues $$N-1 =256 =2^8 $$ sería el  $$2$$ el único primo divisor y no hay ninguno mayor a $$\sqrt {257} -1\cong 15$$ para cumplir la condición.

Sobre la condición 3 ahora la veo mas clara que no necesito tener todos los divisores de $$N$$ para conocer el $$mcd(A,N)$$ mas si como explican $$A>N$$   

Piden $$mcd(a^{\frac{N-1}{p}}-1\ ,\ N)$$  o sea  $$mcd(\left(\sqrt[N-1]{Nx+1}\right)^{\frac{N-1}{p}}-1\ ,\ N)$$ que es lo mismo que $$mcd(\sqrt[p]{Nx+1}-1\ ,\ N)$$ si la vista no falla.
No sé a qué va esto pero quiero entender el fondo de la  cuestión  con el teorema.

Y que  el número de iteraciones del algoritmo de Euclides sea menor a $$n<5k$$ no creo que tarde mucho, solo depende del algoritmo divisor y calculador de restos, es un dato esperanzador , pues lo supongo muy rápido antes de programarlo.   

Todavía no entiendo cómo hallar $$a$$, $$p$$ o mi supuesta  $$x$$ tan fácilmente....

Yo creo que esto va en deducir un primo $$p$$ con esas propiedades( si existe), para hallar un $$a$$ y entonces  decir algo sobre si $$N$$ es primo o no...  lo que me lleva a dudar de la eficacia que es lo que ando buscando 100%

Me lo voy a mirar con mucha mas calma pues no veo un algoritmo fácilmente programable.

[illanlop]

Hola!! Si te interesa el tema estoy haciendo una web en la que propongo un método de cribado que va más allá del de Eratóstenes. También contiene una clasificación de los números enteros, incluyendo compuestos que podrían ser primos pero no lo son. Establezco también patrones entre tales números compuestos y un proceso de factorización.

https://factoranumber.com/

Un saludo 😊

[Richard R Richard]

Hola!! Si te interesa el tema estoy haciendo una web en la que propongo un método de cribado que va más allá del de Eratóstenes. También contiene una clasificación de los números enteros, incluyendo compuestos que podrían ser primos pero no lo son. Establezco también patrones entre tales números compuestos y un proceso de factorización.

https://factoranumber.com/

Un saludo 😊

Hola, sí, ya pasé por el sitio que propones, vi que es prolijo, amigable,  rápido  y fiable para números bajos, si bien  siempre  habrá números más grandes que cualquiera  con los que se trabaja, ¿has probado  tu teoría de los compuestos más allá  de los 16 dígitos?, pues cada vez más $$6k\pm1$$ se vuelven compuestos periodicamente.
Fíjate que cualquier software producido por aventureros improvisados medios  programadores matemáticos como yo manejamos hasta miles de dígitos en pocas líneas de comando, allí  se verá  la potencia  de un método,  si lo que buscas es dar una explicación teórico práctica, está  excelente  muy bien  lograda.

[illanlop]

Buenos días,

Gracias por tu amable respuesta. He probado más allá de 16 dígitos pero me topo con una limitación de JavaScript, ya que a partir de entonces maneja los números de otra manera y afecta a los resultados. Sé que afectaría al tiempo de cálculo con números más grandes para los casos de \( 6x\pm 1 \). He probado a usar librerías para manejar números mayores y ajustar el código a la librería pero no me convenció el resultado. Cuando recopile algo de feedback plantearé el método con números mayores 🙂