Zitat von
3_of_8:
Das hatten wir vor kurzem schon mal. Such einfach nach "Diskrete Exponentialfunktion". Da ist ein schöner, langer Beitrag von mir mit einem Beispiel.
EDIT: Ich hab heute gute Laune und geb dir deshalb gleich den Link:
http://www.delphipraxis.net/internal...=675294#675294
Zitat von
3_of_8:
Code:
function discreteExponent(b, x, m: Integer): Integer;
begin
result:=1;
while x>0 do
begin
if x and 1=1 then Result:=Result*b mod m;
b:=[b](b*B)[/b] mod m;
X:=x div 2;
end;
end;
Bei 299^173 MOD 481 geht das noch gut, wenn man allerdings (wie bei RSA so ueblich ist) mit grossen Zahlen rechnet, duerfteste mit der Funktion ziemlich dumm aussehn.
In einer sache hast du aber recht: sowas hatten wir letztlich schon:
*klick*
D.h. eigentlich wie alci schon geschrieben hat:
Code:
(a ^ b) % c = ((a^(b-1) % c) * (a % c)) % c
vllt. stell ich heut noch ne nicht-rekursive Gleichung dafuer auf.
greetz
Mike