Foros de matemática
10/12/2017, 09:10:28 pm *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Puedes practicar LATEX con el cómodo editor de Latex online
 
 
Páginas: 1 2 3 [4]   Ir Abajo
  Imprimir  
Autor Tema: Consultando a Feriva y El_Manco. Maestros de la matemática.  (Leído 3692 veces)
0 Usuarios y 1 Visitante están viendo este tema.
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 6.705



Ver Perfil
« Respuesta #60 : 10/08/2017, 07:06:49 am »

Buenos días Víctor Luis.

Cita
Siendo n=13070572018536022021

¿Cómo operas con este natural, para evaluar su primalidad con Fermat?



Bueno, no es que no se pueda factorizar (probando con el test) un Mersenne con el pequeño teorema de Feramt, es que no se puede aplicar lo que hacías; lo que te decía, si das un número “n”, elevado a un primo y a ese número le restas 1, pues ya es así, no le puedes restar 1 a la potencia del primo.

Por ejemplo

[texx]28^{3}-1=21951
 [/texx]

Tienes que 21951 es múltiplo de 3, el primo de la potencia, pero esto no es por el pequeño teorema; arriba no tenemos un “p-1”, sino un “p”.

Y no podemos restar un 1 al tres porque porque ya tenemos de compañero al sumando -1; si lo hacemos, si restamos 1 y lo dejamos al cuadrado, nos dará un número menor que 21951 y por tanto, éste, 21951, no lo dividirá por ser mayor; sería falso; ¿lo ves?

Vamos a ver cómo hacerlo bien.

El teorema de Fermat, en su forma principal, es así

[texx]a^{p}\equiv a\,(mod\, p)[/texx]

Spoiler (click para mostrar u ocultar)

Ahora, sí, con esta forma de expresar P.T.Fermat, si tuviéramos un primo en la potencia, si podemos operar para que en vez de esa “a” nos quede un 1 (o sea, para que nos queda la otra forma de expresar el pequeño teorema).

Por ejemplo, con “a=6” y con “p=7”

[texx]6^{7}\equiv279936\,(mod\,7) [/texx] (aquí quería poner un 6 en vez de 27993)

Esto es el P.T.Fermat en su forma principal.
Vamos a traducirlo a igualdad

[texx]6^{7}-6=7k[/texx]

Ahora qué pasa, que los dos sumandos son de la tabla del 6, entonces 7k es de la tabla del 6 porque es igual a eso; y como 7 es coprimo con 6, pues k entonces es el múltiplo de 6

Es decir, podemos dividir la igualdad a los dos lados entre 6, quedando

[texx]\dfrac{6^{7}}{6}-1=(7k)/6
 [/texx]

[texx]6^{7-1}-1=\dfrac{7k}{6}
 [/texx] Donde k/6 es algún entero al que podemos llamar “m”, por ejemplo

[texx]6^{7-1}-1=7m [/texx]

Esto, en forma de congruencia es [texx]6^{7-1}\equiv1\,(mod\,7)
 [/texx], donde el “p” es el primo 7; es decir, así que si “a=6”, tienes la forma [texx]a^{p-1}\equiv1\,(mod\, p)
 [/texx]

Que es la que tú quieres usar directamente, pero ya ves que no se puede usar directamente, es “1” aparece de dividir a los dos lados por “a”, no aparece por una receta mágica.

Si esto te queda claro, que imagino que sí, ya es muy fácil entender qué se sigue para “testar”, que no factorizar (no es apropiado en cuanto a lo que tú quieres hacer con este teorema, es más como un test de primalidad) los números y ver si son primos.

Tú me das este primo (puede ser también de Mersenne o de quién sea); a raíz de lo explicado, ¿qué puedo hacer con el pequeño teorema? Pues oye, tendré que expresarlo tal cual, como un primo en la potencia de la expresión principal del teorema, ésta [texx]a^{p}\equiv a\,(mod\, p) [/texx], donde sólo conozco “p” y tengo que probar distintos números “a” (a ojo de buen cubero).

Entonces, ahora, sabiendo de dónde sale, sí puedo elegir expresarlo así [texx]a^{p-1}\equiv1\,(mod\, p)
[/texx], porque ya sé cómo aparece ese -1 al operar dividiendo, ya sé que no es una receta mágica.

Esta forma [texx]a^{p-1}\equiv1\,(mod\, p)[/texx] nos dice que probando los distintos “a”, si el número que me has dado es primo, que no se sabe a priori, entonces se cumplirá la congruencia, el resto será 1, pero también se puede dar esto y no ser primo, como bien sabes. Ahora bien, siempre que el resto no sea 1, podemos ya decir que no es primo y descartarlo (en este caso no pasará eso nunca porque me has dado un primo).

