matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenZahlentheoriePrimzahlen
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
Forum "Zahlentheorie" - Primzahlen
Primzahlen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Primzahlen: Übung
Status: (Frage) beantwortet Status 
Datum: 09:43 Mi 05.11.2014
Autor: ellegance88

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

        
Bezug
Primzahlen: Antwort
Status: (Antwort) fertig Status 
Datum: 12:04 Mi 05.11.2014
Autor: Teufel

Hi!

Für ein wenig Inspiration, schau mal HIER!

Bezug
        
Bezug
Primzahlen: Primzahltest ?
Status: (Frage) überfällig Status 
Datum: 12:44 Mi 05.11.2014
Autor: Al-Chwarizmi

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

Bezug
                
Bezug
Primzahlen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                        
Bezug
Primzahlen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:06 Mi 05.11.2014
Autor: Al-Chwarizmi

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)
  

> P.S. Laufzeitmäßig wird das Sieb des Eratosthenes aber
> doch gewinnen...

So ungefähr habe ich das eben auch vermutet !

LG ,   Al

Bezug
                                
Bezug
Primzahlen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
                                        
Bezug
Primzahlen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
                                                
Bezug
Primzahlen: danke
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 11:43 Do 06.11.2014
Autor: Al-Chwarizmi

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

Bezug
                                                
Bezug
Primzahlen: Ebenfalls Danke
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                
Bezug
Primzahlen: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 13:20 Do 13.11.2014
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
        
Bezug
Primzahlen: Antwort
Status: (Antwort) fertig Status 
Datum: 00:32 Do 06.11.2014
Autor: Schadowmaster

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 die[]Wikipediaseite 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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]