Autor Tema: Criterios sobre lo que es primalidad

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

28 Mayo, 2020, 12:07 pm
Leído 755 veces

Víctor Luis

  • Héroe
  • Mensajes: 1,164
  • País: bo
  • Karma: +0/-0
  • Sexo: Masculino
Buenas a Todos ...

   * Descartando ó dejando de lado el criterio de "Divisibilidad" ... Qué otros criterios mas tenemos, o se tiene, para dar a entender y/o comprender, lo que es PRIMALIDAD?

Saludos Cordiales ...


(me doy un tiempo mas, para compartir con este magnifico Foro, los criterios empiricos que quiero compartir)

28 Mayo, 2020, 04:03 pm
Respuesta #1

feriva

  • Matemático
  • Mensajes: 9,076
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
  • No soy matemático, eso es una etiqueta.
Buenas a Todos ...

   * Descartando ó dejando de lado el criterio de "Divisibilidad" ... Qué otros criterios mas tenemos, o se tiene, para dar a entender y/o comprender, lo que es PRIMALIDAD?

Saludos Cordiales ...


(me doy un tiempo mas, para compartir con este magnifico Foro, los criterios empiricos que quiero compartir)

Hombre, Víctor Luis, muy buenas; me alegro, como siempre, de verte.

Pues la palabra “primalidad” por lo que yo tengo visto va asociada siempre o casi siempre a los test para saber si un número es o no primo.

Un cordial saludo.

29 Mayo, 2020, 08:56 am
Respuesta #2

Víctor Luis

  • Héroe
  • Mensajes: 1,164
  • País: bo
  • Karma: +0/-0
  • Sexo: Masculino
Buenas Feriva ....

  Un gustazo mi Amigo y Maestro, ya estaba a punto de tirar la tohalla, por lo estresante que es el mundo 'logico'. Ya con casi un año de haber dejado la matematica, por las razones personales que te hube comentado, sucede que me deje llevar por un nuevo analisis, donde inconcientemente conforme un nuevo conjunto, deneminado VM

VM=(5,7,11,13,17,19,23,25)

  Desde cada termino se conforma una sucesion simple ó grupo 'GP()' generandose sus terminos con una misma constante \( K=24 \)

  Siguiendo la idea intuitiva, tome el grupo:

\( GP(5)=(5,29,53,77,101, ...) \)

** METODO ET4 **
(de primalidad)

  Recordemos que denominamos \( nb \) a los terminos de cada grupo GP, de tal manera que el procedimiento de la metodologia nos dice operar:

\( g=\dfrac{nb-1} {4} \)

\( h=(g+1) \)

  Determinamos los restos:

\( r1= 2^{g}  \  mod  \  nb \)
\( r2= 2^{h}  \  mod  \  nb \)

  Luego:

\( n1= (nb-r1) \)
\( n2= (n1*r2) \)

  Y por ultimo:

\( rt= n2  \  mod  \  nb \)

 EVALUACION:

  El criterio de primalidad nos dice que si se cumple que  \( rt=2 \) entonces \( nb \) es Primo, caso contrario es Compuesto.

  Veamos un ejemplo:

(disculpen si no pongo todo en latex)

nb=(29)

siendo:   g=(7)   h=(8)

operamos:
\( 2^{7} \) mod 29= 12
\( 2^{8} \) mod 29= 24

ahora:
n1 = (29 - 12) = 17
n2 = (17 * 24) = 408

por ultimo:

rt = 408 mod 29 = (2) PRIMO

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

*) He comprobado esto hasta el rango de (500) en los 'nb' del grupo GP(5) cumpliendose en los que son primos.
  He evaluado en algunos de los primeros compuestos, y tambien se cumple.

*) Feriva, no tengo computador, por lo que mis evaluaciones fueron de forma manual.
   Si puedes, te pediria que hagas un programa en Python, para que vaya comprobando este criterio y nos reporte:

  > Los primos que no cumplen con el criterio de evaluacion (esperando no se de ninguno)

  > Los compuestos que cumplen con el criterio de evaluacion y pasan por pseudoprimos (es razonable que se den algunos, en cuyo caso seria util saber la "cantidad" de estos en cada intervalo de millon, para saber si la cantidad es proporcionalmente constante ó tiende a disminuir.)

*) Algo medio parecido, pero mas simple, es la PEM (Primalidad Estructural para Mersenne) donde obtenemos un 'rt' con un solo proceso operacional, pero en la evaluacion, no esperamos nos de un valor natural constante como en este caso (2)
  Sino, se verifica que 'rt' pertenezca a uno de los elementos naturales de un conjunto en particular, al que denomine como 'cm={ }'
  Un otro detalle, es que el 'rt' de cada Mp primo de Mersenne, es unico, sin haber dos que se repitan.
  Y lo mejor, es que la PEM es "Determinista".


Saludos Cordiales ....

29 Mayo, 2020, 11:52 am
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,047
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola

** METODO ET4 **
(de primalidad)

  Recordemos que denominamos \( nb \) a los terminos de cada grupo GP, de tal manera que el procedimiento de la metodologia nos dice operar:

\( g=\dfrac{nb-1} {4} \)

\( h=(g+1) \)

  Determinamos los restos:

\( r1= 2^{g}  \  mod  \  nb \)
\( r2= 2^{h}  \  mod  \  nb \)

  Luego:

\( n1= (nb-r1) \)
\( n2= (n1*r2) \)

  Y por ultimo:

\( rt= n2  \  mod  \  nb \)

Dado que trabajando módulo \( nb \) se tiene que: \( n1= (nb-r1)=-r1 \). Entonces (módulo \( nb \)):

\( n2=n1\cdot r2=-r1\cdot r2=-2^{g+h}=-2^{2g+1}=-2^{(nb+1)/2} \)

De forma que directamente:

\( rt=-2^{(nb+1)/2}\quad mod\quad nb \)

Es un test tipo Miller-Rabin.

En el grupo en que lo estás comprobando \( GP(5) \) falla por primera vez para \( 1678541=5+69939\cdot 24 \), que tu test da como primo, pero en realidad es compuesto.

Saludos.

29 Mayo, 2020, 12:49 pm
Respuesta #4

feriva

  • Matemático
  • Mensajes: 9,076
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
  • No soy matemático, eso es una etiqueta.
Buenas Feriva ....


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

Me iba a poner a probarlo ahora, pero como Luis ya lo ha mirado, pues espero a ver si quieres otra comprobación.

Ya la última vez que hablamos, creo, probé un programa que hice a partir del test de Rabin (¿te acuerdas?) pero lo tengo olvidado, tendré que repasar.

Spoiler
Si en algún momento ves que no contesto algo, es porque se me ha caído un trozo de techo recientemente (todos los años se me cae un trozo, pero este año ha sido un poco más grande) y tendrán que venir a hacer alguna chapuza y será un lío con tanto trasto, porque esta casa es un ruina y un desastre de todo. Te lo digo para que no pienses que es que no me apetece o que es el covid-19 (antes que eso es más probable que me caiga un trozo de escayola de punta en el pecho y me mate como a Drácula). En cualquier caso pienso que hasta dentro de dos semanas aproximadamente no vendrán, pero no sé... prefiero decírtelo ya por si se me olvida o después no puedo.


[cerrar]

Un cordial saludo.

29 Mayo, 2020, 03:49 pm
Respuesta #5

Víctor Luis

  • Héroe
  • Mensajes: 1,164
  • País: bo
  • Karma: +0/-0
  • Sexo: Masculino
Buenas Feriva y Luis ...

*) Agradezco su colaboracion, ... como habia dicho, esperaba se den compuestos que pasen por primos.
   Lo que mas me interesaria saber, es si ALGUN PRIMO no cumple con la evaluacion.

*) Ahora si es un metodo tipo Miller-Rabin, ... Sera tambien probabilistico? y quizas un tanto mejor?

Saludos Cordiales ...

29 Mayo, 2020, 07:55 pm
Respuesta #6

feriva

  • Matemático
  • Mensajes: 9,076
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
  • No soy matemático, eso es una etiqueta.
Buenas Feriva y Luis ...

*) Agradezco su colaboracion, ... como habia dicho, esperaba se den compuestos que pasen por primos.
   Lo que mas me interesaria saber, es si ALGUN PRIMO no cumple con la evaluacion.

*) Ahora si es un metodo tipo Miller-Rabin, ... Sera tambien probabilistico? y quizas un tanto mejor?

Saludos Cordiales ...

Parece que para \( GP(5) \), \( GP(11) \)  y \( GP(13) \)  no falla, o sea, los primos dan rt=2 (parece, digo, habría que probar más o demostrarlo) pero para \( GP(7) \) sí falla.

Por otro lado, entiendo que no es determinista desde el momento que un compuesto puede pasar por primo; a no ser que tengas un segundo apartado de comprobación para eliminar esos compuestos.

Un saludo cordial.

30 Mayo, 2020, 12:03 pm
Respuesta #7

Víctor Luis

  • Héroe
  • Mensajes: 1,164
  • País: bo
  • Karma: +0/-0
  • Sexo: Masculino
Buenas Feriva y Luis ....

*) Tienes razon Feriva en que el metodo no es determinista y es que no vamos todavia a ello... un poco de paciencia por favor.

   Respecto a tu observacion, en los grupos:
  GP  (7)  (11)  (19)  (23)

   No se puede aplicar el metodo, ya que sus \( nb - 1 \) no son divisibles entre 4.

   Por otra parte, en GP(17) y GP(25) el procedimiento varia, donde luego de operar y obtener 'r1' y 'r2' realizamos:

\( n1 = r1 * r2 \)
\( rt = n1  \  mod  \  nb \)

   No he realizado una amplia comprobacion, solo en un par de los primeros primos. Tambien esperaremos que se den compuestos que pasen por primos, al dar un resultado  'rt=2'