Es un método para descartar los compuestos, principalmente; si bien no siempre es fácil, porque tenemos tus queridos números de  Carmichael, los cuales dan resto 1 para todo “a” que se pruebe pese a que no son primos (ya sé que tú los distingues con tus cosas, pero este método por sí solo no los distingue; lo cual no quiere decir que se tire a la basura, porque se puede complementar con otras cosas más).

Así pues, con esto ya está terminada la explicación.

Queda elegir los “a” con un poco de tino y probar y ver si no sale compuesto para esas bases de las potencias; si no sale, será probablemente primo, lo cual certificaremos ya  con otro método.

Sé que tienes un poco de desprecio por este test por no ser determinista; pero no hay que despreciarlo, porque cuando el ordenador corre tanto para decirte que un número no es primo, lo encuentra fácilmente apoyándose en este teorema, descartar es muy importante para correr mucho cuando pruebas muchos números.

 Si viajaras en el tiempo, como dices, y conocieras a Fermat, yo creo que te llevarías bien, porque él era muy empírico; y predijo muchas cosas, teoremas que no demostró y luego resultaron ser efectivamente ciertos (como el pequeño teorema éste, entre ellos; lo observó y lo probó, pero no lo demostró). Sólo se equivoco con sus primos de Fermat, que pensaba que todos los que tenían esa forma iban a ser primos, pero no.


Un cordial saludo.
En línea

Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 1.059


Ver Perfil
« Respuesta #61 : 11/08/2017, 05:04:17 am »

Buenos Días Feriva...


◘ Agradezco y Comprendo la explicación y exposición que me haces,... como siempre, te luces dando a conocer los enfoques que pueden abordar a un criterio matemático.


○ Pero mi consulta era simple.... Siendo [texx]n=13070572018536022021[/texx] ¿Cómo evaluamos su primalidad con Fermat?

Iniciamos con [texx]q=n-1[/texx] siendo por tanto:

[texx]q=13070572018536022020[/texx]


De esta forma, aplicando Fermat, deberíamos determinar y evaluar el resto de dividir:

[texx]\displaystyle\frac{2^{q}}{n}[/texx]

Ó

[texx]r=2^{q} \ mod \ n[/texx]


Debiendo darnos  [texx]r=1[/texx] ya que [texx]n[/texx] es primo y este [texx]n[/texx] no es nada de un natural de Mersenne, ni nada por el estilo, es un simple natural impar primo.


• Lo que sucede, es que, para realizar algunos analisis, me es complejo, operar directamente con Python:

Código:
r=(2**q)%n

→ Por lo que me dije.... les consultaré a mis Maestros.






Saludos Cordiales...
En línea
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 6.705



Ver Perfil
« Respuesta #62 : 11/08/2017, 07:01:52 am »

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

Cita

¿Cómo evaluamos su primalidad con Fermat?


No se puede hacer eso usando solamente el pequeño teorema de Fermat, como te comentaba en la respuesta anterior.

Lo que podemos hacer es identificar los compuestos y “filtrarlos”, cribarlos, pero este número que me das no es compuesto, es primo; así que el pequeño Fermat sólo nos dirá todo el rato que el resto es 1, probemos con la base que probemos. Pero de ahí no podemos deducir con seguridad que sea primo, pues hay números que sin ser primos también dan resto 1 para todas las bases.

Si no es primo, lo más normal es encontrar muy pronto una base para la cual el resto no es 1.

De ahí algo que ya conoces muy bien y has probado: Miller (el de el test Miller-Rabin) creó un método basado en el pequeño Teorema de Feramat; este método es determinista condicionalmente; digámoslo así: si es cierta la hipótesis de Reimann, entonces el método de Miller es determinista. Quiere decir que sólo podría equivocarse al evaluar la primalidad de un número si fuera falsa la Hipótesis. Después llegó Rabin y modificó el método por un algoritmo que es completamente seguro.

(Me extraña que preguntes esto porque lo has usado muchas veces y has hablado con el_manco de ello en varias ocasiones)

Spoiler (click para mostrar u ocultar)

Resumiendo y contestando directamente a tu pregunta: lo único que puedes hacer con el pequeño teorema (sin añadir más de lo que dice, como hacen Miller y Rabin) es

buscar valores para “a” aquí

[texx]a^{13070572018536022021-1}-1
 [/texx]

hasta encontrar un valor “a” coprimo con “q” de forma que [texx]a^{13070572018536022021-1}-1
 [/texx] NO sea divisible entre [texx]13070572018536022021[/texx]; eso querrá decir que, con seguridad, el número no es primo.

Pero en este caso sí es primo, luego no se encontrará nunca, siempre será divisible; con lo que no se puede asegurar si es primo o no, sólo se puede sospechar que lo es.

Por lo dicho, con tu ejemplo,probando [texx]{\color{blue}a}={\color{blue}2}
 [/texx] puedes usar [texx]{\color{blue}2}^{q}-{\color{blue}2}
 [/texx] ó [texx]{\color{blue}2}^{q-1}-1
 [/texx] y dividir entre [texx]q[/texx] para ver si es divisible ó puedes usar, como haces, [texx]{\color{blue}2}^{q}
 [/texx] y dividir entre [texx]n=q
 [/texx] para ver si el resto es 1 (ólvidate de ese “n”, es “q” lo que tienes que usar si usas el pequeño teorema).

(lo mismo da hacer una cosa que otra, es lo mismo).

Pero como es primo (haciendo lo que haces) te dará siempre resto 1, no te puede dar otra cosa.

Eso no quiere decir que no sea compuesto, pues hay compuestos que tambien te van a dar resto 1 con base 2. Tendrás que probar además de 2 otras bases; si alguna no da resto 1, es compuesto.

No sirve para más (ni para menos) desenmascara muchas clases de comupuestos fácilmente, pero no determina de forma directa si un número es primo o no.

Así, yo puedo tener 253 y no saber si es primo o no; entonces pruebo [texx]2^{252}\%253
 [/texx] y me da resto 81; luego es compuesto; ya no tengo que probar con otra base, me basta probar con esa primera para descartarlo, tomando como base de la potencia el valor 2.

Si pruebo con un primo como 127, al hacer lo mismo [texx]2^{126}\%127
 [/texx] me da resto 1.

Pruebo tomando de base 3: [texx]3^{126}\%127
 [/texx], me da también resto 1...

No me dará nunca otra cosa, es primo; pero nunca probaré todas las bases y además podría ser un número de Carlmichael, que se comportan en este test como los primos.

Lo puedes hacer también de la otra manera, como te digo yo; tendrías que mirar si [texx](2^{127}-2)\%127
 [/texx]


Cuidado ahí arriba, que había puesto equivocadamente un 1 en vez de un 2 aquí  [texx](2^{127}-{\color{red}1})\%127[/texx]

Obviamente sólo tienes que aplicar la congruencia [texx]base^p-base[/texx] es divisible por "p"

   

 
  da resto cero; y en efecto, lo da, porque es la misma cuenta pero transformada. Y lo dará también para 2 o cualquier base (pero seguiremos sin poder estar seguros de si es primo o no).

Un cordial saludo.
En línea

Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 1.059


Ver Perfil
« Respuesta #63 : 12/08/2017, 08:06:02 am »

Buenas Tardes Feriva...


Cita
De ahí algo que ya conoces muy bien y has probado: Miller (el de el test Miller-Rabin) creó un método basado en el pequeño Teorema de Feramat; este método es determinista condicionalmente; digámoslo así: si es cierta la hipótesis de Reimann, entonces el método de Miller es determinista. Quiere decir que sólo podría equivocarse al evaluar la primalidad de un número si fuera falsa la Hipótesis. Después llegó Rabin y modificó el método por un algoritmo que es completamente seguro.

◘ No comprendo esto que dices.... ¿Qué tiene que ver Miller-Rabin, que se basan en Fermat, para interponerse con la validación de la hipótesis de Riemann?

• No estimo que Riemann, se tenga que validar (por así decirlo) con que Miller-Rabin lleguen a ser deterministas,... puesto que con simplemente probarse ante el natural [texx]n=2^{11}-1=2047[/texx] tanto Fermat como Miller-Rabin "Fallan", donde como nos explicó El_Manco, se utilizan otras bases que no sea únicamente "2" y se determina la no primalidad de este natural, donde luego se dan otros naturales, que suspuestamente pasan por primos, debiendo emplear otras mas bases, como las que nos lo expuso el Amigo El_Manco.
→ Y es justamente por esta situación, que voy en contra de Miller-Rabin, por mas demostración matemática que tengan, donde "nunca" llegarán a ser "deterministas".... ó es que tu crees que para determinar primos de mas de 2500 cifras, aplicaría Miller-Rabin, siquiera por si acaso? ... sabiendo que no me darán un resultado determinista?
→ No pretendo entrar en polémicas,... pero, Miller-Rabin, (en mi criterio personal) NO validan ni sugieren ni siquiera señalan, algo referente a la validez ó invalidez de la hipótesis de Riemann,... esto poniéndome a favor de Riemann, ya que de lo contrario, se estaría aluciendo que Riemann es falso.




◘ Sobre lo nuestro... la consulta que te hice... Agradezco otra vez la explicación que me haces;... pero en sí, tan solo quería saber, el cómo operar con [texx]q=13070572018536022021[/texx] la potencia [texx]2^{13070572018536022020}[/texx] donde luego, obteniendo la cantidad que se dé, Python y los demás lenguajes de programación, determinarán el resto dado de dividir entre [texx]q[/texx]

