Primfaktorzerlegung von sehr großen Zahlen

Aufrufe: 65     Aktiv: 08.09.2021 um 15:57

1
Hallo,

ich habe folgende Aufgabe: Ich soll die PFZ von 626.257 bestimmen. Als Tipp steht ein Hinweis:  φ (626.257) = 624.640.

Der Hinweis sagt mir aus, dass es zu 626.257 insgesamt 624.640 teilerfremde Zahlen gibt, die nicht größer sind als 626.257. Wie komme ich aber anhand dieser Information auf die PFZ? Den Weg "zu Fuß" habe ich schon angefangen... komme aber nicht weit... 

Kann jemand helfen, ohne die Lösung vorzusagen?
Danke!
Diese Frage melden
gefragt

Punkte: 38

 
Kommentar schreiben
1 Antwort
1
Benutze den Satz: Wenn $p,q$ Primzahlen sind, so ist $\varphi(p\,q)=(p-1)(q-1)$.
Ich würde den Hinweis so verstehen, dass es damit geht. Die Primfaktorzerlegung von 624640 ist relativ einfach. Dann diese Zahl in zwei Faktoren zerlegen, so dass die rechte Seite aus dem Satz entsteht. Damit kommt man zum Ziel, etwas Probieren ist natürlich nötig.
Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 16.93K

 

Die PFZ von 624640 ist 2^11*5*61. Durch Probieren bin ich auf 624640 = (2^4)*(2^7*5*61) = 16*39040 = (17-1)*(39041-1) gekommen, wobei 17 und 39041 Primzahlen sind.

Leider weiß ich immer noch nicht, was mir das jetzt gebracht hat...
  ─   einmaleins 08.09.2021 um 14:22

Ja, und, erfüllt diese Zerlegung das verlangte? Wenn ja, fertig. Wenn nein, weiter probieren.   ─   mikn 08.09.2021 um 14:40

Nein, erfüllt es leider nicht. Denn:

Wir wissen ja φ (626.257) = 624.640. Somit ist φ (626.257) = 16*39040. Somit müsste 17*39041 eine PFZ von 626.257 sein, ist es aber nicht, denn 17*39041=663697.

Ich habe weiterprobiert: 624.640 = 976 * 640 = (977-1)*(641-1). 977 und 641 sind Primzahlen und ergeben beide im Produkt 626.257. Die Primfaktorzerlegung von 626.257 ist also 977*641.

Klingt das richtig?
  ─   einmaleins 08.09.2021 um 15:09

1
Ja, das passt. Daraus ist viel zu lernen. PFZ sind schwierig bei großen Zahlen (das hier sind KEINE großen Zahlen). Es sollte keinen kleinen Faktor geben, möglichst nur große (also alle etwa gleich groß), damit es schön schwierig bleibt. Einfach ist es dagegen zu prüfen, ob p*q das gewünschte liefert. Genau das ist ja das Prinzip des RSA-Algorithmus.   ─   mikn 08.09.2021 um 15:56

Kommentar schreiben