*) En fin, lo relevante, es que en \( g \) tenemos un "Punto Estructural" el cual valoramos y obtenemos su resultado en \( r1 \)

   Comprendamos solo hasta esto, que siendo \( nb \) un natural, con la 'valoracion' de uno de sus 'puntos estructurales', podemos llegar a saber y/o determinar su estado de primalidad ... Sin llegar a decir que el metodo expuesto sea de caracter determinista.

   > Disculpenme, pero en lugar de 'g' diremos que \( pt \) es ese punto estructural, que desde su valoracion, podemos llegar a determinar el estado de primalidad del natural en cuestion.

   Podran cuestionar y que pasa con 'h' ... Nada, es solo otro punto estructural ... Pero en general, solo necesitamos valorar un 'pt' punto estructural para determinar la primalidad de los posibles naturales a ser primos.

*) Luis nos dijo que el metodo expuesto, es de 'tipo' Miller-Rabin y es que me pregunto, como le habran echo para ajustar su metodologia, ya que estamos viendo, que no tenemos un mismo proceso operacional que se aplique para todo natural 'nb', bueno, quizas se centraron en evaluar a todos los naturales, sean pares e impares, ... lo que considero es tan solo, para ganar aceptacion, observacion que tambien le hice a Fermat respecto a su pequeño teorema, donde:

\( pt = nb - 1 \)
\( rt = 2^{pt}  \  mod  \  nb \)

   Siendo 'rt=1'  esto cumplen todos los primos y tambien muchos compuestos.

   Pero con solo valorar y evaluar:
   \( pt = nb - 1 \)
   No es suficiente y aun asi, lo aplican Miller-Rabin, queriendo salvar su metodologia con otros ajustes, como el operar con otras bases, es decir:

\( rt = a^{pt}  \  mod  \  nb \)

   Se dice que la cantidad de bases 'a' con las que evaluar, se incrementaria algo asi en proporcion al tamaño del natural que se pretende determinar su estado de primalidad, ... Por lo que supongo es por esto, que no se emplea en confirmar la primalidad de los ultimos Mp primos de Mersenne, ... podria ser asi?

*) Resumiendo, sabiendo el 'pt' punto estructural a valorar, como valorarlo hasta obtener 'rt' aplicaremos un criterio de 'evaluacion' para determinar su 'estado de primalidad'.

   En mi criterio, la Primalidad se la puede comprender y determinar, desde la exploracion y comprension de la Estructura Numerica de naturales con posibilidad de ser primos.

   Para poder validar lo anterior, es decir el excluir a naturales, sin posibilidad de ser primos, me apoyo en lo que denomino como Factorizacion Estructural, que podremos verlo mas luego, y que desde su analisis y comprension, se explicaria, comprenderia y concebiria la "Distribucion de los Numeros Primos" ... El objetivo final al que quisiera llegar.

(correcciones por favor... )


Saludos Cordiales ....

30 Mayo, 2020, 03:36 pm
Respuesta #8

feriva

  • Matemático
  • Mensajes: 9,076
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
  • No soy matemático, eso es una etiqueta.


   Para poder validar lo anterior, es decir el excluir a naturales, sin posibilidad de ser primos, me apoyo en lo que denomino como Factorizacion Estructural, que podremos verlo mas luego, y que desde su analisis y comprension, se explicaria, comprenderia y concebiria la "Distribucion de los Numeros Primos" ... El objetivo final al que quisiera llegar.

(correcciones por favor... )


No tengo ahora la cabeza mucho para corregir, Víctor Luis. Lo importante es que funcione y que sea práctico; creo que Luis lo valorará mucho mejor que yo.

Una cosa aparte, ¿no te has decido aún a arreglar el ordenador? Si fuera caro el arreglo, siempre puedes conseguir uno con un mircoprocesador de arquitectura un poco más antigua que la que se usa ahora; el que yo tengo es así, aunque me regalaron uno moderno, no lo instalo por pereza,, porque hay que reinstalar todo. Si tienes bien el teclado, el monitor, ratón... una CPU de segunda mano como la que te digo te podría salir muy barata o incluso podrías encontrar a alguien que te la regalara.

Es que tengo en mente un “juego” para entretenernos este verano, factorizando números (algo lúdico, por pasar el rato y divertirnos, no pretendiendo factorizar ningún RSA, que no podemos) pero si no tienes ordenador... no podrá ser.

Un cordial saludo.

31 Mayo, 2020, 01:07 am
Respuesta #9

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,272
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Un número entero positivo N se dice irreducible,
  si toda factorización N = A . B, con A, B, enteros positivos,
  implica que A = 1 ó B = 1.

Un número entero positivo N se dice primo,
  si para todo par de enteros positivos X, Y,
  tales que N | X . Y (o sea, N divide al producto X . Y),
  implica que N | X ó N | Y (o sea, N divide a X o bien N divide a Y).

