Autor Beitrag
Moony
ontopic starontopic starontopic starontopic starontopic starofftopic starofftopic starofftopic star
Beiträge: 97

Win XP
D7 Prof
BeitragVerfasst: Mi 14.03.07 12:24 
Morgen,
also ich habe folgendes Problem. Für die Schule muss ich RSA programmieren. Das klappt soweit auch. Mein Problem ist jetzt, dass der Rechner bei hohen Zahlen streikt.
Beispiel 89^77 mod 221.
Bei dieser Rechnung soll ich mit Restklassen arbeiten. Was eine Restklasse ungefähr ist, habe ich mir schon angeschaut und auch einigermaßen verstanden. Aber wie zerteile ich 89^77 so, dass der Rechner es rechnen kann. Schon einmal vielen Dank, falls jemand antwortet.
Moony

_________________
Leben ist ein informationsgesteuerter, hochkomplexer Ordnungszustand der Materie mit der Fähigkeit zur Selbstorganisation und Selbstreproduktion!
ub60
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 764
Erhaltene Danke: 127



BeitragVerfasst: Mi 14.03.07 19:31 
Hier nur mal eine kleine Hilfe:

für 89^77 mod 221:

1. nimm Produkt=1
2. rechne Produkt=Produkt*89
3. wenn Produkt>=221, nimm Produkt=Produkt mod 221 (also nur mit dem Rest weiterrechnen)
4. und das Ganze 77 mal (natürlich ab Zeile 2)

ub60
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Mi 14.03.07 19:42 
Hallo,

89^77 mod 221 = (89 mod 221 * 89) mod 221)* 89) mod 221)* 89) mod 221)...

Zum Potenzieren von Zahlen mit ganzzahligem Exponenten gibt es natuerlich Abkuerzungen ...
www.webplain.de/fore...hp?1,885,898#msg-898

Ich gehe davon aus, dass 0<Bas < Modulus < 2^16 ist.

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
function BasPotMod (Bas,Pot,Modulus :integer):integer;
var
  Quadrat : integer;
begin
  Quadrat := Bas ;
  Result := 1;
  While Pot <> 0 do
    begin
    if Odd(Pot) then
    {Falls Exponent ungerade dann}
      Result= (Result * Quadrat) MOD Modulus;
    Quadrat = (Quadrat * Quadrat) MOD Modulus;
    shr(Pot,1);  {Exponent = Exponent div 2}
    end{while}
end;


Man kann aber Quadrat auch durch Bas ersetzen und braucht überhaupt keine Variable mehr in der Funktion deklarieren und kann das schon inlinen(auf deutsch ?).

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
function BasPotMod (Bas,Pot,Modulus :Cardinal{Dword}):integer;
begin
Result := 1;
While Pot <> 0 do
  begin
  if Odd(Pot) then
    Result:= (Result * Bas) MOD Modulus;
  Bas :=  (Bas * Bas) MOD Modulus;
  Pot := Pot shr 1;  {Exponent = Exponent div 2}
  end{while}
end;


Gruß Horst

P.S. Der Rechner von Windows im Zubehör rechnet sogar 89^77 Mod 221 mit dem Ergebnis 72.
P.S.S. Hoffe es hilft noch..
IngoD7
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 629


D7
BeitragVerfasst: Mi 14.03.07 19:56 
Klingt irgendwie etwas komplizierter als es ist. ;)

Aufgrund gültiger Restklassenarithmetik sind folgende Ausdrücke identisch. Dabei nehme ich zur besseren Veranschaulichung als Exponent 4 anstatt 77:

(89^4) mod 221
= 62742241 mod 221
= 120

( ((89 * 89) mod 221) * ((89 * 89) mod 221) ) mod 221
= ( (7921 mod 221) * (7921 mod 221) ) mod 221
= (186 * 186) mod 221
= 34596 mod 221
= 120

( ((89^2) mod 221) * 89 * 89 ) mod 221
= ( (7921 mod 221) * 89 * 89 ) mod 221
= (186 * 89 * 89) mod 221
= 1473306 mod 221
= 120

Genug der Beispiele. Es sollte deutlich werden, dass zu jedem Zeitpunkt der Multiplikationen (also zwischendurch) ein Zwischenergebnis modulo 221 genommen werden kann, um die Zwischenergebnisse klein zu halten.

Auf die Eingangsfrage bezogen bedeutet das, dass man die 89 nicht erst 77 mal mit sich selbst multiplizieren und erst dann modulo 221 nehmen muss, sondern man kann jederzeit schon die Zwischenergebnisse modulo 221 nehmen. Dadurch hält man die Zahl klein und für den Computer "handlich".

Das kann man auf die Spitze treiben, indem man das nach jedem Multiplikationsschritt macht:
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
function MonsterMod(aBas, aExp, aMod : integer) : integer;
var 
   i : integer;
   E : integer;
begin
   E:=aBas;
   for i := 2 to aExp do
      E:=(E*aBas) mod aMod;
   Result:=E;
end;

//Aufruf mit
MySolution := MonsterMod(89,77,221);


//Nachtrag:
Wie witzig ... erst schreibt keiner, dann Alle. :)
Man sollte, während man ein Posting verfasst, nicht zwischendurch ans Telefon gehen. ;)
Moony Threadstarter
ontopic starontopic starontopic starontopic starontopic starofftopic starofftopic starofftopic star
Beiträge: 97

Win XP
D7 Prof
BeitragVerfasst: Do 15.03.07 00:33 
HVALA. :flehan: VIELEN LIEBEN DANK *Sternchenaugen*. ES LEBT!!! :dance2: Wie putzig es das mit den Restklassen kann :P
*jedem nen Stück Kuchen durch die Leitung schieb*

_________________
Leben ist ein informationsgesteuerter, hochkomplexer Ordnungszustand der Materie mit der Fähigkeit zur Selbstorganisation und Selbstreproduktion!