Forums Neueste Beiträge
 

Carmichael-Zahlen

01/09/2013 - 21:00 von mock | Report spam
Miller-Rabin Test

Ich habe gerade festgestellt, dass der Miller-Rabin-Test bei grossen Zahlen doch recht ungenau ist. Bei PARI habe ich keinen gefunden, also eben selbst geschrieben:

-

/* modulare Potenzierung */
modexp(zhl,xpnt,mdl)={
res=1;binx=binary(xpnt);
for(i=1,matsize(binx)[2],res=res*res%mdl;if(binx[i],res=res*zhl%mdl));
return(res)
}

-

/* Miller-Rabin */
mr(zhl,zkl)={
p=1;
if(zhl<4,if(zhl>1,return(p),return(0)));
if(!zkl,zkl00000);
for(i=1,zkl,j=random(zhl-3);if(modexp(j+2,zhl-1,zhl)!=1,p=0;break()));
return(p)
}

-

Ich habe mal einen Test mit einer Carmichael-Zahl gemacht

cmz$40452197204694952316132995729

und der ging leider in die Hose:

? i=0;while(i++,if(mr(cmz,1000000),print(i);break()))
1

Das Problem mit Carmichael-Zahlen ist bekannt, aber bei, sagen wir, 2048-Bit-Zahlen, könnte die Anzahl der Carmichael-Zahlen ins Gewicht fallen, weil die steigt, wohingegen die Primzahldichte sinkt.

Ist das Verhàltnis schon mal untersucht worden?
 

Lesen sie die antworten

#1 mock
01/09/2013 - 21:37 | Warnen spam
Am Sonntag, 1. September 2013 21:00:51 UTC+2 schrieb mock:

Ist das Verhàltnis schon mal untersucht worden?



Ich muss mich korrigieren. Nach noch nicht eingehenderer Untersuchung scheint es doch so zu sein, dass die Carmichael-Zahl-Dichte stàrker abnimmt als die Primzahldichte. Was ja auch einleuchtend ist, wenn man die Chernicksche Methode ansieht.

Trotzdem besteht das Problem bei RSA-Primtests, weil aus Perfomancegründen keine deterministischen Tests verwandt werden. So wàre bspw. eine Hintertür einzubauen, wenn der "Zufallsgenerator" gezielt Carmichael-Zahlen produziert.

Ähnliche fragen