Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Kann jemand "repeated squaring" ?
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Kann jemand "repeated squaring" ?
 
Autor Nachricht
eshi91
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 21.06.2004
Beiträge: 32

BeitragVerfasst am: 10 März 2005 - 21:37:15    Titel: Kann jemand "repeated squaring" ?

Hallo Leute,
hänge wieder..
Ich brauche für RSA dieses repeated squaring um z.B.: 34^61 mod 72 zu berechnen.... aber wie geht das ?

Ich habe den exponent in bin. umgestellt 61 = 111101
Und jetzt finde ich nicht den richtigen Weg weiter.... meine Versuche bringen das falsche Resultat....

Was nun ?

vielen Dank für Euere Hilfe
Andromeda
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 10.12.2004
Beiträge: 1849
Wohnort: Tübingen

BeitragVerfasst am: 10 März 2005 - 22:24:20    Titel:

Das bekomme ich heraus:



Gruß
Andromeda
eshi91
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 21.06.2004
Beiträge: 32

BeitragVerfasst am: 11 März 2005 - 00:19:04    Titel: Danke, habe aber noch eine winzige Frage dazu...

Nochmals vielen Dank.
Zu Deinem Beispiel hätte ich noch eine kleine Frage:
61 = 111101
aber bei Dir fehlt ein Bit und Du schreibst
61 = 11101 = 1+4+8+16+32
Kannst Du mir bitte diese Zeile noch mal erklären ?
Erstens warum du ein Bit "verschluckst" und zweitens wie das gemacht wird mit 1+4+8+16+32 ?

Ist das nicht so:
2^0, 2^1, 2^2, 2^4, 2^8, 2^16 ?

Es wird mir langsam alles klar, bis auf diese kleine Sache Laughing

Vielen Dank.
Es ist für mich eine große Hilfe.
Andromeda
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 10.12.2004
Beiträge: 1849
Wohnort: Tübingen

BeitragVerfasst am: 11 März 2005 - 00:47:09    Titel: Re: Danke, habe aber noch eine winzige Frage dazu...

eshi91 hat folgendes geschrieben:

61 = 111101
aber bei Dir fehlt ein Bit und Du schreibst
61 = 11101 = 1+4+8+16+32
Kannst Du mir bitte diese Zeile noch mal erklären ?
Erstens warum du ein Bit "verschluckst" und zweitens wie das gemacht wird mit 1+4+8+16+32 ?

Ist das nicht so:
2^0, 2^1, 2^2, 2^4, 2^8, 2^16 ?


Da ist mir oben ein Schreibfehler unterlaufen, der sich aber in der weiteren Rechnung nicht wieterzieht. Es fehlt eine 1

61 = 111101

Es gilt nicht

2^0, 2^1, 2^2, 2^4, 2^8, 2^16 sondern
2^0, 2^1, 2^2, 2^3, 2^4, 2^5 =
1 + 2 + 4 + 8 + 16 + 32

Aber man muss von rechts anfangen zu zählen, da das niedrigste bit rechts steht.

11101 = 1*2^5 + 1*2^4 + 1*2^3 + 1*2^2 + 0*2^1 + 1*2^0

= 32 + 16 + 8 + 4 + 1 = 61

Das 2. bit ist 0, sonst gibt es ja auch in der Summe keine 61.

Dann musst du entsprechend der Formel alle einzelnen modulo berechnen.

Bei höheren Zahlen, zum Beispiel a^8 kannst du das Ergebnis von a^4 nehmen, quadrieren und davon wieder modulo bilden.

Dann nimmt man das Produkt aller Ergebnisse und bildet davon wieder modulo.

Gruß
Andromeda
upb
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 15.03.2005
Beiträge: 18

BeitragVerfasst am: 15 März 2005 - 12:01:57    Titel:

Dies ist ein Lösungsweg auf für hohere Potenzen

Zitat:

34^61 mod 72

61 = 1 a1=1 a2=1 a3=1 a4=0 a5=1

a1= 34² = 1156 mod 72 = 4 und 4*34= 136 mod 72=64
a2= 64² = 4096 mod 72 = 64 und 64*34=2176 mod 72=16
a3= 16² = 256 mod 72 = 40 und 40*34=1360 mod 72=64
a4= 64² = 4096 mod 72 = 64
a5= 64² = 4096 mod 72 = 64 und 64*34=2176 mod 72=16


MfG

upb die Eliteuni
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Kann jemand "repeated squaring" ?
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum