Fermatischer Primzahltest < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Keine Spezifische Aufgabe |
Hallo, ich lese gerade einen kurzen Absatz über den Fermatischen Primzahltest.
Dabei wird folgendes Beispiel aufgeführt
Nehmen wir x = 2, wir wollen zeigen, dass [mm] 2^{38} \not= [/mm] 1 mod 39.
[mm] 2^{38} [/mm] = [mm] 2^{36+2} [/mm] mod 39
= [mm] (2^{6})^{6} 2^{2} [/mm] mod 39
Wir rechnen [mm] 2^{6} [/mm] mod 39 = 64 mod 39 = 25 mod 39 und [mm] 26^{2} [/mm] mod 39 = 625 mod 39 = 1 mod 39, so dass [mm] 25^{6} [/mm] mod 39 = 1 mod 39 folgt
Daraus erhalten wir [mm] 2^{38} [/mm] mod 39 = [mm] (2^{6})^{6} 2^{2} [/mm] mod 39 = (1*4) mod 39 = 4 mod 39 [mm] \not= [/mm] 1 mod 39.
Infolge wird ausgiebig die Möglichkeit besonders große Zahlen auf diese Art zu berechnen gelobt. Leider aber kein Beispiel aufgezeigt. Nun habe ich mich sowohl selbst daran versucht, als auch ein entsprechend ausführliches Beispiel online gesucht.
Leider bekomme ich das selbst nicht hin und bei meiner Suche kam ich nur auf Beispiele mit kleineren Zahlen,oder auf solche die nicht ausführlich gezeigt werden.
Villeicht kann mir hier ja jemand einen Link geben, der den Vorgang mit einer größeren Zahl in aller Ausführlichkeit zeigt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:20 So 19.06.2016 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