• Quizas el valor natural de [texx]q[/texx] dado en este ejemplo, no devele una complejidad en el tiempo de proceso en Python,.... donde si tomas un natural [texx]q[/texx] de digamos 500 cifras,... esto no es posible hacerlo, así de forma directa, que si bien no nos produce un "error", Python se toma su muy tiempo mensual de vacasiones, para darnos un resultado y es que consultaba, si no habría otra manera de operar esto, ya que con [texx]3^{q-1}[/texx] es mucho mas complejo, para un [texx]q[/texx] de ni siquiera 250 cifras.
→ La mejor solución con complejidad reducida, es la que encontré, operando con la forma binaria de [texx]q-1[/texx] empleando como divisor a [texx]q[/texx] y esto sirve, tanto para las bases: {2,3,5,...} que empleemos;.... Pero, en naturales de más de 1000 cifras, el valor binario tiene mayor cantidad de cifras, algo como 1500 cifras en binario, donde operando con cada cifra, el proceso se hace complejo y mucho mas, cuando tratamos naturales de 2500 cifras, donde no sabría decir, si Python se demora mas, en conformar el natural binario ó la complejidad se dá, al operar con esa metodología, con cada cifra binaria,... ó quizas ambos ocasionan la complejidad.




Saludos Cordiales....
En línea
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 6.705



Ver Perfil
« Respuesta #64 : 12/08/2017, 08:32:02 am »



Hola, Víctor, buenos días.

Luego te leo más despacio que me voy a hacer la comida.

Ten en cuenta que, claro, si la potencia es de un millón de números, por ejemplo, eso supone un número de un millón de cifras; le costará hasta hacer sumas con esas cantidades, así que más le costará sacar restos.

Luego te veo.

Un cordial saludo.
En línea

Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 1.059


Ver Perfil
« Respuesta #65 : 12/08/2017, 10:32:58 am »

Buenas Tardes Feriva....



Cita
Ten en cuenta que, claro, si la potencia es de un millón de números, por ejemplo, eso supone un número de un millón de cifras; le costará hasta hacer sumas con esas cantidades, así que más le costará sacar restos.

◘ Y eso de sacar restos.... debes conocer alguna ó algunas metodologías,... y es lo que me motiva a consultarles, sin entrar a fundamentos, teoremas y demás.....









En línea
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 6.705



Ver Perfil
« Respuesta #66 : 12/08/2017, 11:15:52 am »


◘ Y eso de sacar restos.... debes conocer alguna ó algunas metodologías,... y es lo que me motiva a consultarles, sin entrar a fundamentos, teoremas y demás.....



Pues el que se pueda hacer algo (hasta donde a mí se me ocurre, que a lo mejor hay cosas por ahí que te podrían decir los que saben más) va a depender de la descomposición del par de la potencia; vamos a verlo con un número pequeño

[texx]\dfrac{2^{30}}{31}
 [/texx]

Tenemos que 30=2*3*5, entonces lo podemos escribir, por ejemplo como [texx]2^{30}=2^{30-6}*2^{6}
 [/texx] con lo que tenemos dos potencias más pequeñas.

No tiene más secreto que la regla de que las potencias se suman en los productos de una misma base; en general: [texx]x^{a}*x^{b}=x^{a+b}
 [/texx].

Es lo mismo. Pero escribiéndolo así podemos hallar los restos para dos “doses” con potencias más pequeñas.

Entonces, por una parte

[texx]2^{6}\%31=2
 [/texx]

y por otra parte

[texx]2^{24}\%31=16
 [/texx]

Esto quiere decir que 2 a la 6 es un múltiplo de 31 más 2, y 2 a la 24 es un múltiplo de 31 más 16.

Luego

[texx]2^{30}=2^{6}*2^{24}=(31k+2)(31k+16)=31m+32
 [/texx]

(ahí no tienes ni que preocuparte por multiplicar por la distributiva, todos van a ser múltiplos de 31 menos el producto de los dos números que no lo son, con mirar ese producto vale; y el valor de “m” nos da igual cuál sea, es un mútliplo de 31 y ya está).

Y entonces finalmente tenemos que 32=31+1

Es decir, resto 1.

Bien, pues descomponiendo ese numeraco en sumas pequeñas, haces lo mismo y sacas el resto.

Spoiler (click para mostrar u ocultar)

Saludos.
En línea

Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 1.059


Ver Perfil
« Respuesta #67 : 13/08/2017, 06:47:05 am »

Buenos Días Feriva....


◘ GRACIAS MI AMIGO y MAESTRO...  es como tú ya sabes, con las "potencias" me hago un lío;... pero como lo explicas tú, se entiende, "mas claro que agua de manantial !".

• Descompones el exponente 30 de la potencia en: 6 y 24, dándote para el divisor (ó modulo) [texx]31[/texx] los restos:

[texx]r_{1}=2^{6} \ mod \ 31=2[/texx]

[texx]r_{2}=2^{24} \ mod \ 31=16[/texx]

→ Lo que no sabía, era que [texx]r_{3}=r_{1}\cdot{}r_{2}=32[/texx]

Donde:

