Construcción de números de caso de prueba de primalidad de Miller-Rabin de tamaño arbitrario

Question

El de Miller–Rabin (o de Rabin-Miller) prueba de primalidad es un algoritmo que determina si un número dado es primo.

Es posible construir una serie que pasará a un número arbitrario de Miller-Rabin y Rabin-Miller rondas de pruebas?

Esta Generación de Números Primos Informe papel de la prueba los números que pasan de 20 rondas del SR.

Me gustaría que un método general el número de la prueba que puede pasar a $n$ (por ejemplo, $n = 50$) rondas, si tal cosa es posible.

Gracias por la ideas.

Answer 1

La pregunta es un poco desacertado. Miller Rabin utiliza una combinación de Fermat Poco y Teorema Chino de la División Teorema de la promesa de que una falsa principal para cualquier número no es devuelto con una probabilidad de más del 25%. Así que para cualquier número compuesto al menos 3 intentos de 4 con una sola prueba que el SEÑOR le informe como compuesto. http://rosettacode.org/wiki/Talk:Carmichael_3_strong_pseudoprimes,_or_Miller_Rabin%27s_nemesis#Analysis examina el comportamiento de un rango de números. Tenga en cuenta que para 703 (19*37) SEÑOR le informe como, posiblemente, el primer 22.86% del tiempo con 1 trate. Así que con 10 intentos, se le informe de forma incorrecta 1 en un millón de veces. Ver http://rosettacode.org/wiki/Talk:Miller-Rabin_primality_test. Tenga en cuenta que para la mayoría de los compuestos de la probabilidad es mucho menor que 25%. Así que la respuesta es que encontrar un número que cumple con su requisito es simple. Cualquier prime va a hacer, no compuesto de voluntad. Creo que la confusión es que el documento sugiere que estos siete números compuestos. Dong wong es que no lo son. Las posibilidades de encontrar un SEÑOR pseudoprime es la misma como la búsqueda de la izquierda en plesiosaurio en el Lago Ness, ambos son míticos. Dong no encontrar 7 para su proyecto de clase, estos números son primos.

Answer 2

D=4*3*5*7*11*13*17*19*23*29*31*37*41*43*47*53*59*61*67*71*73*79*83*89*97

P=3864905207490318811+ i * D - donde i=0,1,2,3...

Q=37*P-36

R=41*P-40

si P, Q, R son todos los números primos (PEPRI-2 en la práctica), que N=P*Q*R se puede ser un fuerte pseudoprime para todos los (25) el primer bases por debajo de 100 -, pero no es al azar bases, que usa el SEÑOR de la prueba.

Ejemplos: i= 0, 2896, 3246, 5745, 6128, 8134, 9402, 10075, ...

o P=41837477983818300631+ i * D , Q=13*P-12 , R=17*P-16 , i=0, 645, 1469, 2744, 3186, 3713,...

Answer 3

@Amzoti: Es difícil de explicar, yo no soy matemático, pero estoy tratando de... Me genera una tabla para este triple (1,37,41) con posible resto de los pequeños números primos:

n mod p:

3:[ 1] 0

5:[ 2] 0 1

7:[ 2] 0 2

11:[ 3] 0 5 7

13:[ 2] 0 10

17:[ 4] 0 1 10 13

19:[ 5] 0 7 12 16 17

23:[ 6] 0 13 15 17 19 21

29:[ 7] 0 4 11 13 15 17 25

31:[ 7] 0 2 4 8 14 17 25

37:[ 1] 8

41:[ 1] 30

43:[10] 0 6 7 15 18 20 23 29 35 39

... y así sucesivamente. Y n+1, 37n+1, 41n+1 debe ser un primo.

Detalles: ZHENXIANG ZHANG:ENCONTRAR C3-FUERTE PSEUDOPRIMES

Otro ejemplo de número: 2809386136371438866496346539320857607283794588353401165473007394921174159995576890097633348301878401799853448496604965862616291048652062065394646956750323263193037964463262192320342740843556773326129475220032687577421757298519461662249735906372935033549531355723541168448473213797808686850657266188854910604399375221284468243956369013816289853351613404802033369894673267294395882499368769744558478456847832293372532910707925159549055961870528474205973317584333504757691137280936247019772992086410290579840045352494329434008415453636962234340836064927449224611783307531275541463776950841504387756099277118377038405235871794332425052938384904092351280663156507379159650872073401637805282499411435158581593146712826943388219341340599170371727498381901415081480224172469034841153893464174362543356514320522139692755430021327765409775374978255770027259819794532960997484676733140078317807018465818200888425898964847614568913543667470861729894161917981606153150551439410460813448153180857197888310572079656577579695814664713878369660173739371415918888444922272634772987239224582905405240454751027613993535619787590841842251056960329294514093407010964283471430374834873427180817297408975879673867

(1189 dígitos)

Este número es un fuerte pseudoprime para todos (168) primer bases por debajo de 1000. Es un número de Carmichael también, con el mismo formato.

Reg.: Joe53

Answer 4

197475 704297076 769879318 479365782 605729426 528421984 294554780 711762857 505669370 986517424 096751829 488980502 254269692 200841641 288349940 843678305 321105903 510536750 100514089 183274534 482451736 946316424 510377404 498460285 069545777 656519289 729095553 895011368 091845754 887799208 568313368 087677010 037387886 257331969 473598709 629563758 316982529 541918503 729974147 573401550 326647431 929654622 465970387 164330994 694720288 156577774 827473110 333350092 369949083 055692184 067330157 343079442 986832268 281420578 909681133 401657075 403304506 177944890 621300718 745594728 786819988 830295725 434492922 853465829 752746870 734788604 359697581 532651202 427729467

(618 dígitos)

Este número es un fuerte pseudoprime para todos (100) primer bases de hasta 541. Es un número de Carmichael con 3 factores primos, con formato: N = (n+1)(37n+1)(41n+1)

Reg.: Joe53