Modulares Potenzieren

Neue Frage »

sari25 Auf diesen Beitrag antworten »
Modulares Potenzieren
Meine Frage:
Hallo, mir fehlen für die Rechnung 2^2520 (mod 246082373) ein paar Hintergründe.

Vielleicht kann mir jemand den Rechenweg erklären (am besten so einfach wie möglich Augenzwinkern )?!



Meine Ideen:
Als Tipp habe ich erhalten, dass ich 2520 als Summe von Zweierpotenzen darstelle, also

2520 = 2^3 + 2^4 + 2^6 + 2^7 + 2^8 + 2^11

Nun wollte ich "ganz schlau" sein und 2^2^i (mod 246082373) für i = 0,1,...,11 berechnen,
muss aber schon bei i=6 aufgeben, da ich da erhalte:

i=6 : (2^32)^2=2^64 (mod n)

Da das mein Taschenrechner nicht rechnen kann, muss es irgendeinen Trick dahinter geben. Habe mir jetzt schon einige Seiten im Internet angeschaut, die mir aber nicht weitergeholfen haben traurig
tatmas Auf diesen Beitrag antworten »

Der Trick an der Sache ist nicht 2^64 in den Taschenrechner zu tippen sondern zuerst 2^32 mod 246082373 auszurechnen, insbesondere das Ergebnis reduziert (in deinem Lieblingsrepräsentantensystem) darzustellen und das dann zu quadrieren.
das soll auch die Schreibweise (2^32)^2 suggerieren.
HAL 9000 Auf diesen Beitrag antworten »

Trotzdem sollte der TR natürlich noch in der Lage sein, Integer-Multiplikationen mit Operanden, die betragsmäßig kleiner oder gleich sind (hier mit Modul m=246082373) noch durchführen zu können. Bei nur 10 oder 12 Stellen Mantisse ist dies nicht möglich, im vorliegenden Fall benötigt man dann schon 17 Stellen für die möglichen Multiplikationsergebnisse, sonst muss man die Rechnung weiter zerlegen (was relativ aufwändig ist).


EDIT: Sofern man die Primfaktorzerlegung kennt, geht die Berechnung natürlich auch noch anders. smile
sari25 Auf diesen Beitrag antworten »

Das leuchtet mir ja auch ein.
Ich erhalte dann aber:

(2^32)^2 = 111566955^2

Das kriegt er (der Taschenzwerg) wirklich noch hin...

Aber dann bei

(2^64)^2 = 166204404^2 werden die Zahlen ja so groß....!
sari25 Auf diesen Beitrag antworten »

Das mit der Primfaktorzerlegung von n (bzw. bei dir m) hab ich auch schonmal
irgendwo gesehen.

Irgendwie scheint mir dafür aber das Verständnis zu fehlen,

wieso man dabei mit 2521 arbeitet??


Kannst du mir da vielleicht einen Hinweis für die Rechnung geben?
Was stell ich mit den beiden Faktoren genau an?
Tut mir leid, aber ich seh bei diesem Thema (eigtl. Faktorisierungsalgorithmen großer Zahlen) einfach kein Land verwirrt
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von sari25
wieso man dabei mit 2521 arbeitet??

Erstaunt1

Drück dich mal bitte klarer aus: Dass ist, ergibt sich einfach als Ergebnis der eindeutigen Primfaktorzerlegung! D.h., es ist ja nicht so, dass man da auf Faktor 2521 "hingearbeitet" hat. unglücklich
 
 
sari25 Auf diesen Beitrag antworten »

Das stimmt schon, aber die Faktorisierung von n= 246082373 =2521 *97613

soll mein Ergebnis sein.

Ich soll zuerst 2^2520 mod n berechnen und dann mit Hilfe des Euklidischen Algorithmus durch den ggT ((2^2520) -1, n) meinen nichttrivialen Faktor von n erhalten (und das wird ja wirklich 2521 sein.....nur warum?)
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von sari25
Das stimmt schon, aber die Faktorisierung von n= 246082373 =2521 *97613

soll mein Ergebnis sein.

Dann hättest du vielleicht im Eröffnungsbeitrag darauf hinweisen sollen. Ich lese da als Primärziel die Berechnung von 2^2520 (mod 246082373), und kein Wort von dem Ziel der Faktorisierung von 246082373. Augenzwinkern
sari25 Auf diesen Beitrag antworten »

Ja, das war nicht so günstig merk ich gerade.

Also nochmal zur Aufgabe:
Primär geht es um das (p-1) Faktorisierungsverfahren von Pollard.
Ich versuche jetzt,

2^2520 = 2(2^3 +2^4+2^6+2^7+2^8+2^11) (mod 246082373) zu berechnen.
Dafür wollte ich für i= 0,1,...,11 die

2^2^i (mod 246082373) ausrechen, aber ab i=7 komme ich nicht weiter...
tatmas Auf diesen Beitrag antworten »

Es gibt eine Reihe von Möglichkeiten, z.B.

-Nutze als Repräsentantensystem.
-Zieh Faktoren aus der Basis raus, z.B.ist 36 | 166204404
HAL 9000 Auf diesen Beitrag antworten »

Was mich wundert: Die Quadrierung von kriegt er noch hin, die des nur etwas größeren nicht mehr? Sind ja wirklich hart an der K...zgrenzen, deine Rechenkapazitäten. Augenzwinkern


Wenn nur dieses kleine Quäntchen fehlt, dann arbeite doch mit vorzeichenbehafteten Resten, d.h., lege deine Reste nicht ins Intervall , sondern .

Im Fall ist ja , und es ist

,

dann klappt's vielleicht auch wieder mit dem Quadrieren.


P.S.: Sehe jetzt erst beim Verfassen, dass der erste Vorschlag von tatmas in die gleiche Richtung geht.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »