Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Kongruenz mit großen Zahlen
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Kongruenz mit großen Zahlen
 
Autor Nachricht
mathmetzsch
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 03.05.2005
Beiträge: 56
Wohnort: Berlin

BeitragVerfasst am: 04 Dez 2005 - 14:53:22    Titel: Kongruenz mit großen Zahlen

Hallo,

ich habe hier eine Kongruenz zu lösen, bei der ich allerdings nicht so recht weiß wie:

1581^662597 mod(2537)=m

Wie bestimmt man m in diesem Fall? Ich kann das ja schlecht in den Taschenrechner eingeben. Hat jemand eine Idee?

Danke und viele Grüße.

Daniel
trinkMilch
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 19.06.2005
Beiträge: 228

BeitragVerfasst am: 04 Dez 2005 - 23:15:17    Titel:

Hi,

also es gibt einige kleine vereinfachungen...

z.B. gilt:

a^b mod m = (a mod m)^(b mod phi(m)) mod m

hier bei dir würde ich das soo machen, wenn ich es schriftlich machen muesste:

1581^662597 mod(2537)

= (1581 - 2537)^(662597 mod phi(2537)) mod 2357

= (-776)^(662597 mod 2356) mod 2357

= (-776)^561 mod 2357

nun koennte man so weitermachen....

1581^2 mod 2357 = (-776)^2 mod 2357 = 1141

(1581)^4 mod 2357 = 1141^2 mod 2357 = 817

(1581)^8 mod 2357 = 817^2 mod 2357 = 458

(1581)^16 mod 2357 = 458^2 mod 2357 = 2348 = -9

1581^32 mod 2357 = 2348^2 mod 2357 = (2348-2357)^2 mod 2357 = 81

1581^64 mod 2357 = 81^2 mod 2357 = 1847

1581^128 mod 2357 = (1847-2357)^2 mod 2357 = 830

1581^256 mod 2357 = 830^2 mod 2357 = 656

1581^512 mod 2357 = 656^2 mod 2357 = 1362

und nun:

1581^561 mod 2357 =
(1581^512 mod 2357) * (1581^32 mod 2357) * (1581^16 mod 2357)
*(1581^1 mod 2357) mod 2357

= (1362 * 81 * (-9) * 1581) mod 2357 = 2047
(natuerlich kann man nach jeder multiplikation noch einmal mod 2357
rechnen...)

somit: 1581^662597 mod(2537) = 2047


cu...
mathmetzsch
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 03.05.2005
Beiträge: 56
Wohnort: Berlin

BeitragVerfasst am: 05 Dez 2005 - 09:48:38    Titel: Danke

Vielen Dank. Hast mir sehr geholfen!

VG Daniel
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Kongruenz mit großen Zahlen
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