Primzahlen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Beweise, daß eine ungerade Zahl p genau dann prim ist, wenn
$ [mm] [(\bruch{p-1}{2})!]^2 \equiv (-1)^\bruch{p+1}{2} \quad [/mm] mod [mm] \quad [/mm] p $ |
Guten morgen,
könnte mir jmd. bitte einen Ansatz geben, sodass ich diese Aufgabe lösen kann?
LG
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:04 Mi 05.11.2014 | | Autor: | Teufel |
Hi!
Für ein wenig Inspiration, schau mal HIER!
|
|
|
| |
|
Beweise, daß eine ungerade Zahl p genau dann prim ist,
wenn
[mm]\blue{[(\bruch{p-1}{2})!]^2 \equiv (-1)^\bruch{p+1}{2} \quad mod \quad p}[/mm]
Hallo,
in dieser Behauptung scheint ein auf einer im Prinzip
einfachen Berechnung beruhender, allgemein gültiger
Primzahltest vorzuliegen, der ohne Suchalgorithmus
(wie etwa das Sieb des Eratosthenes) auskommt.
Bei der Suche nach Primzahltests habe ich diese
Methode aber trotzdem nicht gefunden, sondern
nur eine gewisse Verwandtschaft mit dem Lucas-
Test vermuten können.
Kann mir jemand dazu Tipps geben ?
So recht praktikabel scheint der Test aber wohl
doch nicht zu sein, und zwar schlicht wegen der
Berechnungen astronomischen Ausmaßes, die von der
quadrierten Fakultät in dem zu berechnenden
Term ausgehen.
LG , Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:04 Mi 05.11.2014 | | Autor: | Marcel |
Hallo Al,
> Beweise, daß eine ungerade Zahl p genau dann prim ist,
> wenn
>
> [mm]\blue{[(\bruch{p-1}{2})!]^2 \equiv (-1)^\bruch{p+1}{2} \quad mod \quad p}[/mm]
>
>
> Hallo,
>
> in dieser Behauptung scheint ein auf einer im Prinzip
> einfachen Berechnung beruhender, allgemein gültiger
> Primzahltest vorzuliegen, der ohne Suchalgorithmus
> (wie etwa das Sieb des Eratosthenes) auskommt.
>
> Bei der Suche nach Primzahltests habe ich diese
> Methode aber trotzdem nicht gefunden, sondern
> nur eine gewisse Verwandtschaft mit dem Lucas-
> Test vermuten können.
>
> Kann mir jemand dazu Tipps geben ?
ich sehe hier eher eine Verwandtschaft zum Satz von Wilson.
> So recht praktikabel scheint der Test aber wohl
> doch nicht zu sein, und zwar schlicht wegen der
> Berechnungen astronomischen Ausmaßes, die von der
> quadrierten Fakultät in dem zu berechnenden
> Term ausgehen.
Du rechnest modulo p, d.h., wenn Du immer drauf achtest, dass Du in
dem gleichen vollst. Repräsentantensystem bei den Multiplikationen bleibst,
wirst Du von der Betrags-Größenordnung nicht größer als p-1 (oder, wenn
Du das Günstigste nimmst: [p/2]+1 oder sowas) werden.
Ich hatte nämlich einen ähnlichen Gedankenfehler
hier (klick!)
P.S. Laufzeitmäßig wird das Sieb des Eratosthenes aber doch gewinnen...
Gruß,
Marcel
|
|
|
| |
|
Guten Abend Marcel
> > in dieser Behauptung scheint ein auf einer im Prinzip
> > einfachen Berechnung beruhender, allgemein gültiger
> > Primzahltest vorzuliegen, der ohne Suchalgorithmus
> > (wie etwa das Sieb des Eratosthenes) auskommt.
> >
> > Bei der Suche nach Primzahltests habe ich diese
> > Methode aber trotzdem nicht gefunden, sondern
> > nur eine gewisse Verwandtschaft mit dem Lucas-
> > Test vermuten können.
> >
> > Kann mir jemand dazu Tipps geben ?
>
> ich sehe hier eher eine Verwandtschaft zum Satz von
> Wilson.
Zu meiner Schande muss ich zugeben, dass mir dieser
Satz noch gar nicht bekannt war (oder dass ich ihn
vergessen habe). Erstaunt war ich aber, dass der Satz
eigentlich gar nicht diesem modernen Schnösel Wilson
zugeschrieben werden sollte, da er eigentlich schon auf
Abu Ali al-Hasan ibn al-Haitham zurückgehen soll ... 
![[]](/images/popup.gif) Quelle
In dieser Quelle findet man übrigens gleich darunter
auch den vorliegenden Satz.
Ich weiß jetzt also, womit ich mich beschäftigen muss,
wenn ich das Ganze auch verstehen möchte. Danke sehr
also für den Hinweis !
> > So recht praktikabel scheint der Test aber wohl
> > doch nicht zu sein, und zwar schlicht wegen der
> > Berechnungen astronomischen Ausmaßes, die von der
> > quadrierten Fakultät in dem zu berechnenden
> > Term ausgehen.
>
> Du rechnest modulo p
> .....
Ja ! Daran hatte ich schon gedacht, aber trotzdem bleibt
auch so der Rechenaufwand noch "astronomisch" (dies
könnte man durch eine Laufzeitanalyse präzisieren)
> P.S. Laufzeitmäßig wird das Sieb des Eratosthenes aber
> doch gewinnen...
So ungefähr habe ich das eben auch vermutet !
LG , Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:39 Mi 05.11.2014 | | Autor: | Marcel |
Hi,
> Guten Abend Marcel
>
> > > in dieser Behauptung scheint ein auf einer im Prinzip
> > > einfachen Berechnung beruhender, allgemein
> gültiger
> > > Primzahltest vorzuliegen, der ohne Suchalgorithmus
> > > (wie etwa das Sieb des Eratosthenes) auskommt.
> > >
> > > Bei der Suche nach Primzahltests habe ich diese
> > > Methode aber trotzdem nicht gefunden, sondern
> > > nur eine gewisse Verwandtschaft mit dem Lucas-
> > > Test vermuten können.
> > >
> > > Kann mir jemand dazu Tipps geben ?
> >
> > ich sehe hier eher eine Verwandtschaft zum Satz von
> > Wilson.
>
> Zu meiner Schande muss ich zugeben, dass mir dieser
> Satz noch gar nicht bekannt war (oder dass ich ihn
> vergessen habe). Erstaunt war ich aber, dass der Satz
> eigentlich gar nicht diesem modernen Schnösel Wilson
> zugeschrieben werden sollte, da er eigentlich schon auf
> Abu Ali al-Hasan ibn al-Haitham zurückgehen soll ...
>
>
> Quelle
> In dieser Quelle findet man übrigens gleich
> darunter
> auch den vorliegenden Satz.
> Ich weiß jetzt also, womit ich mich beschäftigen muss,
> wenn ich das Ganze auch verstehen möchte. Danke sehr
> also für den Hinweis !
>
> > > So recht praktikabel scheint der Test aber wohl
> > > doch nicht zu sein, und zwar schlicht wegen der
> > > Berechnungen astronomischen Ausmaßes, die von der
> > > quadrierten Fakultät in dem zu berechnenden
> > > Term ausgehen.
> >
> > Du rechnest modulo p
>
> > .....
>
> Ja ! Daran hatte ich schon gedacht, aber trotzdem bleibt
> auch so der Rechenaufwand noch "astronomisch" (dies
> könnte man durch eine Laufzeitanalyse präzisieren)
ja, Du meinst, weil man [mm] $[p/2]\,$ [/mm] Multiplikationen braucht? Das stimmt. Schade,
dass man das nicht, wie bei Potenzen, *runterbrechen* kann...
> > P.S. Laufzeitmäßig wird das Sieb des Eratosthenes aber
> > doch gewinnen...
>
> So ungefähr habe ich das eben auch vermutet !
Ich habe mir dazu noch nie Gedanken gemacht, aber soweit ich mich
erinnere, hat Teufel das mir vor Kurzem in einer PN geschrieben.
Obenstehender Satz ist aber sicher effizienter wie der direkte Primzahltest
mit Wilson.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 07:24 Do 06.11.2014 | | Autor: | felixf |
Moin,
> > Ja ! Daran hatte ich schon gedacht, aber trotzdem bleibt
> > auch so der Rechenaufwand noch "astronomisch" (dies
> > könnte man durch eine Laufzeitanalyse präzisieren)
>
> ja, Du meinst, weil man [mm][p/2]\,[/mm] Multiplikationen braucht?
> Das stimmt. Schade,
> dass man das nicht, wie bei Potenzen, *runterbrechen*
> kann...
Genau.
> > > P.S. Laufzeitmäßig wird das Sieb des Eratosthenes aber
> > > doch gewinnen...
> >
> > So ungefähr habe ich das eben auch vermutet !
>
> Ich habe mir dazu noch nie Gedanken gemacht, aber soweit
> ich mich
> erinnere, hat Teufel das mir vor Kurzem in einer PN
> geschrieben.
Die Laufzeit vom Sieb des Eratosthenes ist $O(p [mm] \log [/mm] p [mm] \log\log [/mm] p)$ mit $O(p)$ Speicher.
> Obenstehender Satz ist aber sicher effizienter wie der
> direkte Primzahltest
> mit Wilson.
Viel langsamer als die Methode vom Satz von Wilson ist das aber auch wieder nicht, da es nur etwa halb so viele Multiplikationen sind. Die Laufzeit ist also $O(p [mm] \log [/mm] p [mm] \log\log [/mm] p [mm] \log\log\log [/mm] p)$ mit schneller Ganzzahlarithmetik (basierend auf Fouriertransformation), oder $O(p [mm] \log^2 [/mm] p)$ bei "naiver" Ganzzahlarithmetik. Wilson hat die gleiche asymptotische Laufzeit. Der Speicherbedarf ist hier allerdings [mm] $O(\log [/mm] p)$.
Damit ist klar, dass das Sieb von Eratosthenes schneller ist (asymptotisch gesehen auf jeden Fall), und da man dort keine komplizierte Arithmetik braucht (man muss nur addieren) ist es auch einfacher zu implementieren. Dagegen benötigt es sehr viel Speicher. In der Praxis muss man also schauen, was bei wie grossen Zahlen auf welchem System wirklich schneller ist (grosser Speicherbedarf impliziert auch Langsamkeit, weil man die CPU-Caches nur kaum nutzt, und normaler Speicherzugriff sehr langsam ist).
Ich würde da eher ganz andere Primzahltests verwenden. Für Zahlen in einem begrenzten Intervall kann man den Miller-Rabin-Test exakt machen (siehe hier), er wird beide obigen Algorithmen in allen praktischen Situationen schlagen. (Auch schon in der Nähe von $p < 3'825'123'056'546'413'051$ sind die völlig unbrauchbar.)
LG Felix
|
|
|
| |
|
Salü Felix ,
Besten Dank für die Analyse !
Dass diese Art von Tests z.B. in den Regionen der heutigen
kryptologischen Primzahlen praktisch unbrauchbar sein
würden, war ja aber schon von vornherein abzusehen.
LG , Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:51 Do 06.11.2014 | | Autor: | Marcel |
Hi Felix,
auch meinerseits Danke für diese vielen Informationen. Es wird aber sicher
einige Zeit brauchen, bis ich dazu komme, diese zu verarbeiten bzw.
nachzurechnen bzw. etwas nachzuschlagen. (Zumal es für mich aktuell "nur"
interessante Hintergrundinformationen sind, die ich [noch] nicht wirklich
brauche. Nichtsdestotrotz: Sehr interessant!)
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:20 Do 13.11.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
Hey ellegance88,
wie schon in den Mitteilungen ausdiskutiert riecht dein Problem sehr stark nach dem Satz von Wilson, den du hoffentlich schon in der Vorlesung hattest. Ein Blick auf dieWikipediaseite liefert auch gleich eine Lösung für dein Problem: eine Induktion nach $n$.
Zugegeben, damit kriegst du nur die eine Richtung gezeigt, also dass wenn $p$ eine Primzahl ist deine Gleichung gilt.
Die andere Richtung ist aber auch nicht so schwer.
Nehmen wir an $p$ sei keine Primzahl, also $p=ab$ für $a,b$ natürliche Zahlen und beide echt größer als 1.
Nun nehmen wir einfach mal $p>4$ an, die anderen $p$ kannst du sicher von Hand erledigen.
In diesem Fall ist mindestens einer der beiden Faktoren $a,b$ echt kleiner als [mm] $\frac{p-1}{2}$. [/mm] Was heißt das für deine Fakultät; warum kann jetzt auf keinen Fall mehr eine Potenz von $-1$ rauskommen?
lg
Schadow
|
|
|
|
