Pseudo Primzahlen...

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

Pseudo Primzahlen...

Beitrag von oren78 »

Kleine Frage zu Aufgabe G2 in der Übung: 9

Wir sollen die kleinste Pseudo-Primzahl zur Basis 3 bestimmen, im Buch auf der Seite: 126 stehen hierfür zwei Bedingungen die gelten müssen:

\(a^{n-1}\;\equiv\;1\;mod\;n\;\land\;n\;=\;ungerade\;zusammengesetzte\;Zahl\)

gibt es ein effizientere methode außer stures brute-force um die Pseudo-Primzahl zu bestimmen...?
ohne hilfe von Pari wäre ich nicht so schnell auf die 91 gekommen 8)
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

Dreamdancer
Mausschubser
Mausschubser
Beiträge: 67
Registriert: 17. Jul 2005 23:17
Wohnort: Frankfurt am Main

Re: Pseudo Primzahlen...

Beitrag von Dreamdancer »

Interessiert mich auch gerade. Obwohl: Da es ja kein Kampfrechnen geben soll, ist das scheinbar wirklich nur eine Interessens-Frage.

citta
Mausschubser
Mausschubser
Beiträge: 96
Registriert: 7. Nov 2006 21:52

Re: Pseudo Primzahlen...

Beitrag von citta »

Bei Wikipedia gibt es eine Formel dazu http://de.wikipedia.org/wiki/Fermatsche_Pseudoprimzahl
Aber ich denke nicht, dass wir die können müssen. Die Aufgabe soll wohl nur den Begriff verständlich machen.

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

Re: Pseudo Primzahlen...

Beitrag von oren78 »

eine kleine frage:

n = 19459 sollte eigentlich eine carmichael-zahl sein, ihre drei primfaktoren lauten: 11, 29, 61 wieso aber wird diese zahl NIRGENDWO als carmichael-zahl erwähnt..??

http://de.wikipedia.org/wiki/Carmichael-Zahl

Laut des Theorems: 8.3.1 von Prof. Buchmanns Buch müsste n, die die vorgegebenen Eigenschaften besitzt eine Carmichael Zahl sein...irrt sich hier das Buch oder was genau ist falsch an meiner vermutung?

Edit: sorry, hab die zweite Eigenschaft übersehen: "für jeden Primteiler p von n muss gelten: (p - 1) teilt (n - 1)" 8)
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

Antworten

Zurück zu „Archiv“