nicht angemeldet
Hallo Henryk,
Wobei man Potenzen von 2 natürlich nicht über die Multiplikation sondern über Bitoperationen ausrechnet: pow(2,x) == 1 << x
Da man aber die Modulooperation immer noch dazwischen schieben muss, hilft einem das nicht viel. In dem Algorithmus gibt es ja nur eine Multiplikation mit 2.
Man könnte natürlich einfach n mal mit 2 Multiplizieren, aber da hat man dann n Modulos und Shifts, wärend man so nur lg(n) hat.
So lang man mit longs rechnet, ist das in etwa gleich schnell. Wenn man mit größeren Zahlen rechnen will, wirkt sich das aber auch, da die Rechenoperationen dann natürlich auch deutlich langsamer sind.
Vorsicht! So kann man nicht auf Primzahlen testen. Das Programm würde behaupten dass 561 (die erste Carmichael-Zahl) eine Primzahl ist, obwohl 561 = 3·11·17.
Vermutlich handelt es sich eh nur um eine Spielerei, dass das für Verschlüsselung nicht taugt, steht ja auch in dem angegebenen Wikipediaartikel.
Ich wollte nur demonstrieren, dass man solche Probleme nicht durch mehr Rechenpower oder Assemblertrickserreien löst.
Grüße
Daniel