Pseudoprimzahl faktorisieren

Neue Frage »

bafla13 Auf diesen Beitrag antworten »
Pseudoprimzahl faktorisieren
Hallo
Mein Frage:
Wie kann man einer natürlichen Zahl dasss Pseudoprimzahl (aber keine Starke) ist den nicht trivialen faktor finden?? was ist überhaupt ein nicht trivialer faktor ??

Danke schön
watcher Auf diesen Beitrag antworten »

Was verstehst Du denn unter einer Pseudoprimzahl?
Dieser Begriff wird im Allgemeinen nur informell verwendet.

Triviale Faktoren sind die die alle Zahlen haben: 1 und sich selbst.
bafla13 Auf diesen Beitrag antworten »

Zitat:
Original von watcher

Triviale Faktoren sind die die alle Zahlen haben: 1 und sich selbst.

Danke für die Antwort smile

Ich verstehe den Begriff Pseudoprimzahlen,

Aber die Frage war ,wie finde ich so einer Zahl den trivialen Faktor??
watcher Auf diesen Beitrag antworten »

Zitat:
Was verstehst Du denn unter einer Pseudoprimzahl? Dieser Begriff wird im Allgemeinen nur informell verwendet.


Zitat:
Ich verstehe den Begriff Pseudoprimzahlen,


Sorry aber deine Antwort zeugt nicht davon, dass du meinen Post gelesen hast.
Oder ist das ein versuch eines non sequitur?

Zitat:
Aber die Frage war ,wie finde ich so einer Zahl den trivialen Faktor??

Nein, das war nicht die Frage.

Also nochmal:
Welche Art von zahlen möchtest du gern faktorisieren?
Pseudoprimzahlen gibt's viele verschiedene.
Kennst Du allgemeine Faktorisierungsverfahren?
bafla13 Auf diesen Beitrag antworten »

also ich habe die eine Aufgabe die einfach so lautet:

Wie kann man einen nichttrivialen Faktor von der natürlichen Zahl n finden, falls n zur Basis b eine
Pseudoprimzahl, aber keine starke Pseudoprimzahl ist?

Ich habe bis jetzt an der Uni kein bestimmtes verfahren gelernt obwohl ich einige kenne,und daher brauche ich angeblich diese verfahren nicht smile

so z.b 341 ist ein pseudoprimzahl aber keine starke,
aber wie kann ich die faktoren bestimmen smile ??
Mystic Auf diesen Beitrag antworten »

Deine Angaben sind alle sehr bruchstückhaft und zeugen von wenig Ahnung von der Materie... geschockt

Wahr ist, dass 341 den Fermattest zur Basis 2 erfüllt, aber nicht den Miller-Rabin Test... Es gilt somit



aber wenn man beidseitig die Wurzeln zieht, solange dies möglich ist, erhält man nicht immer , wie es sein müsste, wenn 341 prim wäre (das ist eben der Miller-Rabin Test!)... Überprüf das mal und dann sehen wir weiter...
 
 
bafla13 Auf diesen Beitrag antworten »

Zitat:
Original von Mystic
Deine Angaben sind alle sehr bruchstückhaft und zeugen von wenig Ahnung von der Materie... geschockt

Wahr ist, dass 341 den Fermattest zur Basis 2 erfüllt, aber nicht den Miller-Rabin Test... Es gilt somit



aber wenn man beidseitig die Wurzeln zieht, solange dies möglich ist, erhält man nicht immer , wie es sein müsste, wenn 341 prim wäre (das ist eben der Miller-Rabin Test!)... Überprüf das mal und dann sehen wir weiter...


Also ich teile nachher 340/2
und es gilt
wieder 170/2

und deshalb ist 341 keine Primzahl
ist der Test nicht so??
aber wie kann uns das weiterbringen ??
Mystic Auf diesen Beitrag antworten »

Wunderbar... Freude

Und nun mach bitte genau das Gleiche noch einmal, aber mod 11 bzw. mod 31, also für die (noch unbekannten) Primfaktoren von 341...
bafla13 Auf diesen Beitrag antworten »

Zitat:
Original von Mystic
Wunderbar... Freude

Und nun mach bitte genau das Gleiche noch einmal, aber mod 11 bzw. mod 31, also für die (noch unbekannten) Primfaktoren von 341...

Da bekomme ich vom ersten schritt dass diese Zahl keine Primzahl ist

Beim 31 ist es gleich 155 also ungleich 1
Beim 11 ist es gleich 242 also ungleich 1
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von bafla13
Da bekomme ich vom ersten schritt dass diese Zahl keine Primzahl ist

Beim 31 ist es gleich 155 also ungleich 1
Beim 11 ist es gleich 242 also ungleich 1

Oh Gott, du solltest doch mod 31 bzw. mod 11 rechnen... Wie können da so Mammutzahlen wie 155 bzw. 242 dabei herauskommen? Forum Kloppe
bafla13 Auf diesen Beitrag antworten »

Zitat:
Original von Mystic
Zitat:
Original von bafla13
Da bekomme ich vom ersten schritt dass diese Zahl keine Primzahl ist

Beim 31 ist es gleich 155 also ungleich 1
Beim 11 ist es gleich 242 also ungleich 1

Oh Gott, du solltest doch mod 31 bzw. mod 11 rechnen... Wie können da so Mammutzahlen wie 155 bzw. 242 dabei herauskommen? Forum Kloppe


oo sorry ich dachte ich mache das gleiche wieder für 11^340 mod341 was ja bestimmt immer alles außer 1 liefert,
also muss ich nun 341 mod 11 und 341 mod 31 machen oder was meinst du genau ??
Mystic Auf diesen Beitrag antworten »

Hm, ich dachte eigentlich, ich hätte mich klar ausgedrückt, also einfach das Gleiche wie vorhin, d.h.





Und nimm bitte die kleinsten Absolutreste, also auch negative Reste, wenn diese dem Betrage nach kleiner sind...
bafla13 Auf diesen Beitrag antworten »

Zitat:
Original von Mystic
Hm, ich dachte eigentlich, ich hätte mich klar ausgedrückt, also einfach das Gleiche wie vorhin, d.h.





Und nimm bitte die kleinsten Absolutreste, also auch negative Reste, wenn diese dem Betrage nach kleiner sind...


Also alle liefern 1 außer


Mystic Auf diesen Beitrag antworten »

Ja, und diese Rechnungen laufen mod 11 bzw. mod 31 entweder "synchron" mit gleichen Werten +1 oder -1 oder mit mit verschiedenen Werten wie eben bei ... Diese "Asynchronität" macht sich dann der Miller-Rabin Test erbarmungslos zunutze und liefert als Ergebnis, dass 341 nicht prim sein kann... Für uns heißt das aber, dass die beiden Zahlen



dann nichttriviale Teiler von 341 sein müssen...
bafla13 Auf diesen Beitrag antworten »

Zitat:
Original von Mystic
Ja, und diese Rechnungen laufen mod 11 bzw. mod 31 entweder "synchron" mit gleichen Werten +1 oder -1 oder mit mit verschiedenen Werten wie eben bei ... Diese "Asynchronität" macht sich dann der Miller-Rabin Test erbarmungslos zunutze und liefert als Ergebnis, dass 341 nicht prim sein kann... Für uns heißt das aber, dass die beiden Zahlen



dann nichttriviale Teiler von 341 sein müssen...


OOOOK verstehe ich jetzt smile vielen Dank aber ich habe noch eine Frage,

Wenn es mehr als zwei Primteiler gegeben würde,wie könnte man die Teiler finden??
weil ja nur zwei Teiler liefern kann oder?
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von bafla13
Wenn es mehr als zwei Primteiler gegeben würde,wie könnte man die Teiler finden??
weil ja nur zwei Teiler liefern kann oder?

Schlimmer noch: Man bekommt i.allg. so einen Teiler, der gar nicht prim sein muss, und seinen Komplementärteiler, den man ja auch so dann erhalten hätte... Aber es war andererseits auch nirgendwo davon die Rede, dass man auf diese Weise eine vollständige Primfaktorzerlegung der Zahl bekommt...
bafla133 Auf diesen Beitrag antworten »

Zitat:
Original von Mystic
Zitat:
Original von bafla13
Wenn es mehr als zwei Primteiler gegeben würde,wie könnte man die Teiler finden??
weil ja nur zwei Teiler liefern kann oder?

Schlimmer noch: Man bekommt i.allg. so einen Teiler, der gar nicht prim sein muss, und seinen Komplementärteiler, den man ja auch so dann erhalten hätte... Aber es war andererseits auch nirgendwo davon die Rede, dass man auf diese Weise eine vollständige Primfaktorzerlegung der Zahl bekommt...


Achsooo alles klar smile ich bedanke mich ^^
HD1920 Auf diesen Beitrag antworten »

Genau jetzt findest du einen Faktor, indem du von 1 abziehst und dann den ggT mit 341 bildest!
Neue Frage »
Antworten »



Verwandte Themen

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