Diskussion:Primzahltest

Probedivision meint etwas anderes, als ein konsequentes durchdividieren

Bei der Probedivision geht es, wie schön in gleichnamigem Artikel beschrieben, um einen Angriffspunkt der Teilbarkeit zu finden. Es reicht also erstmal, einen einzigen Teiler zu finden. Bei einem Test auf Primzahl muß man aber alle Zahlen bis zur Quadratwurzel testen, da eine Zahl nur dann eine Primzahl ist, wenn alle Zahlen zwischen 2 und der Quadratwurzel der Zahl keine Teiler dieser Zahl sind. --Arbol01 17:26, 27. Mai 2004 (CEST)

Sobald ich einen Teiler finde, weiss ich, dass die Zahl nicht prim ist. Dann kann ich aufhören. "Wenn ich Pech habe", dann muss ich auch bei der Probedivision bis zur Wurzel von n hochgehen, und wenn ich dann keinen gefunden habe, ist die Zahl prim.

Ich sehe nicht den Unterschied im Verfahren. Der einzige Unterschied, den ich sehe, besteht darin, dass ich bei der Probedivision am konkreten Teiler interessiert bin, beim Primzahltest nur daran, ob ein Teiler existiert. --SirJective 22:27, 27. Mai 2004 (CEST)

Das sieht nur so aus. Lies mal genau. Im Artikel Probedivision steht:

"Für die Probedivision benötigt man eine Liste mit kleinen Primzahlen, die man gewöhnlich über das Sieb des Eratosthenes erzeugt".

Wenn ich aber schon mal das Sieb des Erathosthenes verwende, muß ich nicht mehr durchprobieren, ob kein Teiler existiert.

Nochmal: Ich will wissen, ob eine Zahl eine Primzahl ist. Bei dem konsequenten Durchdividieren muß ich den potentiellen Primzahlkandidat n , ohne Kenntnis irgendeiner Primzahl, durch 2, 3, 4, 5, 6, ... bis Quadratwurzel(n) dividieren.

Wenn ich umgekehrt wissen will, ob eine Zahl teilbar ist, reicht mir schon ein einziger Teiler. --Arbol01 06:38, 28. Mai 2004 (CEST)

Ich gebe zu, ich habe Probedivision bisher nur so gemacht, dass ich durch alle ungeraden Zahlen bis sqrt(n) teile. Für mich sieht es jetzt also so aus, als wäre das "einfache Durchtesten auf Teilbarkeit" eine "schlechte Probedivision", bei der ich eben nicht nur die Primzahlen bis sqrt(n) teste, sondern alle Zahlen von 2 bis sqrt(n) verwende.

Aber gut, nach den momentan drinstehenden Darstellungen sind das zwei verschiedene Verfahren. --SirJective 21:07, 28. Mai 2004 (CEST)

Die Verfahresnweise ist halt sehr ähnlich, aber die Motivation ist völlig unterschiedlich. Im einen Fall hofft man, das man blos möglichst schnell einen Teiler findet, und im anderen Fall hofft man, das man blos keinen Teiler findet.

Obsolet ist im Prinzip das Verfahen so oder so. Im einen Fall gibt es bessere Fakturierungsverfahren, im anderen Fall kommt man prima mit Erathostenes, Fermat und Konsorten hin.

Was die Fakturierungsverfahren betrifft, hätte ich gerne das Verfahren mit den Qaudratzahlen näher ausgeführt. Also das z.B. 21 = 3*7 = (5-2)*(5+2) = 5²-2². --Arbol01 22:58, 28. Mai 2004 (CEST)

---

Ich glaube der eine Herr beim Soloway-Strassen-Test heisst eigentlich 'Solovay' mit v und nicht mit w. Demnach also 'Solovay-Strassen-Test' (nach Robert Solovay und Volker Strassen).

--Teylen 23:19, 7. Jul 2004 (CEST)

Ich denke, du hast Recht. Das Blöde ist nur, dass ich beim Erstellen des Artikels nur kurz zur Überprüfung mit google gesucht hab, und da auch eine Menge mit w gefunden wurden. Ich werde den Artikel verschieben und einen Link auf die beiden Autoren einfügen. Danke! --Sebi 18:48, 9. Jul 2004 (CEST)