[texx]r_{3} \ mod \ 31=1[/texx]


 :sonrisa_amplia:  Y es que por la ignorancia de uno, lo primero que se le ocurre, es sumar los restos,... y es que en las lecciones de las literaturas consultadas, no se indica específicamente, que los restos se multiplican ó al menos, no encontré esta parte,... ó quizás es algo obio, cuya obiedad no se me dió.


◘ Habrían otras maneras que determinar el resto de [texx]\displaystyle\frac{2^{30}}{37}[/texx] ?


Por ejemplo, determino:

[texx]r_{1}=2^{10} \ mod \ 37=25[/texx]


Donde luego operamos:

[texx]r_{2}=r_{1}^{2} \ mod \ 37=33[/texx]


Y finalmente operamos:

[texx]r=r_{2}\cdot{}r_{1} \ mod \ 37=11[/texx]


○ Ya que:  [texx]2^{30}\equiv{11} (mod \ 37)[/texx]

► Esto sería en algo similar a lo que explicaste ?





Gracias y Saludos Cordiales....
En línea
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 6.705



Ver Perfil
« Respuesta #68 : 13/08/2017, 08:41:26 am »

Hola, Víctor Luis.

Sí, claro que hay otras maneras, haciendo todas las sumas que quieras; ten en cuenta que, en general esa regla no es sólo para dos potencias de 2, es

[texx]2^{k}=2^{a}*2^{b}*2^{c}*...2^{z}
 [/texx]

tal que [texx]a+b+c..+z=k
 [/texx]

Convendrá elegir las que se vean más fáciles según la multiplicidad de los números, pero en principio el mecanismo es así de simple.

Y se pueden hacer, efectivamente, cosas con cuadrados y demás pues también tenemos esta regla:

[texx]2^{k}=(2^{a})^{b}
 [/texx] tal que [texx]k=a*b
 [/texx]

Entonces, por ejemplo

[texx]2^{30}=(2^{5})^{6}
 [/texx] que sería 2 a la cinco multiplicado seis veces

[texx]2^{30}=2^{5}*2^{5}...seis\, veces
 [/texx]

y aquí ya ves que las dos reglas se dan la mano, pues la suma de seis 5 es 30.

Sin embargo, ya vemos que [texx]2^5[/texx] es menor que 37, según el módulo que has elegido, por tanto, como hay una cantidad par, también podemos tomar [texx]2^{5}*2^{5}=2^{5+5}=2^{10}
 [/texx] multiplicado tres veces en vez de seis.

Basta hacerlo sólo con uno y luego ya multiplicamos el resto res veces y hallamos el resto

[texx]2^{10}\%37=25
 [/texx]

Daría efectivamente 11 tres veces.

Lo que sea más corto; puedes usar potencias de diez... lo que veas.

Otra cosa que puedes usar, cuando el "dividendo" es menor que el módulo, entonces el resto es el propio dividendo, no sé si lo sabes; o esa, por ejemplo 7%35 igual resto 7.

Un cordial saludo.
En línea

Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 1.059


Ver Perfil
« Respuesta #69 : 16/08/2017, 04:40:07 am »

Buenos Días Feriva....


☼ MUCHAS GRACIAS... MI MAESTRO FERIVA... !!!!

○ Aunque por ahora no lo aplique en las modalidades de calculo de mis programas,... en breve te haré unas consultas mas, para de una vez por todas, quitarme la complejidad de operar con potencias y restos de estas hacia algún módulo.





Saludos Cordiales....
En línea
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 6.705



Ver Perfil
« Respuesta #70 : 16/08/2017, 08:18:40 am »

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

Cita
Aunque por ahora no lo aplique en las modalidades de calculo de mis programas,... en breve te haré unas consultas mas, para de una vez por todas, quitarme la complejidad de operar con potencias y restos de estas hacia algún módulo.

La complejidad, yo creo, es inevitable, se puede acortar un poco, pero ten en cuenta que los programas ya hechos, módulos optimizados y demás, ya manejan esos “trucos” y más todavía; y aun así no dan para encontrar fácilmente el siguiente primo de Mersenne, por ejemplo.

Una cosa importante que quedó sin contestar.

Decías por ahí que los restos se multiplica y creías que se sumaban. Esto depende de la cuenta que tengamos.

Si lo que analizamos es una suma, se suman los restos respecto de cada sumando y se mira a ver si esa suma se queda corta en cuanto al módulo o se queda justa o se pasa. Por ejemplo:


Queremos expresar esto respecto del módulo 3, por ejemplo:

[texx]60+35+8
 [/texx]

tenemos que el resto respecto de 60 es cero, respecto de 35 es 2, y respecto de 8 es 2 también.

Los restos suman 4, y lo que hacemos es descomponerlo en suma de treses y lo que sobre.

Queda 3+1, luego el resto es 1.

Podría haber sido 3+3+1 ó 3+3+3+2... esto es un caso particular, claro

Naturalmente, es más cómodo escribirlo con multiplicaciones; si tenemos [texx]3+3+3+3+1[/texx] escribimos [texx]4*3+1[/texx].

