Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Bestimmen Sie die letzten beiden Ziffern von 2^751

Bestimmen Sie die letzten beiden Ziffern von 2^751

Universität / Fachhochschule

Elementare Zahlentheorie

Kryptologie

Teilbarkeit

Tags: Elementare Zahlentheorie, Kryptologie, Teilbarkeit

platofan23 aktiv_icon

23:42 Uhr, 27.04.2020

Hallo Leute,

ich bin gerade am Uni-Mathe lernen

(1

Semester). Ich habe jetzt die Aufgabe wie Sie im Titel steht und will nur überprüufen, ob ich alles richtig gemacht habe.

Die Rechnung sieht man im Bild. Wäre auch offen für Verbesserungsvorschläge.
Ergänzend zum Rechnungsweg wäre es nett nochmal zu erklären, warum man den ggT bilden muss und warum man die Eulerische Phi-Funktion nutzen muss. Mir wurde es leider nicht so genau erklärt und ich habe mir das meiste durch Internetrechere selbst beibringen müssen.

Gruß
Platofan23

PS:Es werden noch ein paar Fragen kommen. Freue mich über freundliche Zusammenarbeit

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

HAL9000

07:13 Uhr, 28.04.2020

> warum man die Eulerische Phi-Funktion nutzen muss.

Man muss sie nicht nutzen, aber sie hilft eben bei der Reduktion des Exponenten auf erträgliche Werte, in der dargestellten Weise. Du kannst sie auch links liegen lassen und die kompletten Potenzen berechnen.

Ich stelle mal einen etwas anderen, weniger rechenlastigen Lösungsweg vor:

Gemäß Euler-Fermat ist

2^{φ (25)} = 2^{20} \equiv 1 mod 25

, das ergibt auch

2^{10} \equiv \pm 1 mod 25

(d.h. eins von beiden), ein genaueres Nachrechnen ergibt nun

2^{10} = 1024 \equiv - 1 mod 25

.

Damit bekommen wir

2^{751} = {(2^{10})}^{75} \cdot 2^{1} \equiv (- 1)^{75} \cdot 1 = - 2 mod 25

, und für

a \equiv 2^{751} mod 100

bleibt dann wegen

a \equiv 0 mod 4

nur noch diejenige der Varianten

- 2 + 25 k

mit k=0,1,2,3 übrig, welche durch 4 teilbar ist. Das tritt für k=2 ein, und es ist dann

a = - 2 + 2 \cdot 25 = 48

anonymous

09:53 Uhr, 28.04.2020

Oder - ein pragmatischer Weg:
Wir wissen ja:

2^{2} = 04

2^{3} = 08

2^{4} = 16

Wenn man das mal so weiter treibt, dann kommt schnell die Ahnung auf, mehr als

100

Kombinationen für die Endziffern sind wohl nicht möglich - nein sogar nur

50

geradzahlige.
Und siehe an, schon nach

20

Durchläufen kommt man wiederum zur Endziffengruppe:

2^{22} \to

Endziffern

04

2^{23} \to

Endziffern

08

2^{24} \to

Endziffern

16

Und wer noch weiß, wie man mit Papier und Bleistift multipliziert, der weiß noch, dass man anfängt, die letzte Ziffer zu multiplizieren, ggf. einen Übertrag macht, dann die nächste Ziffer multipliziert,

u . s . w ., u . s . w

.
Wenn also die letzten zwei Endziffern bekannt sind, dann sind auch die letzten beiden Ziffern des Doppelten schnell bekannt.

D . h

. die Endziffernfolge ist periodisch, mit einer Periode von

20

.

Da

2^{751} = 2^{20 \cdot 37 + 11}

wird also

2^{751}

die gleiche Endzifferngruppe haben, wie

2^{11}

und das ist bekanntlich

2048

platofan23 aktiv_icon

12:03 Uhr, 28.04.2020

Den letzten Schritt verstehe ich, aber warum nutzt du 2^φ(25)und nicht φ(100)welches es normal sein müsste, da ja die letzten zwei Stellen gesucht werden. Der Ansatz ist doch im Prinzip der Satz von Euler?

HAL9000

12:14 Uhr, 28.04.2020

Die Frage geht wohl an mich:

Die Bestimmung von

a \equiv 2^{751} mod 100

kann wegen

100 = 2^{2} \cdot 5^{2}

auch geschehen als Lösung des KongruenzSYSTEMS

a \equiv 2^{751} mod 2^{2}

und

a \equiv 2^{751} mod 5^{2}

. Ersteres ergibt trivialerweise

a \equiv 0 mod 4

, während die Lösung von

a \equiv 2^{751} mod 25

in der von mir beschriebenen Weise stattfindet. Zum Schluss müssen die beiden Lösungen

a \equiv 0 mod 4

und

a \equiv - 2 mod 25

zu der einen Lösung modulo 100 zusammengefügt werden (Stichwort: Chinesischer Restsatz).

D.h., man teilt erst das Gesamtmodul 100 auf, löst die Einzelkongruenzen der dann zahlentheoretisch "einfacheren" Module, und fügt zum Schluss alles per Chinesischem Restsatz zum Originalmodul wieder zusammen. Das ist nicht immer nötig bzw. die beste Variante, aber im vorliegenden Fall sehe ich es schon als ganz passablen Weg an.

platofan23 aktiv_icon

12:45 Uhr, 28.04.2020

achsoo. Kannst du mir sagen für was man immer noch den ggT berechnen soll. Ich habe es so verstanden, dass man damit prüft ob der Teiler eine Primzahl ist. Wenn es keine wäre dürfte man die Phi-Funktion dann ja nicht anwenden.

HAL9000

13:55 Uhr, 28.04.2020

> Ich habe es so verstanden, dass man damit prüft ob der Teiler eine Primzahl ist. Wenn es keine wäre dürfte man die Phi-Funktion dann ja nicht anwenden.

Ja, das sehe ich auch als Grund an. D.h., der Euler-Fermat

a^{φ (100)} \equiv 1 mod 100

darf auf

a = 2

hier NICHT angewandt werden.

[Übrigens ein weiterer Vorteil meiner Betrachtung, zumindest was den Modulteil 25 betrifft: Dort herrschte die nötige Teilerfremdheit ggT(2,25)=1.]

platofan23 aktiv_icon

14:22 Uhr, 28.04.2020

Das müsste, dann auch heißen das meine Rechnung falsch ist oder bzw. auch nicht weil ich ja nicht direkt den Eulersatz verwendet habe...

HAL9000

15:10 Uhr, 28.04.2020

Ja, jetzt wo du es sagst, fällt es mir auch auf:

In der Rechnung oben taucht irgendwann

2^{40} \equiv 76 mod 100

auf. Das ist zweifelsohne richtig, nur fällt es ein wenig vom Himmel, d.h., es wird nicht näher erklärt, wie der Wert zustande kam - das kann mehr oder weniger aufwändig geschehen sein...

Das weitere ist dann schon klarer: Wegen

7 6^{2} \equiv 76 mod 100

gilt dann für alle Potenzen

2^{40 k} \equiv 76 mod 100

, sofern

k \geq 1

. (*)

P.S.: Eine einfache Erklärung wäre

2^{20} \equiv {(2^{10})}^{2} = 102 4^{2} \equiv 2 4^{2} = 576 \equiv 76 mod 100

, und dann greift das Argument (*).

platofan23 aktiv_icon

15:31 Uhr, 28.04.2020

ja gut. ich versuche das immer über

z.B

2^450 mod 100=2^3*150 mod 100=(2^150)^3 mod 100 = (2^150 mod 100)^3 mod 100= 24 mod 100

zu erklären. Also das der Teil der in der Klammer steht immer modulo gerechnet und aufgeteilt wird.

Es gibt ja immer mehrere Wege nach Rom :-D)

HAL9000

15:32 Uhr, 28.04.2020

Hab mir gerade folgendes überlegt: Es gibt ja vom Kleinen Fermat zwei gebräuchliche Fassungen:

1)

a^{p - 1} \equiv 1 mod p

für alle nicht durch

p

teilbaren

a

,

2)

a^{p} \equiv a mod p

für ALLE

a

.

Hab mir gerade überlegt, wie man auch eine entsprechende Analogie für den Euler-Fermat

1')

a^{φ (m)} \equiv 1 mod m

für alle teilerfremden

a, m

.

schaffen könnte, d.h., eine

a

-Potenz-Aussage, die für ALLE

a

gilt:

2')

a^{φ (m) + s} \equiv a^{s} mod m

für alle

a

.

Dabei sei

s

von allen in der Primfaktorzerlegung von

m

auftretenden Primzahlpotenzen der MAXIMALE Exponent.

Beispiel:

m = 100 = 2^{2} \cdot 5^{2}

, da wäre

s = max (2, 2) = 2

, und 2') würde dann

a^{42} \equiv a^{2} mod 100

für ALLE

a

besagen, speziell auch für

a = 2

.

2') ist sicher keine Neuentdeckung, aber ich bin halt nicht so firm in all den (mehr oder weniger bekannten) Untervarianten und Folgerungen von Euler-Fermat. :-)

EDIT: Das

φ (m)

in 2') kann man überdies durch die Carmichael-Funktion

λ (m)

ersetzen, und die Aussage bleibt richtig! Mit

λ (100) = k g V (λ (4), λ (25)) = k g V (2, 20) = 20

haben wir damit sogar

a^{22} \equiv a^{2} mod 100

,

und die obige Rechnung vereinfacht sich nach dieser Vorarbeit sogar zu

2^{751} = 2^{37 \cdot 20 + 11} \equiv 2^{11} = 2048 \equiv 48 mod 100

. Ich glaub, kürzer krieg ich es nun wirklich nicht mehr hin. :-D)

platofan23 aktiv_icon

16:11 Uhr, 28.04.2020

das kann gut sein, aber das geht mir jeztz dann doch zu weit. Ich sage dann mal dicke danke :-D)

HAL9000

16:43 Uhr, 28.04.2020

Ja, ist Ok, ist ja nur Kür.

Hab halt ein bisschen Brainstorming zu dem Thema gemacht, und vielleicht finden ja andere diese weiter gehenden Überlegungen interessant (oder können mir sagen, ob es für 2') in der Literatur einen eigenen Namen gibt, und wie der lautet).

platofan23 aktiv_icon

17:28 Uhr, 28.04.2020

interessant ist es aufjedenfall, aber man zeit für hat auch. naja momentan sind die unis ja zu und selbst beim dualen ist es nicht mal sicher, ob noch mal geschoben wird XD.

achja ich hab dann noch ein aufgabe, wo ich gerne eine meinung zu hätte:

Berechnen Sie modulo 10 alle ganzzahligen Lösungen zu:

4*3+4*x=6/7*2+2

nun habe ich hier angefangen und in inverse von 7 bestimmt. Dort komme ich auch 3 bzw. dann von mod 10 abgezogen 3 ist dann 7...

1500478

1500388

	Status: nicht eingeloggt	Noch nicht registriert?