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

[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?

[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).

[oren78]

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

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ß...

[Tristan]

das war mir eigentlich vor diesem thread schon klar

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

[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?

[oren78]

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

[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".

[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.

[AhGuGu]

Hallo,

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