Se puede demostrar que todo número primo es también irreducible.

En el caso de los enteros positivos (o también los enteros en general),
se puede demostrar que todo irreducible es también primo.

Pero hay estructuras algebraicas en las que no es equivalente ser primo que ser irreducible.

Por lo tanto, ahí tendrías una definición alternativa de número primo,
la de ser irreducible,
que aunque es equivalente para números enteros,
no lo es en otros contextos.

Por ejemplo, en el conjunto

  \(R = \{a+ i b \sqrt 5 : a,b\in\mathbb Z\}\),

se puede hablar de los conceptos de divisibilidad, primalidad e irreducibilidad.

Sólo que ahora, la condición A = 1 ó B = 1 de la irreducibilidad se cambia por |A| = 1 ó |B| = 1
(o sea, el valor absoluto o norma de A o de B es 1).

Por ejemplo, el número 3 sería irreducible pero no primo.
En este caso, 3 divide a \(9 = (2 + i \sqrt{5}).(2-i\sqrt{5})\),
pero no divide a ninguno de los factores del producto.



31 Mayo, 2020, 09:30 am
Respuesta #10

feriva

  • Matemático
  • Mensajes: 9,076
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
  • No soy matemático, eso es una etiqueta.
Un número entero positivo N se dice irreducible,
  si toda factorización N = A . B, con A, B, enteros positivos,
  implica que A = 1 ó B = 1....


Hola, Argentinator. Esto que dices (si no me equivoco) creo que lo querías haber puesto en este otro hilo:

https://foro.ealaipi.com/index.php?topic=113404.msg447777#msg447777

Saludos.



31 Mayo, 2020, 08:15 pm
Respuesta #11

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,272
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Hola feriva.

Contesto al post inicial de Victor Luis, que decía esto:

Buenas a Todos ...

   * Descartando ó dejando de lado el criterio de "Divisibilidad" ... Qué otros criterios mas tenemos, o se tiene, para dar a entender y/o comprender, lo que es PRIMALIDAD?



31 Mayo, 2020, 11:15 pm
Respuesta #12

feriva

  • Matemático
  • Mensajes: 9,076
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
  • No soy matemático, eso es una etiqueta.
Hola feriva.

Contesto al post inicial de Victor Luis, que decía esto:

Buenas a Todos ...

   * Descartando ó dejando de lado el criterio de "Divisibilidad" ... Qué otros criterios mas tenemos, o se tiene, para dar a entender y/o comprender, lo que es PRIMALIDAD?


Ah, bien, entonces nada...

no leas esto Víctor Luis

...sólo que como empiece a discutir la definición de primo vas a tener debate para un mes o dos  :)

[cerrar]

Saludos.

06 Junio, 2020, 11:54 am
Respuesta #13

Víctor Luis

  • Héroe
  • Mensajes: 1,164
  • País: bo
  • Karma: +0/-0
  • Sexo: Masculino
Buenas Feriva, Luis y Argen... ....

   *** El objetivo en este hilo, no es entrar en 'debate', creo que eso ya lo hicimos anteriormente... simple debate, ustedes con sus criterios literarios, que por supuesto ahora comprendo (lo suficiente) habiendo verdad y validacion, en base a las demostraciones matematicas, que a sus 'axiomas' he criticado. Y es que es suficiente un axioma falso o medio falso, para propagar camufladamente (invisiblemente) una falsedad que de apoco, llegue a contaminar criterios posteriores, que se basen en dicho axioma y derivados de este.

   En esta entrada, (respuesta ó publicacion en el hilo) busco se me entienda, el criterio que tan solo 'concebi' de lo que considero es primalidad, mas alla del dado desde una simple definicion, donde si n(5) no es divisible entre los naturales mayores a (1) que le anteceden, consideramos es  p(5) primo, algo evidente, pero: ¿Esta indivisibilidad es primalidad? ... ¿Nos ha sido suficiente para comprender y dar a entender sobre como es que se da la distribucion de numeros primos?

Spoiler
  FERIVA... disculpa por mi demora en responder(les) ... Y es que sucede, que no estaba bien de salud, fue una semana estresante, donde por decirlo asi, evalue a mi hijo, agradeciendo al creador.

   Sobre mi computador, ... antes de la pandemia, lo hice revisar y el diagnostico fue daño del BIOS, por lo que era cambiar toda la placa o comprar otra compu, y ahi quede por la cuarentena del coronavirus (el cual es un simple parasito de tipo protozoario con estructura pseudo-viral)
[cerrar]

   *) Antes de continuar, les habia pedido sus criticas u observaciones, y como no las hubo, reitero que:

  'pt' .... es un "punto estructural"
  'rt' .... es una variable que contiene la valoracion final de 'pt', con el cual evaluaremos segun algun criterio, para determinar el estado de primalidad del 'nb' natural base.

  'estado de primalidad' .... no es mas que saber si un 'nb' es ó no primo y para esto, empleamos un metodo cuyo resultado se evalua en base a un criterio, para saber si el natural base es primo ó compuesto.

.... Continuare...


Saludos cordiales....

06 Junio, 2020, 02:25 pm
Respuesta #14

Víctor Luis

  • Héroe
  • Mensajes: 1,164
  • País: bo
  • Karma: +0/-0
  • Sexo: Masculino
Buenas mis Amigos ....

   
Spoiler
Es la segunda vez que escribo esta entrada, porque se acabo mi tiempo o algo asi, ... estoy neondertal con la tecnologia celular, .... Aparte de saber, que las potencias, espian nuestras actuales exposiciones.
[cerrar]

*) El 'pt' de Fermat es:

   \( pt = nb-1 \)

   Es uno solo, mientras que Miller-Rabin implementan una funcion, que de acuerdo al tamaño del 'nb' se daran varios y muchos 'pt'.

   Fermat realiza una valoracion:

\( rt = 2^{pt}  \  mod  \  nb \)

  Mientras que Miller-Rabin realizan varias valoraciones, pues implementan una funcion para bases 'a':

\( rt = a^{pt}  \  mod  \  nb \)

...) Si Fermat no llego a dar con el Enfoque Estructural, peor será Miller-Rabin.


** (PEN) Primalidad Estructural para Naturales base.

   Primero, es que valoramos con un solo 'pt' de primalidad:

pt = \( \dfrac {nb-1} {2} \)

   Diferente a Fermat, pero es un solo 'pt' punto estructural. Ahora nuestra valoracion es:

  \( rt = a^{pt}  \  mod  \  nb \)

   Se parece a Miller-Rabin podran decir algunos, pero no es asi, ya que con:

   a = {2, 3}

   Logramos un 98% de resultado determinista (aprox) y con:

   a = {2, 3, 5}

   Logramos un 99,99999% de resultado determinista (algo que les he reiterado muchas veces) ... Donde el asunto no esta en ampliar la cantidad de bases 'a', sino, en conocer de como se distribuyen los 'nb' primos, de acuerdo a su estructura.

   Complementando la metodologia, el criterio de evaluacion es:

   \( rt = 1 \)
ó
   \( rt = nb-1 \)

...) Disculpenme, pero no se precipiten trivialmente en decir:  que el criterio se asemeja al de Miller-Rabin .... Y es que acaso ellos mismos saben, el por qué de (1) ó (nb-1) ???
   Estructuralmente, esto se comprende, en si, se lo observa, algo que quizas nuestros de antes lo obiaron....


Saludos cordiales....

06 Junio, 2020, 04:00 pm
Respuesta #15

Víctor Luis

  • Héroe
  • Mensajes: 1,164
  • País: bo
  • Karma: +0/-0
  • Sexo: Masculino
Buenas ....

**) Con la PEN antes expuesta la metodologia, es que pude realizar, la Coleccion de Primos adjuntado en un hilo del foro, y es que, buscando en la red, numeros primos algo grandes, ... digamos de 1.000 digitos ... Pues no habian a disposicion libre, algo que me servirian para comprobar y/o ajustar la metodologia,... no asi para copiar y publicar como algo mio, como uno alguno en el foro, se atrevio insinuarlo.

   Pues debia ser improbable el conseguir primos de 2.000 digitos e casi imposible el obtener primos de 5.000 digitos, verdad?  Asi era, por lo que me propuse llegar hasta primos (por lo menos hasta uno) de 10.000 digitos .... y asi lo hice, comprobando Luis el ultimo.

   Saben con cuantas valoraciones es que determinamos los primos, a partir de los 2.500 digitos?
   Pues con una sola, con:  a(2)  simplemente, que les parece ... Y es que, encontre contados compuestos, de hasta 12 u 14 digitos, que pasan la evaluacion como primos, llegando en mas adelante a desaparecer (por asi decirlo) ... Recuerdo haberlos denominado como: Pseudoprimos Realmente Validos (prv) .... ¿Cuantos encontrarian ustedes, de mas de 15 digitos? Aplicando la PEN, con las bases: a=(3,5) para simplificarlo?

***) Se muy bien que la PEN no es (aun) determinista, y analizarla, piensen sea algo trivial ... Pero en su tiempo libre, dense la oportunidad de determinar primos 'nb' de: 500, 1.000, 2.000 y 2.500 digitos ... digamos 5 de cada uno, para luego volverlos a evaluar, con: Mathematica u otra metodologia, y luego con la PEN, controlando en cada caso, el tiempo de proceso y la veracidad de su primalidad.

   Busquen luego, (con la PEN) 2 primos de: 5.000, 5.500, 6.000, 7.000 y 7.500 digitos, para luego determinar su primalidad y tiempo de proceso, tanto con la PEN y Mathematica ... En esto, yo logre sacarle unos segundos de ventaja, donde para dar con primos de 10.000 digitos, y al escasear estos, los segundos fueron siendo minutos, algo que deja atras a Mathematica 5.0 si buscamos determinar primos de mas de 16.000 digitos.


