V
0xdeadbeef schrieb:
...und schludrig noch dazu Im Pinzip alles richtig, aber ich merz grad noch mal die Flüchtigkeitsfehler aus - solche Dinger sind für das Verständnis tödlich.
jetzt bin ich sicher, daß du es kapiert hast.
für die hauptfunktion verwende kein array.
du brauchst nur zugriff auf die letzen beiden werte.
x[0] = exp_mod(a, u, n); //exp_mod sei gegeben - siehe oben.
for(int i = 1; i <= t; ++i) {
x[i] = x[i - 1] * x[i - 1] % n;
if(x[i] == 1 && x[i - 1] != 1 && x[i - 1] != n - 1) {
delete x;
return true;
}
}
wird zu (achtung, schludrig):
x = exp_mod(a, u, n); //exp_mod sei gegeben - siehe oben.
for(int i = 1; i <= t; ++i) {
xalt=x;
x = x * x % n;
if(x == 1 && xalt != 1 && xalt != n - 1) {
return true;
}
}
was macht die funktion eigentlich?
edit: sie scheint auf strong probable primes zu prüfen.
aber ist dazu nicht dieser code äquivalent? sieht nach ner schnelleren schleife aus.
bool witness(int a,int n){
int u=n-1;
int t=findFirstBitTrue(u);
u>>=t;
int x=powMod(a,u,n);
if(x==1) return true;
if(x==n-1) return true;
for(int i=0;i<t;++i){
x=mulMod(x,x,n);
if(x==n-1) return true;
}
return false;
}