Sicherer Primzahltest auf Perrin-Basis?

Es existiert anscheinend ein Primzahltest auf der Perrin-Folge der sicher ist. Es ist möglich, das die perrinschen Pseudoprimzahlen inkompatibel zu den fermatschen Pseudoprimzahlen sind. Sollte das der Fall sein, dann könnte eine Kombination aus einem für fermatsche Pseudoprimzahlen empfindlichen Verfahren und der Perrin-Folge, einen zu 100% sicheren, und gleichzeitig relativ schnellen Primzahltest ergeben. 1982 haben anscheinend Adams und Shank an so einem Test gearbeitet. Wer weiß mehr? --Arbol01 17:03, 5. Nov 2004 (CET)

Elliptic Curve Primality Proving (ECPP)

Im Artikel "Primzahltest" vermisse ich den gegenwärtig wichtigsten Primzahltest im Kapitel "2 Bekannte Primzahltest-Verfahren", http://mathworld.wolfram.com/EllipticCurvePrimalityProving.html: ECPP (Elliptic Curve Primality Proving) is the fastest known general-purpose primality testing algorithm. Ist diese Auslassung ein Versehen ? Hans Rosenthal (hans.rosenthal AT t-online.de -- ersetze AT durch @ )

Wenn der Artikel noch nicht existiert, dann ist es sicher kein Zufall. Wer schreibt ihn? Aber ist es denn auch ein Primzahltest? Oder ist es vielleicht ein Faktorisierungsverfahren? --Arbol01 08:53, 13. Jun 2005 (CEST)

Einleitung

Der zweite Einleitungssatz ist im Sinne der Sprachlogik völlig wirr. Denn Das Sieb des Erathostenes läßt sich kaum mit einem Primzahltest vergleichen. Ein Primzahltest behandelt eine einzelne Zahl. Das Sieb des Erathostenes ist aber ein Verfahren, um Primzahlenfolgen zu bestimmen, bzw. eine große Anzahl von Primzahlen zu erzeugen. Völlig unterschiedliche Dinge also, die man nicht in den zwei einfachen Sätzen zusammenfassen kann. Da es nicht das gleiche tut wie der Primzahltest, kann es auch keine Ausnahme sein. Ich habe das korrigiert.--Löschfix 21:03:39, 23. Aug 2005 (CEST)

Ich bin mit deiner Änderung einverstanden. Allerdings möchte ich darauf hinweisen, das das Sieb des Erathostenes, als Primzahltest, für kleine Zahlen (bis z.B. 4.000.000) viel schneller ist, als der herkömmliche naive Brute Force-Test durch Ausprobieren. Denn nach dem Durchlauf des Sieb des Eratosthenes kann man aus einer Tabelle ablesen, ob eine Zahl, innerhalb des Intervalls, eine Primzahl ist; und wenn man die Tabelle konserviert, kann man auch noch später darauf zugreifen.

Gegen die probabilistischen Primzahltest hat das Sieb des Eratosthenes natürlich keine Chance. --Arbol01 21:29, 23. Aug 2005 (CEST)

Kürzung definitiv zu drastisch.

Die Änderung 21:42, 16. Nov. 2006 Squizzz (Diskussion | Beiträge) (→Bekannte Primzahltest-Verfahren - gekürzt (Wikipedia ist kein Lehrbuch)) finde ich eindeutig zu drastisch. Was heißt den hier "kein Lehrbuch"? Wenn man sowas löscht, dann sollte man auch den halben Mathematikinhalt löschen weil der voller Mathematischer Begriffe und Sätze ist. Was Squizzz getan hat ist einfach nur Informationen rausnehmen, nicht vereinfachen. Der Nächste der darauf stößt wird sich fragen wieso es reicht bis Wurzel(n) zu prüfen. Wer sich den Artikel soweit durchliest will auch wissen wie es genau passiert und das beschreibt meine Version. Ich finde, die vorherige Version sollte wiederhergestellt werden. 129.69.211.10 18:34, 17. Nov. 2006 (CET)

Sieb des Eratosthenes, Pseudocode

Hab 3 recht unnötige Zeilen in der Implementierng des Siebs entfernt, die von der Programlogik her redundant waren und nur den Code verwirrender machten, und die Einrückung leicht verbessert, so dass der Code nun lesbarer sein _sollte_. Evtl. kann man das aber noch weiter verbessern? Mit richtigen geschweiften Klammern so dass die einzelnen Absätze und Kontrollstrukturen besser lesbarer sind? Weiß nicht wie da die Regeln von Wikipedia bezüglich Pseudocode aussehen...

Es gibt keine Konventention. Allerdings sollte Pseudocode nur verwendet werden, wenn diese für den Artikel einen bedeutenden Mehrwert mit sich bringt. Ist jedoch eine textliche Beschreibung eines Algorithmus ausreichend, so sollte auf Pseudocode verzeichtet werden. Insbesondere ist die Wikipedia keine Paseudocode-Sammlung. Die Ausführung zum Sieb des Eratosthenes in diesem Artikel habe ich entfernt, da es dafür einen eigenen Artikel gibt. --Stefan Birkner 22:37, 23. Mär. 2007 (CET)

Zeitaufwand bei Probedivision

Folgendes steht unter Probedivision: Die Probedivision ist jedoch viel zu aufwändig, sodass sie in der Praxis als Primzahltest nicht zum Einsatz kommt.

Bei der Ermittlung von riesigen Primzahlen mag das vielleicht der Fall sein, doch das ist ja nicht überall so. In der Schule, zum Beispiel, lernt man kein anderes Verfahren und mithilfe des Computers ist es im Millisekundenbereich möglich Zahlen unter einer Billionen mit diesem Verfahren zu überprüfen. So ist diese relativ wage Aussage zu spezifizieren. --Jobu0101 19:16, 5. Aug. 2008 (CEST)

Meines Wissens werden Primzahltests vor allem in der Kryptologie für sehr große Zahlen durchgeführt (siehe Abschnitt „Praktische Anwendung“). Für diese kommt die Probedivision höchstens als Teil eines größeren Algorithmus zum Einsatz. Unter dieser Voraussetzung ist die Annahme richtig. Wenn du jedoch einen relevanten anderen Anwendungsfall hast, dann würde ich die Aussage entsprechend korrigieren. --Stefan Birkner 19:33, 5. Aug. 2008 (CEST)

Ja bei kleinen Zahlen. Das, was man mal so schnell im Kopf macht... --Jobu0101 19:38, 5. Aug. 2008 (CEST)

Ich werde mal konkreter. Ausgenommen irgendwelche Spielereien und Mathehausaufgaben: Wann braucht man einen Primzahltest für kleine Zahlen? Wozu macht man mal so schnell einen Primzahltest im Kopf? --Stefan Birkner 21:05, 5. Aug. 2008 (CEST)

Eine Primzahl ist immer ungerade, aiser die ZIFFER 2

Umbenennung: Primalitätstest

Ich schlage vor den Artikel in Primalitätstest umzubenennen. Das ist die korrekte Sprechweise, denn es wird ja die Primalität einer Zahl getestet. Würde man Primzahlen testen, wie der Name Primzahltest suggeriert wäre das trivial. (nicht signierter Beitrag von 129.26.72.116 (Diskussion) 15:00, 16. Nov. 2011 (CET))

Primalitätstest Algorithmen

Habe herausgefunden, dass es ein paar andere Algorithmen für die Primalitätsprüfung gibt.

$x\in \mathbb {P}$ wenn $f(x)=0$. Ansonsten $x\notin \mathbb {P}$.

$f(x)=$ $x$ $mod$ $1$ $\cdot \prod _{n=2}^{\sqrt {x}}$ $(x$ $mod$ $n)^{-1}$

Das ähnliche gilt für:

$h(x)=sin(x\cdot \pi )\cdot \prod _{n=2}^{\sqrt {x}}sin(x\cdot {\frac {\pi }{n}})^{-1}$

$g(x)={\frac {1}{x!}}\cdot \prod _{n=2}^{\sqrt {-x}}({\frac {x}{n}}!)^{-1}$