Saludos Cordiales ....

06 Junio, 2020, 07:26 pm
Respuesta #16

feriva

  • Matemático
  • Mensajes: 9,076
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
  • No soy matemático, eso es una etiqueta.
Buenos dís, Víctor Luis.

Pero tienes un poco olvidado lo de Fermat (si no soy yo el que me he olvidado). Fermat es más general, no es sólo con 2, es  \( a^{p}\equiv a\,(mod\, p)
  \) para cualquier “a” apropiado.

Y dividendo entre “a” (cosa que se puede hacer sólo si “a” y “p” son coprimos) queda  \( a^{p-1}\equiv1\,(mod\, p)
  \); que es lo que se usa en el test.

Miller-Rabin, según la Wiki, toma un número impar “m” tal que  \( m=\dfrac{n-1}{2^{k}}
  \), donde “n” es el número a probar si es primo o no ( y “k” y “m” son únicos por descomposición; dado que n-1 es par y “m” impar).

Después calcula el resto  \( r_{0}
  \)  tal que \( a^{m}\equiv r_{0}\,(mod\, n)
  \);  donde “a” es una cierta base a elegir.

Luego, analiza si ocurre  \( r_{0}\equiv\pm1\,(mod\, n)
  \); en caso de que así sea, es probable primo.

Si no ocurre, calcula  \( r_{1}
  \) tal que  \( r_{0}^{2}\equiv r_{1}\,(mod\, n)
  \).

Después analiza  \( r_{1}\equiv-1\,(mod\, n)
  \);  y, si esto ocurre, es probable primo.

Si tampoco pasa eso (después de haber probado todo lo anterior) se calcula  \( r_{1}\equiv1\,(mod\, n)
  \)

y si se da esto último, entonces queda descartado como primo con seguridad (en este caso sí es seguro).

Citar

Y es que acaso ellos mismos saben, el por qué de (1) ó (nb-1) ???


Creo que se puede decir que sí y que no, según a qué te refieras. Por lo que tengo entendido, el test de Miller es determinista en caso de que la Hipótesis de Riemann sea cierta; cosa que parece que sí pero aún no se ha podido demostrar. Es decir, Miller sí sabe por qué hace eso, pero no tiene la seguridad en la Hipótesis. Rabin modifica el test y usa un resultado probabilístico que no depende ya de que la Hipótesis esté probada o no. Pero es lo que he leído, no sé decirte bien.

Citar

FERIVA... disculpa por mi demora en responder(les) ... Y es que sucede, que no estaba bien de salud, fue una semana estresante, donde por decirlo asi, evalue a mi hijo, agradeciendo al creador.


Me alegro de que no haya pasado nada y ya estéis bien.

Saludos.

10 Junio, 2020, 12:41 pm
Respuesta #17

Víctor Luis

  • Héroe
  • Mensajes: 1,164
  • País: bo
  • Karma: +0/-0
  • Sexo: Masculino
Buenas Feriva, Luis, Argenti ....

  *) Disculpen mi ignorancia, desde el criterio y punto de vista de ustedes, y es que yo mismo me contradijera e invalidaria, si no fuera por el Enfoque Estructural, donde observamos que si bien Fermat tiene razon con que todos los primos (impares) cumplen con su 'pt', tambien lo hacen muchisimos compuestos, como tambien todos los 'Mn' numeros de Mersenne compuestos, es decir, no existen pseudoprimos de Mersenne, por asi decirlo.

   En resumen, no es satisfactorio, (fructifero) el criterio de primalidad de Fermat, donde el valorar un solo 'pt' y evaluar su 'rt', no es un imposible para llegar a un resultado determinista.

 *) Respecto a Miller-Rabin (que abreviare como 'MR') ... me perdi, con la simple lectura que le di, pero Gracias mi Maestro. Pero estos señores se equivocan, ya que solo debemos valorar:

\( pt = \dfrac {nb-1} {2} \)

   Solo un 'pt' (punto estructural) con lo que dejamos atras a nuestro estimado Fermat (lo digo con respeto y admiracion) y en parte tambien a 'MR' porque emplean o dan, muchos exponentes ó potencias, a valorar, sin tomar en cuenta las bases 'a' que tambien se consideran para valorar.

   En el metodo 'PEN' que les expuse, este no es totalmente determinista y sigue siendelo asi, ... lo deje asi, porque por intuicion empirica, sabia que necesitaba saber y conocer mas, sobre la estructura numerica, no de los naturales pares, sino de los 'nb' naturales base, naturales impares no multiplos de (3) que organizados en los Conjuntos: FV, VL, V, VM, etc encontraremos una manera de clasificarlos de acuerdo a las similitudes e igualdades, respecto a la estructura numerica de los que son primos.

  *) Analizando lo anterior, desde el Conjunto FV, encontre criterios que fueron absolutos, para que la PEN sea determinista. Lo que me distrajo, fue el encontrar un modo o procedimiento, con el que estructuralmente, si un 'nb' compuesto pasase por primo, con el proceso se llegaba a determinar sus divisores (p,q) no encontrandose estos cuando era primo.

   La metodologia era muy compleja para evaluar 'nb' cada vez mas grandecitos, llegando a concebir que existe un 'pf' (Punto de Factorizacion) Estructural, lo que al comentarlo en uno de mis