La cuestión es que tendremos una suma que será un múltiplo de 3, ó el módulo que sea, y sumando menor que 3 que será el resto.

Si tenemos un producto, se multiplican los números de la cuenta que no son múltiplos del módulo, los restos respecto de cada factor; y luego, según lo que sobre, se obtiene el resto; por ejemplo:

[texx]14*7
 [/texx]

Para expresarlo módulo tres, por ejemplo, haremos

[texx](3*4+2)*(3*2+1);o\, sea\,(3a+2)*(3b+1)
 [/texx]

Y, claro, al multiplicar por la distributiva te va a quedar la suma

[texx](3a*3b+3a)+(2*3b+2*1)[/texx]

Todos son múltiplos de 3 menos el sumando que procede del producto de los que no son múltiplos de 3.

Si esto lo haces multiplicando paréntesis que tengan más de dos sumandos, también pasa igual, todos serán múltiplos del 3 (o el módulo que sea) excepto el producto de los que no son múltiplos del módulo.

Un cordial saludo.
En línea

Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 1.059


Ver Perfil
« Respuesta #71 : 16/08/2017, 09:44:41 am »

Buenas Tardes Feriva...


Cita
Si tenemos un producto, no es exactamente que se multipliquen los restos, se multiplican los números de la cuenta que no son múltiplos del módulo; y luego, según lo que sobre, se obtiene el resto; por ejemplo: ....


• En esto ultimo que explicas,.... sinceramente,... me perdí,... aunque veo lógica, de acuerdo al Algebra que aprendí,... pero se me ocurrió, que podría habrir un hilo, para que en este, me explaye, consultando mis dudas y lagunas petenciales,... como las modalidades de calculo, que fui desarrollando y/o re-descubriendo, cuando analizaba manualmente con lápiz y cuaderno, luego de haberse quemado mi computador....  y es que reitero esto,... porque si el destino, hubiera querido que se quemara y/o explotara, el ventilador,... (al que le apliqué un poco de grasa mecánica, sin considerar que esta se diluiría e hiciera corto con el componente eléctrico) para interrumpir todo el suministro del circuíto eléctrico,... es que, sin esta ignorancia y sin los datos de enseñanza que me ivan dando tanto tú Feriva como El_Manco, respecto a la primalidad de Miller-Rabin y mi testarudéz, de no seguir el criterio de esta metodología, tal como nos lo exponía El_Manco, ante lo cual, debía corroborarlo por mi mismo criterio,.... es que todos estos aspectos y acontecimientos, se dieron, para que realizara y/o continuara, mis analisis y anotaciones manuales con lápiz y cuaderno,... donde lo único que tenía, era recordar lo que me fueron enseñando (ustedes mis maestros) y así, empíricamente (orgullo propio) recorrí los pasos de Fermat, cayendo en la credubilidad de sus famosos primos [texx]P_{f}[/texx] y dándome cuenta que estos no eran una forma de generación de naturales primos;... porque, tuve que desarrollar mis propias fórmulas, para evaluar la primalidad, con la desepcionante metodología de Miller-Rabin, recordando, que no es determinista,... y es que,... qué mas uno puede hacer, con esos recursos?
→ Pues mucho, si nos salimos del criterio concebido hasta ahora, de nuestra matemática actual, respecto al campo de Teoría de Números, (con lo cual, no me voy a desestimar a toda la matemática actual,... por si acaso...) donde luego de ocupar dos cuadernos, me dije de resumir los datos de estos, en un tercero, y es cuando observé, la estructura numérica que tienen los números naturales, excepto, los naturales múltiplos de 2 y 3, que favorablemente, se acomodaban al Conjunto FV y es algo que no lo hice adrede, sino que se dió así y pude comprender, la estructura de primalidad inicial que debe tener todo natural impar, para ser considerado como un posible primo,... algo que carecen los famosos pseudoprimos de Carmichael,... donde no tengo nada contra este matemático,... sino que estos famosos compuestos pseudoprimos,... «NO EXISTEN»,... ante en "Enfoque Estructural".

• ¿Quién imaginara que un testarudo, ante la quema de su computador y proseguir con su testarudéz de comprensión?... Concibiera, un enfoque de primalidad "estructural", concibiendo que en esta primalidad, también está el criterio de factorización, que expresa y manifiesta a la comunidad, que todo compuesto semiprimo, tiene un "punto de factorización", cuya determinación, (sin importar el tamaño de cifras que tenga el compuesto) su factorización es inminente, in-negable, irre-futable,... con la seguridad de apostar los multi-universos existentes, a quien quiera contradecir, este criterio, que mas que criterio, es un principio universal de factorización de compuestos semiprimos (por ahora...).
→ Si [texx]m=p\cdot{}q[/texx] sabiendo [texx]p[/texx] y [texx]q[/texx] sabemos determinar [texx]x[/texx] (para Fermat) y ya con esto, tenemos la factorización del compuesto, asegurada.

