Faktorisierung --> (p - 1) Methode, Fragen...

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

Faktorisierung --> (p - 1) Methode, Fragen...

Beitrag von oren78 »

hallo miteinander,

hätte da zwei fragen bzgl. der (p - 1) Methode...

1.) gibt es ein noch effizienteren weg statt der schnellen exponention wie man p = gcd(2^k - 1, n) bestimmen kann...? Der kleine Satz vom Fermat scheitert hier natürlich da (2^k)-1 und n NICHT teilerfremd zueinander sind, also fällt das schon mal weg...sonst noch alternativen?

2.) Wie bestimme ich eigentlich selbst die Schanke B ? oder kann man sich drauf verlassen das diese gegeben wird?
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

Benutzeravatar
Tristan
Windoof-User
Windoof-User
Beiträge: 29
Registriert: 22. Okt 2008 20:32

Re: Faktorisierung --> (p - 1) Methode, Fragen...

Beitrag von Tristan »

Also um \(2^k\) zu bestimmen, benutzt du schnelle Exponentiation. Den ggT kriegst du mit dem Euklidischen Algorithmus.

Die Schranke wählt man so groß wie möglich, so dass die Berechnung noch zeitlich machbar ist. Falls in der Klausur so eine Aufgabe kommt, versuch halt ein paar Schranken durch, bis es klappt. Die kann man nicht "bestimmen" - je höher desto besser (solange es berechnbar bleibt).

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

Re: Faktorisierung --> (p - 1) Methode, Fragen...

Beitrag von oren78 »

Tristan hat geschrieben:Also um \(2^k\) zu bestimmen, benutzt du schnelle Exponentiation. Den ggT kriegst du mit dem Euklidischen Algorithmus.
das war mir eigentlich vor diesem thread schon klar 8)
Tristan hat geschrieben: Die Schranke wählt man so groß wie möglich, so dass die Berechnung noch zeitlich machbar ist. Falls in der Klausur so eine Aufgabe kommt, versuch halt ein paar Schranken durch, bis es klappt. Die kann man nicht "bestimmen" - je höher desto besser (solange es berechnbar bleibt).
wenn man die schranke so groß wie möglich wählt, warum reicht dann in der 9 Übung B = 8 schon aus? 8 finde ich nicht sonderlich groß...
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

Benutzeravatar
Tristan
Windoof-User
Windoof-User
Beiträge: 29
Registriert: 22. Okt 2008 20:32

Re: Faktorisierung --> (p - 1) Methode, Fragen...

Beitrag von Tristan »

das war mir eigentlich vor diesem thread schon klar 8)
Warum fragst du dann? :?:
wenn man die schranke so groß wie möglich wählt, warum reicht dann in der 9 Übung B = 8 schon aus? 8 finde ich nicht sonderlich groß...
Wo ist denn da der Widerspruch? Das war eben ein Fall, wo es bereits mit einer kleineren Schranke klappt. Das ist wie wenn du fragst "wie viele Zahlen probiert man bei Probedivision aus?": so viele wie möglich - manchmal reicht aber schon eine :wink:

Benutzeravatar
roddy
Windoof-User
Windoof-User
Beiträge: 33
Registriert: 21. Apr 2004 16:48
Wohnort: Darmstadt
Kontaktdaten:

Re: Faktorisierung --> (p - 1) Methode, Fragen...

Beitrag von roddy »

Ich hätte auch noch ne Frage zur (p-1)-Methode. Laut dem Buch verwendet man für k "die Produkte aller Primzahlpotenzen, die nicht größer als eine Schranke B sind". In der Übungsaufgabe ist die Schranke B = 8. Wenn ich jetzt auf der Suche nach Primzahlpotenzen wäre, würde ich wie folgt vorgehen:

2^1 = 2 <= 8 --> OK
2^2 = 4 <= 8 --> OK
2^3 = 8 <= 8 --> OK
2^4 = 16 > 8 --> fällt raus
3^1 = 3 <= 8 --> OK
3^2 = 9 > 8 --> fällt raus
5^1 = 5 <= 8 --> OK
5^2 = 25 > 8 --> fällt raus
7^1 = 7 <= 8 --> OK
7^2 = 49 > 8 --> fällt raus

somit hätte ich als "alle Primzahlpotenzen, die nicht größer als die Schranke B sind" die Zahlen 2, 4, 8, 3, 5 und 7. In der MuLö zur Ü9/G5 werden aber nur 8, 3, 5 und 7 verwendet. Kann mir jemand erklären, warum da nicht auch die 2 und die 4 mit verwendet werden?
"Welch traurige Epoche, in der es leichter ist ein Atom zu zertrümmern als ein Vorurteil"
Albert Einstein

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

Re: Faktorisierung --> (p - 1) Methode, Fragen...

Beitrag von oren78 »

roddy hat geschrieben:somit hätte ich als "alle Primzahlpotenzen, die nicht größer als die Schranke B sind" die Zahlen 2, 4, 8, 3, 5 und 7. In der MuLö zur Ü9/G5 werden aber nur 8, 3, 5 und 7 verwendet. Kann mir jemand erklären, warum da nicht auch die 2 und die 4 mit verwendet werden?
also folgendes: die primfaktoren die überhaupt in frage kommen sind: \(\lbrace\;2,\; 3,\; 5,\; 7\;\rbrace\)
wir benötigen nun das produkt dieser zahlen und zwar so, das ihre höchste potenz kleinergleich der Schranke B sind...

somit kommen nur: \(\lbrace\; 2^3,\; 3^2,\; 5^1,\; 7^1\;\rbrace\) in frage, das wars schon eigentlich...übrigens ist die Schranke B immer gegeben ;-)
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

Benutzeravatar
roddy
Windoof-User
Windoof-User
Beiträge: 33
Registriert: 21. Apr 2004 16:48
Wohnort: Darmstadt
Kontaktdaten:

Re: Faktorisierung --> (p - 1) Methode, Fragen...

Beitrag von roddy »

Vielen Dank.

Also geht es quasi um "das Produkt der jeweils höchsten Potenz aller Primzahlen, wobei die Potenz kleiner gleich 8 sein muss".
"Welch traurige Epoche, in der es leichter ist ein Atom zu zertrümmern als ein Vorurteil"
Albert Einstein

Benutzeravatar
bruse
Kernelcompilierer
Kernelcompilierer
Beiträge: 412
Registriert: 2. Aug 2006 22:42

Re: Faktorisierung --> (p - 1) Methode, Fragen...

Beitrag von bruse »

Ja, das ist im Buch unglücklich formuliert, bzw. die dort abgedruckte Formel schlicht nicht korrekt. Wenn man sich aber klar macht, wie die p-1-Methode funktioniert, sieht man warum es reicht, jeweils die höchste Potenz zu nehmen: Wir suchen ja ein Vielfaches von p-1. Ist jetzt eine niedrigere Potenz schon "drin", hat man mit einer höheren halt ein mehrfaches, das bringt einem höchstens einen Extraschritt beim Euklid ein.
Un hombre de frente a una ventana
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.

AhGuGu
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 8. Dez 2005 13:21

Re: Faktorisierung --> (p - 1) Methode, Fragen...

Beitrag von AhGuGu »

Hallo,
bruse hat geschrieben:Ist jetzt eine niedrigere Potenz schon "drin", hat man mit einer höheren halt ein mehrfaches, das bringt einem höchstens einen Extraschritt beim Euklid ein.
Das ist gerade das entscheidende. Das Verfahren würde auch ohne Primzahlpotenzen funktionieren. Allerdings hat man dann unter Umständen Pech und muss eine höhere Schranke wählen. Wenn mich nicht alles trügt, reichen in dem Beispiel die Primzahlen aus.

gruß Ahgugu

Antworten

Zurück zu „Archiv“