$j(x)={\frac {\prod _{n=1}^{x}(x-n)}{\prod _{t=2}^{\sqrt {x}}\prod _{s=1}^{x}(x-t\cdot s)}}$

Diese Algorithmen basieren auf dem Prinzip des Siebes des Eratosthenes, wo Beispielsweise, $(x$ $mod$ $1)$benutzt wird um alle Nummern bis ${\sqrt {x}}$, zu repräsentieren, und das Produkt $((x$ $mod$ $n_{1})$ $\cdot$ $(x$ $mod$ $n_{2})$ $\cdot$ $(x$ $mod$ $n_{3})$$\ldots )^{-1}$, welches gebildet wird um die "Streichung" von Vielfachen von $n$ in $(x$ $mod$ $1)$ zu bezwecken.

Ich würde mir wünschen, dass es jemanden gibt, der eine Laufzeitprüfung von f(x) im Vergleich zu anderen Algorithmen machen kann.

Ich hatte einige rechen Probleme mit h(x) und g(x) weil die Präzision der Funktion, beim Umgang mit sin(x), im Programm Python zu klein war. Selbst $\pi$ zu verwenden war tückisch. Da die Nachkommastellen wichtig sind, das Programm aber diese nicht richtig verwendete, war es hoffnungslos genaue Ergebnisse zu bekommen. Zusätzlich schien mir, sich mit dem Komplexen Zahlensystem auseinander zu setzen, in Bezug auf g(x), es zu programmieren etc. zu schwer. So, dass ich nur f(x) empfehlen kann um exakte Rechnungen zu vollführen.

Ich empfehle beim Kalkulieren hoher Zahlen, ein Komma und eine Null hinten ran zu fügen wenn nicht schon vorhanden, da es Konvertierungsprobleme von hohen Zahlen gibt sobald von einer integer Variabel zu einer float Variabel konvertiert wird. Hier mal der Code in Python:

import math
import numpy


x=7.0 #zu testene Zahl hier einfügen
n=2.0
a=x%1
q=1
	
while(n<=numpy.sqrt(x)):
	q=q*(x%n)
        if (x%n==0):
		break
	n=n+1

try :
	y=a/q 
except ZeroDivisionError:
	y=1
if(y==0):
	print("x value ",x,"y value ",y)
else:
	print("x value ",x,"y value ",y)

Lincalm (Diskussion) 17:14, 31. Okt. 2019 (CET)

Testete mein Programm mit einem anderen um herauszufinden welches schneller ist.

Nummer: 10000000000003 getestet mit:

from time import *
import numpy
t1=clock()
n=10000000000003.0

prim=True
	
if n==1:
	prim= False
	
else: 
	i=2
	while i<=numpy.sqrt(n):
		if n%i==0:
		     break
			prim=False
		i=i+1
		
print("n= ", n,prim)
t2=clock()
t=t2-t1
print("Laufzeit in Sek. ", t)

Gebrauchte Zeit: 0.000484

Im Verhältnis dazu der andere Test:

Nummer: 10000000000003 getestet mit:

from time import *
import math
import numpy

#wenn y=0 dann ist x in P
#ansonsten x ist nicht in P

x=10000000000003.0# Nummer zum testen hier einfügen
n=2.0
a=x%1
q=1
t1=clock()	
while(n<=numpy.sqrt(x)):
	q=q*(x%n)
        if (x%n==0):
		break
	n=n+1 #kalkuliert das endliche Produkt

try :
	y=a/q #kalkuliert das Ergebnis
except ZeroDivisionError:
	y=1000 #y auf 1000 gesetzt falls eine durch Null Division aufkommt, welche den ZeroDivisionError auslösen würde.
if(y==0):
	print("x Wert ",x,"y Wert ",y)
else:
	print("x Wert ",x,"y Wert ",y)
t2=clock()
t=t2-t1

print("Laufzeit in Sek. ",t)

Gebrauchte Zeit: 0.000470

Man kann erkennen, dass mein Programm etwas schneller ist. Wirklich nennenswert ist das aber nicht.

Benutztes System: Wiko View XL Prozessor: Quad Core 1.4Ghz Entwicklungsumgebung: Pydroid3