• Pero como no sabemos [texx]p[/texx] ni [texx]q[/texx],... lo único que nos guía, es la raiz cuadrada [texx]rz=\sqrt[ ]{m}[/texx],... que por sí sola, NO nos dice nada, salvo que delimita el valor natural de ambos divisores,... lo que tampoco nos dá una ventaja, para factorizar compuestos de cifras como querramos.
→ PERO... con Fermat, encontramos, que para cada [texx]Kp=\displaystyle\frac{p\cdot{}100}{rz}[/texx] proporción del divisor [texx]p[/texx] respecto a la raiz cuadrada [texx]rz[/texx] tenemos una proporción constante [texx]cq[/texx] que nos permite determinar un punto natural muy próximo al valor natural del divisor [texx]q[/texx],... donde supongo todos, consideran que operar una factorización desde [texx]q[/texx], es un completo absurdo de las absurdeces triviales,... simplemente, porque, [texx]q[/texx] es mas grande y complejo que [texx]p[/texx],... y entre estos, aún no se tiene, una fórmula-proporcional, que nos permita deterrminar [texx]q[/texx] desde [texx]p[/texx] para algún [texx]Kp[/texx],.... y es que para [texx]q[/texx], se debe tener, una proporción [texx]Kq[/texx], donde entre [texx]Kp[/texx] y [texx]Kq[/texx],... no se tiene, una fórmula equipotencial, para determinar ambos naturales,... algo que (supuestamente) nos acompleja ante la Factorización.

• Esto no es real,... sin importar el valor natural de los divisores [texx]p[/texx] y [texx]q[/texx], sin importar si estos son de igual ó diferentes cifras, sin importar si el compuesto semiprimo inicia con las cifras iniciales: {9,8,7,6,5,4,3,2,1} mismo que altera el valor natural de la raiz cuadrada,.... sin importar todos estos,.... es que para cada [texx]Kp[/texx], se tiene una secuencia, con la cual conformamos, la proporción [texx]cq[/texx] para determinar, el punto natural mas próximo al valor natural del divisor [texx]q[/texx].
→ Si conforman y exportan compuestos, iniciados con las cifras: {9,8,7,...} observarán, que las raíces cuadradas, se dan muy altas, que los compuestos con cifras: {1,2,3,...},... lo cual es "trivial", ya que a pesar de tratarse de compuestos muy-distintos y muy-distantes, con sus respectivas raíces cuadradas, muy-distintas y muy-distantes,... "TODOS" tienen, una misma proporción [texx]cq[/texx] para cada proporción [texx]Kp[/texx], que con esto determinamos al divisor [texx]q[/texx] en base a [texx]Kp[/texx], que es lo que Fermat no nos lo dijo de forma directa con su metodología de factorización,... que especulativamente, diremos, es por desconocer, el Enfoque Estructural.


Spoiler (click para mostrar u ocultar)




Saludos Cordiales....
En línea
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 6.705



Ver Perfil
« Respuesta #72 : 16/08/2017, 10:59:57 am »

Buenas Tardes Feriva...


Cita
Si tenemos un producto, no es exactamente que se multipliquen los restos, se multiplican los números de la cuenta que no son múltiplos del módulo; y luego, según lo que sobre, se obtiene el resto; por ejemplo: ....


• En esto ultimo que explicas,.... sinceramente,... me perdí,...

Perdóname, lo tenía bien y luego lo cambié y lo volví a cambiar; edité y no lo puse en otro color, es culpa mía. Sí, son los restos de cada sumando respecto del módulo; ahora te sigo leyendo, pero quiero aclarar esto cuanto antes...

Es muy simple, no te líes por mi culpa por favor:

Si trabajas módulo 5 y tienes un sumando que es 27, lo escribes así 25+2, ¿no? Pues entonces sí, ese 2 es el resto, y esos restos son los que se suman o se multiplican.
He sido yo el que mientras iba escribiendo he dicho algo raro, no es que tú lo entendieras mal.

Cita
y es que,... qué mas uno puede hacer, con esos recursos?

Pues lo que te decía, usando Fermat, si un número es compuesto, normalmente se detecta enseguida (salvo algunos) con lo que se criba deprisa; no es determinista, pero quita las hierbas del camino digamos; eso es lo que se puede hacer. Y se puede complementar con otras cosas.

Un cordial saludo.
En línea

Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 1.059


Ver Perfil
« Respuesta #73 : 17/08/2017, 04:35:22 am »

Buenos Días Feriva...



Cita de: Feriva
Pues lo que te decía, usando Fermat, si un número es compuesto, normalmente se detecta enseguida (salvo algunos) con lo que se criba deprisa; no es determinista, pero quita las hierbas del camino digamos; eso es lo que se puede hacer. Y se puede complementar con otras cosas.