hilos, no se como me vi enrredado con los RSA (y debiendo una piel de tigre de bengala)

  Gracias a las explicaciones de mis maestros, descubri que determinando el 'pf' de un compuesto, determinamos y/o obtenemos directamente 'X' y con este ya pues 'Y' con los que conformamos a los divisores (p,q) .... a lo que me referi, como que aplicando Fermat, conformamos el valor natural de los divisores especificos del compuesto.

  Me exprese de esa manera, porque era pura emocion el llegar a la factorizacion de Fermat, desde el enfoque estructural. Claro que luego Feriva me explico que lo que se decia era que los compuestos se pueden expresar como una diferencia de cuadrados, sin restarle merito a Fermat.

  *) Analizando y exportando datos, es que se me ocurrio ver como seria la factorizacion en 'Mn' compuestos de Mersenne, y estando en esto, en una de las exportaciones y/o impresiones de datos en pantalla, intuitivamente me llamo la atencion, por lo que exportando en solo los que eran 'Mp' primos de Mersenne, habia algo singular, mas al coleccionarlos en una lista, eran naturales dados sin un orden perceptible, lo que era de menos, pues al ordenarlos, tampoco habia una constante o razon, que indique sucesion o progresion y tampoco era importante esto, donde comenzando a exportar otros datos, me di cuenta que esos naturales de valoracion, pertenecian a un conjunto de naturales.

   Es asi que comprobe, hasta poco mas de la mitad de los 'Mp' encontrados, que esa unica valoracion en 'rt' pertenezca al conjunto exclusivo que denomine como:  cm={ }

  Increiblemente era asi, pero me dije que estaria como Fermat, donde si bien todos los 'Mp' lo cumplen, tambien se darian 'Mn' compuestos que pasarian por primos. Entonces hice que el programa en Python evaluara cada 'Mn' numero de Mersenne, determinando su primalidad y controlando como contabilizando los fallos que se dieran. El resultado fue que no se dieron fallos, hasta donde pude evaluar uno por uno.

  A la metodologia lo denomine como: 'PEM' Primalidad Estructural para Mersenne, el cual es un Metodo Determinista.


Saludos cordiales ....

10 Junio, 2020, 02:12 pm
Respuesta #18

Víctor Luis

  • Héroe
  • Mensajes: 1,164
  • País: bo
  • Karma: +0/-0
  • Sexo: Masculino
Buenas ....

Spoiler
Gracias Amigo Feriva,... por tu preocupacion por mi salud, y es que a finales de 2018 mi madre tuvo una caida de su altura, lo que nos revelo problemas neurologicos que tenia. Si te digo que 'en casa de herrero, cuchillo de palo' esto es poco, (mi hermana es medico general) me costo MUCHO restablecer a mi madre(y es que aqui, los medicos son burros en un 75% ... y eso) y luego, el año pasado 16-Jun fallecio mi padre, algo que para lo que me fui preparando, y semanas antes llegaba mi hijo, rechazado por la familia de mi ex y por ella misma, .... suficiente razon para dejar de lado mi proyecto matematico, echar a la basura, un montonazo de papeles, hojas de carpeta en su mayoria, ... pues me decidi por cumplir mi rol de padre, que muy trabajoso y doloroso me ha costado hasta hace semana atras, donde evalue  mi hijo, en llevar adelante un negocio de tienda de barrio.
   Antes de la llegada de mi hijo, me hice revisar, donde el problema de mi fatiga, es que uno de mis pulmones trabaja a casi la mitad de su capacidad, lo que repercute en el corazon ... el Neumologo me diagnostico 'asma por fumar' y aunque ya no fumo, cuando hace frio, se me hincha la barriga y es como un ataque, con insuficiencia respiratoria, lo que me descompensa y con esto del coronavirus, hasta llego a pensar que pues ni modo, ya me llego ... Si me llega a dar, no creo que lo supere amigo.
[cerrar]

  *) Validando a la 'PEM' como metodo determinista, (criterio mio por ahora) es que es viable como valido, la existencia de un "Punto Estructural de Primalidad" que por mi parte no he logrado ajustar el criterio de evaluacion debido a que debe organizarse a los 'nb' en un conjunto tal, donde los que son primos y de acuerdo a su estructura numerica, se vayan dando en correspondientes grupos GP.

  Algo de esto ya lo hube encontrado, años atras, antes de quedar sin computador y en los analisis posteriores que hice, ... donde desde la estructura correlativa de dos primos, encontramos a que estos conforman (a priori) a un 'Mn' compuesto, con lo que analizando mas esto, especulo sabriamos de antemano, una gran cantidad de Mn que son compuestos. (no pudiendo hacer esto, nuestros amigos de GIMPS)

  *) Antes de mi ultima ausencia del foro, por causas computacionales, me di el gustito (por decirlo asi) de hacer un reto, expresando que:

  "siendo (p) primo, como valida e invalida este la primalidad de (q) un natural impar no multiplo de tres?"

  Resulta que si:

   m = (5*7) = 35

  La estructura de 'm', debe darse y estar estructurada, precisa y exactamente cabal, a las estructuras de sus divisores, es decir de (5) y de (7) ... Esto no se observa en compuestos 'pares', algo que no es capricho mio.

  Dicho de otra manera, sabiendo la estructura de (P) y de (Q) conocemos la estructura basica del compuesto 'm' que conforman, es decir, que con la estructura de 'P' el cual es primo, llegamos mas facilmente a saber la estructura basica de 'm' y con estos, llegariamos a una estructura basica que deberia ser de 'Q', donde solo procedemos a comprobar esto y de ser asi, entonces es primo ... que les parece, (35) no solo indica que es 7 partes de 5, ó que es 5 partes de 7, como considero nos lo hace dar a concebir, el criterio de divisibilidad, ... desde el cual, extraen y elaboran, criterios sobre 'primalidad' y/o factorizacion, criterios que son complementarios y no necesariamente extraños.


Saludos cordiales ....

10 Junio, 2020, 08:10 pm
Respuesta #19

feriva

  • Matemático
  • Mensajes: 9,076
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
  • No soy matemático, eso es una etiqueta.
Hola, Víctor Luis.


 *) Respecto a Miller-Rabin (que abreviare como 'MR') ... me perdi, con la simple lectura que le di,


Te lo explico a mi manera, que lo otro era tal como lo explica la Wiki.

El número “n” es un número impar del que queremos saber si es primo.

Entonces supón que es n=85.

A partir de ahí, si a “n” le restamos 1, queda un par, 84, y lo que hacemos es buscar la descomposición de este par:

(Bueno, en la práctica a lo mejor no es fácil factorizar, pero se puede ir dividiendo varias veces por 2 hasta que quede el impar, yo te lo explico factorizando)

\( 84=2^{2}\cdot3\cdot7
  \).

Multiplicando los factores impares, el número 84 queda expresado en producto dos de factores:

\( 84=2^{2}\cdot21
  \).

Para el caso general (ya sea n= igual a 85 o a otro impar cualquiera) el producto de los impares de esa descomposición (sean dos, tres... los que sean) es lo que llama “m”; es un número que es el producto de esos impares, de tal forma que aquí tendríamos

\( 84={\color{blue}n-1=2^{k}\cdot m}=2^{2}\cdot21
  \); o sea, en este caso la potencia es k=2 (en otros casos “k” puede ser 2 u otra potencia).

Despejando en la igualdad azul, \( m=\dfrac{n-1}{2^{k}}
  \); que en este caso es \( m=\dfrac{85-1}{2^{2}}=\dfrac{84}{4}=21
  \).

Hasta aquí lo mismo que tu pt, creo.

Entonces, en el test de Miller-Rabin, toma una base “a”, vamos a poner que sea a=3, y halla este resto

\( a^{m}\equiv r_{0}(mod\, n)
  \)

En nuestro caso \( 3^{21}\equiv r_{0}(mod\,85)
  \); que sale \( r_{0}=73
  \).

Acto seguido mira a ver si esto fuera cierto

\( r_{0}\equiv\pm1(mod\,85)
  \); o sea \( 73\equiv\pm1(mod\,85)
  \); y no es cierto.

Si hubiera sido cierto sería probable primo; y ahí acabaría el test del número.

Entonces el test sigue así; calcula este otro resto, al que llama r1:

\( r_{0}^{2}\equiv r_{1}(mod\,85)
  \); o sea \( 73^{2}\equiv r_{1}(mod\,85)
  \); y sale \( r_{1}=59
  \).

Seguidamente, mira a ver si esto es verdad

\( r_{1}\equiv-1(mod\,85)
  \); o sea \( 59\equiv-1(mod\,85)
  \); y no es cierto.

Si hubiera sido cierto, sería probable primo y acabaría el test.

Después mira a ver si es cierto lo mismo pero con 1 en vez de -1:

\( 59\equiv1(mod\,85)
  \); que tampoco es verdad.

Si hubiera sido verdad, se hubiera concluido con seguirdad que No es primo.

Como el test no ha dicho nada todavía para n=85, se sigue elevando al cuadrado el resto (que va hasta aquí por \( b_1 \)) y haciendo la misma rutina hasta que salga algún resultado de ésos.

...

No sé si me habré liado y habrá algo mal.

Lo importante es que vayan mejor las cosas para ti, tu hijo y la familia, esto otro se puede explicar más veces con más ejemplos, si quieres.

Un abrazo.