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-ZahlenPor 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í
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]
Saludos.