Pseudocode in c++. Ich schaffs nich.
-
Wie sieht diese Funktion in c++ aus?
http://highered.mcgraw-hill.com/sites/dl/free/0070131511/25346/witness.gifVorallen Dingen macht mir die Funktion Modular-Exponention Probleme.
Und ein paar Dinge wie "xi <-- xi-1² mod n"
Das ist mir zu hoch.Ich weiß das ist so ein Post in der Form "Mach mal" aber ich weiß es nicht besser. Danke!
Der code ist von http://highered.mcgraw-hill.com/sites/0070131511/student_view0/chapter31/algorithm_pseudocode.html#
-
witness(a,n) let n-1 = 2^t*u, where t>=1 and u is odd x0 <- modular_exponentiation(a,u,n) for i <- 1 to t do x(i) <- x(i-1)^2 mod n if x(i) = 1 and x(i-1) != 1 and x(i-1) != n-1 then return true if x(t) != 1 then return true return falseerstmal t und u rausfinden.
n-1 soll 2^t*u sein. dann nehme ich mal an, witness
soll nicht für ungerade zahlen aufgerufen werden.
ne gerade zahl n-1 kann man immer so lange durch 2 teilen, bis was
ungerades rauskommt. den rest dann nenne ich u.
also sowas:int t=0,u=n-1; while(u%2!=0){ u/=2; ++t; }haste ne schnelle funktion, die das erste auf 1 gesetze bit in einem wort
findet, würde ich die einsetzen, um die eventuell lange schleife zu sparen.inline u32 findFirstBitTrue(u32 data) { __asm bsf eax,dword ptr[data]; };hier wähle ich typedef unsigned __int32 u32 und verwende ab dann nur noch u32, um
sicher zu gehen, daß die sachen, wo ich ein wenig schummle, auch auf anderen comilern
laufen.u32 u=n-1; u32 t=findFirstBitTrue(u); u>>=t;so, wir haben t und u. nun zu modexp.
zum exponentieren führe ich erstmal ein rekursives exp ein.
int exp(int b,int e){ if(e==0) return 1; return exp(b,e-1)*b; }kein trick: b hoch e ist gleich b hoch (e-1) mal b
und dann fastexp
int exp(int b,int e){ if(e==0) return 1; if(e%2==0) return exp(b,e-1) hoch 2; return exp(b,e-1)*b; }trick: wenn der exponet gerade ist, kann ich
b^e schreiben als (b2)(e/2)
womit ich in der rekursion den exponenten halbiere.
damit geht b^e ausrechnen statt in e multiplikationen jetzt
in log(e) multiplikationen.und dann fstexpmod
int exp(int b,int e,int m){ if(e==0) return 1; if(e%2==0) return exp(b,e-1) hoch 2 mod m; return exp(b,e-1)*b mod m; }trick: statt b^e zuerst auf 1000000 stellen auszurechnen und dann
erst mod m zu rechnen, kann ich auch nach jeder teilrechnung schnell mod m rechnen.
dadurch brauche ich überhaupt keine langen zahlen.nachdem der trick rekursiv kapiert wurde, geht auch ne iterative version, weil
leicht schneller.u32 powMod(u32 base,u32 exp,u32 modul) {//rechnet 'base hoch exp mod modul' u32 a1=base,z1=exp,x=1,m=modul; while(z1!=0){ while((z1%2)==0){ z1/=2; a1=mulMod(a1,a1,m); } --z1; x=mulMod(x,a1,m); } return x; }mulMod hat ein problem. das zwischenergebnis ist 64-bittig.
also entweder:inline u32 mulMod(u32 a,u32 b,u32 m){ return u64(a)*b/m; }oder gleich zaubern
inline u32 mulMod(u32 a,u32 b,u32 m){ _asm mov eax,dword ptr a //eax=a _asm mov esi,dword ptr b //esi=b _asm mov edi,dword ptr m //edi=m _asm mul esi //edx:eax=esi*eax _asm div edi //eax R edx=edx:eax/edi _asm mov eax,edx //eax=edx }war sonst was unklar?
-
Volkard, du bist ein Monster
-
...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. Erstens:
[cpp]
int t = 0, u = n - 1;
while(u % 2 == 0){ // <-- Tipfeeler.
u /= 2;
++t;
}
[/cpp]
Was fastexp angeht, das ist auch wieder Pseudocode, und noch dazu buggy (ts, ts):
[cpp]
int exp(int b,int e){
if(e == 0)
return 1;
if(e % 2 == 0) {
int x = exp(b, e / 2);
return x * x;
}
return exp(b, e - 1) * b;
}
[/cpp]
In exp/mod-Viech dasselbe, und ein paar Parameter fehlen:int exp(int b,int e,int m){ if(e == 0) return 1; if(e % 2 == 0) { int x = exp(b, e / 2, m); return x * x % m; } return exp(b, e - 1, m) * b % m; }...und in mulMod statt / ein % (Ich bin in Assembler nicht so fit, aber ich glaube, da ist der Fehler auch):
inline u32 mulMod(u32 a,u32 b,u32 m){ return u64(a) * b % m; }Was die Prozedur angeht -
bool witness(int a, int n) { //sonst hat das mit exp(2, t) * u == n - 1, t >= 1, u % 2 == 1 nicht hin assert(n > 2 && n % 2 != 1); int t, u, *x = new int[t + 1]; // n - 1 >> t ist dasselbe wie (n - 1) / exp(2, t) - google nach bitshifting for(t = 1; (n - 1 >> t) % 2 == 0; ++t); u = (n - 1) >> t; 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; } } delete x; return x[t] != 1; }Das ist jetzt ne ziemlich genaue Abschrift des Codes, deswegen gut übertragbar. Eigentlich käme man auch ohne dynamisch angeforderten Speicher klar, aber so ist es für das Verständnis sinnvoller, denke ich.
-
Autsch, autsch, autsch, ich bin ein Idiot. Natürlich:
[cpp]
bool witness(int a, int n) {
//sonst hat das mit exp(2, t) * u == n - 1, t >= 1, u % 2 == 1 nicht hin
assert(n > 2 && n % 2 != 1);int t, u, *x = new int[t + 1];
// n - 1 >> t ist dasselbe wie (n - 1) / exp(2, t) - google nach bitshifting
for(t = 1; (n - 1 >> t) % 2 == 0; ++t);
u = (n - 1) >> t;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;
}
}bool ret = x[t] != 1;
delete x;
return ret;
}
[/cpp]
Ich kann ja nicht erst etwas freigeben und danach darauf zugreifen...
-
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; }