• También considero que Fermat quita las hierbas malas del camino, es decir, naturales compuestos que pasan con Fermat al evaluarlos con [texx]2^{p-1}\equiv{1} (mod \ p)[/texx]

→ Estos son unos pocos dados, hasta el Rango([texx]10^{6}[/texx])

Spoiler (click para mostrar u ocultar)

→ Y entre el Rango([texx]10^{6}[/texx],[texx]10^{7}[/texx]) tenemos estos otros:

Spoiler (click para mostrar u ocultar)


◘ El pequeño detalle, es que de estos 619 compuestos que hacen fallar a Fermat,... con un simple criterio de primalidad estructural, tan solo el 7,1% de los compuestos, se las darían como primos;... Pero, aplicando el criterio de Primalidad_PQ, donde si [texx]p[/texx] es un natural primo, con este podemos verificar la primalidad de [texx]q[/texx] un natural impar no múltiplo de 3,.... Y ya con esto, ninguno de estos compuestos pasan como primos, donde supongo entre estos, estarán los famosos Pseudoprimos de Carmichael.

○ Si Fermat ayuda a quitar las hirbas del camino, para luego cribarse deprisa,... con el Enfoque Estructural, el proceso de la cribación, sería en mucho menos compleja, al tener casi nada de hierbas que se infiltren, como probables y recién válidos "Pseudoprimos".

Spoiler (click para mostrar u ocultar)




Saludos Cordiales...
En línea
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 6.705



Ver Perfil
« Respuesta #74 : 17/08/2017, 10:11:39 am »


Buenas tardes, Víctor Luis.

Cita
• Aunque eso de la cribación,... no comprendo a qué metodología de primalidad se refiere.

Pues al igual que se criba al factorizar, se criba al mirar si los números son primos o no. Por ejemplo, tú tienes un método para saber cuáles son los números de Carmichael. Bien, ¿ese método los desenmascara directamente mediante una fórmula cerrada? Supongo que no, tendrás que comprobar cosas e ir descartando cosas probadas, aunque utilices de partida un primo “p” para hacer esas pruebas.

Una criba es un colador; o una red de pescar en la que la arena, y lo que no son los peces, lo que no se quiere, se cae por los agujeros quedando en la red sólo lo que interesa; y aquí los peces son los primos, en este caso concreto.

Un forma de que no fuera una criba es ésa, que tuvieras un polinomio, una fórmula cerrada con tres o cuatro cosas, donde al meter el número y hacer los cálculos (mediante suma, resta, multiplicación... de las variables) te diera soluciones A y B, queriendo decir una de ellas que es primo seguro o que no lo es.

Otra forma que no supondría una criba es la que te comenté para la factorización (forma hipotética, no sabemos si existe); construir el número, en este caso el primo en vez del semiprimo. Y claro, para que no sea una criba, tenemos que tener algo que no tenemos en las cribas; como saber la relación de orden que existe entre ese número probado y el primo a encontrar: si es más grande o si es más pequeño. Aunque esto, que sí sería propio para la factorización donde buscamos unos primos concretos, en el asunto de la primalidad ya no se ve tan claro; puesto que tomamos cualquier número y miramos si es primo o no, o si es un cierto primo en concreto.

Yo diría que una criba es un método que prueba números que no dan información (hasta que se da con lo que se busca, cuando toque encontrarlo). En el caso de los primos simplemente verificamos que  los números son compuestos y a raíz de eso los tiramos, no los usamos para acercarnos a un primo. Decimos “este es compuesto, fuera”, no decimos “este compuesto me indica que en el intervalo tal, y más o menos por el centro, hay un primo”. No, no nos dan una información de ese tipo, simplemente los tiramos y seguimos buscando. Pasa como con la arena que cae de la red, antes de caer no nos dice en qué zona están los peces, la arena no nos dice nada, sólo que ella no es un pez.

Si existiera algo así, tendríamos que probar muy poco, llegaríamos en seguida; es como ir por una calle que no hay nadie buscando una casa amarilla; no hay nadie, no podemos preguntar, sólo ir mirando las casas a ver cuándo vemos la de ese color, la cual, a lo mejor, está muy cerca, pero en uno de los muchos callejones y tapada por otras casas; con lo que tardamos en encontrarla.

Sin embargo, si en la calle hay gente del pueblo a la que preguntar, pues alguien dirá por dónde tenemos que ir. La pregunta viene a ser la misma que te hice para el caso de la factorización; ¿existe gente en el pueblo que nos pueda dar una información verdaderamente valiosa para no tener que recorrer casi toda las calles?

 Hasta ahora, que yo sepa, nadie ha visto un alma en los pueblos que ha visitado, pero a lo mejor es que la gente está metida en sus casas, el pueblo no tiene por qué ser un pueblo fantasma hasta que no se demuestre lo contrario.

Un cordial saludo.
En línea

Páginas: 1 2 3 [4]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.1 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!