Primzahltest

22.07.2007, 01:28

matze(2)

Primzahltest

Hallo,

ich habe mir folgenden Primzahltest überlegt:

Es sei $\begin{eqnarray*} t \end{eqnarray*}$ die zu testende ungerade natürliche Zahl > 1, also $\begin{eqnarray*} t \in \{3, 5, 7, 9, 11, ...\} \end{eqnarray*}$

Wenn $\begin{eqnarray*} \sqrt{t + i^{2}} \end{eqnarray*}$ für ein $\begin{eqnarray*} i = 0, 1, 2, 3, 4, ..., \frac{t-1}{2}-2, \frac{t-1}{2}-1 \end{eqnarray*}$ rational ist, so ist $\begin{eqnarray*} t \end{eqnarray*}$ zusammengesetzt, andernfalls ist $\begin{eqnarray*} t \end{eqnarray*}$ prim.

Mich würde es nun freuen zu erfahren, ob dieses Verfahren noch optimierbar ist oder ob man es noch etwas verändern muss, damit es zu einer Wahrscheinlichkeit von ungerundeten 100% ein wahrheitsgemäßes Ergebnis liefert.

22.07.2007, 09:32

Gast1234

Auf diesen Beitrag antworten »

Sei $\begin{eqnarray*} t=5 \end{eqnarray*}$ .

Für $\begin{eqnarray*} i=2 \end{eqnarray*}$ ist $\begin{eqnarray*} \sqrt{t+i^2} = \sqrt{5+4} = 3 \in \mathbb Q \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow t=5 \notin \mathbb P \end{eqnarray*}$

verwirrt

22.07.2007, 09:56

Dual Space

Auf diesen Beitrag antworten »

Zitat:

Original von Gast1234
Sei $\begin{eqnarray*} t=5 \end{eqnarray*}$ .

Für $\begin{eqnarray*} i=2 \end{eqnarray*}$ ist $\begin{eqnarray*} \sqrt{t+i^2} = \sqrt{5+4} = 3 \in \mathbb Q \end{eqnarray*}$

Stimmt, aber laut Voraussetzung soll in diesem Falle $\begin{eqnarray*} i\in\{0,1\} \end{eqnarray*}$ sein.

22.07.2007, 10:31

Auf diesen Beitrag antworten »

@matze(2)

Erstmal die gute Nachricht: Die Aussage stimmt.

Jetzt aber die schlechte: Über Optimierbarkeit dieses Verfahrens zu sprechen macht m.E. wenig Sinn - denn der erkennbare Aufwand $\begin{eqnarray*} O(t) \end{eqnarray*}$ ist für einen Primzahltest miserabel. Selbst die übliche primitive Methode, alle ungeraden Zahlen kleiner oder gleich der Wurzel als Teiler zu überprüfen, schneidet mit Aufwand $\begin{eqnarray*} O(\sqrt{t}) \end{eqnarray*}$ deutlich besser ab.

22.07.2007, 17:29

matze(2)

Auf diesen Beitrag antworten »

Das habe ich schon befürchtet. Ursprüglich wollte ich ein Verfahren finden mit dem man Primzahlen konstruieren kann, aber das ist sehr schwer.

22.07.2007, 18:23

Dual Space

Auf diesen Beitrag antworten »

So schwer nun auch wieder nicht: http://de.wikipedia.org/wiki/Primzahlen#..._von_Primzahlen Man muss das Rad ja nicht neu erfinden. Augenzwinkern

22.07.2007, 19:15

matze(2)

Auf diesen Beitrag antworten »

"Es gibt allerdings Formeln, bei denen eine gewisse Wahrscheinlichkeit besteht, dass die erzeugten Zahlen eine Primzahl sein könnten. Trotzdem müssen die erzeugten Zahlen auf ihre Eigenschaft als Primzahl getestet werden."

Ich würde eine Formel, die bei gegebenen Bedingungen allgemein gültig ist, viel schöner finden.

22.07.2007, 22:17

Dual Space

Auf diesen Beitrag antworten »

Vorsicht. Diese Aussage bezieht sich nur auf eine bestimmte Klasse von Formeln. Eben solche zur Berechnung der n-ten Primzahl.

Du sprachst bisher nur von Formeln zur Berechnung von Primzahlen. Und da gibt es zahlreiche allgemein gültige Formeln.

24.07.2007, 02:25

matze(2)

Auf diesen Beitrag antworten »

Gut, ok, nun bin ich wieder einmal schlauer geworden smile

Ja, so ist das heutzutage. Es gibt von dem, was man gebrauchen kann, schon fast alles und das, was es noch nicht gibt, wird es auch in unmittelbarer Zukunft noch nicht geben. (Jedenfalls in dem Niveau, bei dem ich mich noch befinde.)

24.07.2007, 08:37

Dual Space

Auf diesen Beitrag antworten »

Man muss bei der Forschung ja nicht immer gleich nach den Sternen greifen, sondern kann auch kleine Schritte machen. Augenzwinkern

25.07.2007, 20:52

matze(2)

Auf diesen Beitrag antworten »

Ja, das ist wirklich war.

Neue Frage »

Antworten »

Primzahltest

Verwandte Themen