Geheimnis der Primzahlen

@Christopher101
Mit der Kryptografie bin ich nicht 100%ig vertraut.
Zitat von @interpreter aus einer anderen Diskussion:

Zum Beispiel werden Primzahlen die für Verschlüsselungen verwendet werden keineswegs gesiebt. Es gibt andere Möglichkeiten auf Primalität zu testen.

Beispielsweise gibt es einen speziellen Test für "Mersenne Primzahlen" nach dem Schema 2^x-1

Nicht alle Zahlen nach diesem Schema sind Prim. Aber es lässt sich leicht und effizient testen. Das heißt ein Algorithmus der eine Primzahl für Verschlüsselung erzeugt, erzeugt ein paar Zahlen nach diesem Schema auf Zufallsbasis und testet sie, bis er ne Primzahl findet.

Christopher101 schrieb:man könnte 2 auch als keine anshehen weil es eine gerade Zahl ist

Bitte? Wenn man 2 auch als nicht-Primzahl ansehen kann, dann zerlege mir doch bitte mal 6 in seine Primfaktoren.

Christopher101 schrieb:man könnte 2 auch als keine anshehen weil es eine gerade Zahl ist

Nah, das kann man natürlich nicht. Gerade Zahlen ab 4 sind deswegen keine Primzahlen weil sie durch 2 teilbar sind. 2 ist nur durch sich selbst und 1 teilbar und damit eine Primzahl.

@gerhard86

klar aber gibt es denn gerade primzahlen?

Christopher101 schrieb:klar aber gibt es denn gerade primzahlen?

@Christopher101
Mit Ausnahme der 2 natürlich nicht.

Christopher101 schrieb:klar aber gibt es denn gerade primzahlen?

Genau eine. Gerade heißt durch 2 teilbar. Es gibt auch genau eine Primzahl, die durch 3 teilbar ist.

Heizenberch schrieb:Es gibt auch genau eine Primzahl, die durch 3 teilbar ist.

Genau, nämlich 3. Und nur eine die durch 5 teilbar ist, nämlich 5. Und nur eine die durch 7 teilbar ist, nämlich 7. Und nur eine die durch 78839 teilbar ist, nämlich 78839. Verstehst du, @Christopher101, die 2 ist nichts Spezielles bis auf dass du auf den ersten Blick siehst ob eine Zahl dadurch teilbar und daher keine Primzahl ist.

@HYPATIA

Da kann man ja schon das eine oder andere Muster erkennen. Ist auch bekannt ob das auch fuer grosse Primzahlen so weitergeht, dass mehrere Primzahlen in einer 'Reihe' liegen oder liegt das nur an der anfaenglichen Dichte an Primzahlen?

Hängt davon ab, ob es unendlich viele Primzahlzwillinge gibt. Das ist bisher noch nicht bewiesen. Es wurden zwar auch für große Primzahlen schon solche Gruppen gefunden, nur der Beweis steht noch aus:

Wikipedia: Primzahlvierling

Nichtkommutative Geometrie passt zu den Primzahlen

"Die Erwartung war, dass diese neue Form der Geometrie dabei helfen könnte, einige fundamentale Fragen der Natur zu beantworten, von der Entstehung des Universums bis hin zum Quantenphänomen.
Noch während der Konferenz erkannte Connes die Verbindung: seine neue Form der Geometrie passte zu den Primzahlen."
http://www.3sat.de/page/?source=/hitec/156499/index.html

@McNeal
Die Muster treten in jeder Größenordnung auf (zumindest da, wo wir Primzahlen kennen) und man braucht bei der Spirale nicht mal mit der 1 anfangen. Recht viel weiß man nicht, außer dass es sehr viele dieser Diagonalen gibt, für die die Primzahldichte höher ist, als bei einer zufälligen Verteilung zu erwarten ist. Trotzdem ist bis jetzt keine wirkliche Struktur entdeckt worden.
Das ganze funktioniert übrigens auf für andere Arten, die Zahlen aufzutragen, dann ergeben sich andere Muster:

Original anzeigen (0,4 MB)

Viele sinnvolle Beweise gibts leider noch nicht, jedenfalls nicht, solange keine anderen Vermutungen bewiesen werden, wie etwa die Goldbach-Vermutung.



Jedenfalls immer sehr spannend, wie aus einfachen Zusammenhänge komplexe Muster entstehen können :)

In dem Zusammenhang ist auch noch die Mill-Konstante A interessant. Damit kann man beliebig große Primzahlen berechnen.

Dazu rechnet man A ^ (3^n) und rundet das Ergebnis ab. Das Ergebnis ist immer eine Primzahl.

A ist vermutlich (wenn die Riemann-Hypothese richtig ist) ungefähr
A=1.3063778838630806904686144926026057129167845851567136443680537599664340537668...

Damit könnt ihr ja mal rumprobieren, funktioniert immer. Jedenfalls in dem Bereich, in dem unsere Computer diesen Spaß auch mitmachen, die Zahlen werden nämlich recht schnell hässlich groß.

HYPATIA schrieb:Recht viel weiß man nicht, außer dass es sehr viele dieser Diagonalen gibt, für die die Primzahldichte höher ist, als bei einer zufälligen Verteilung zu erwarten ist. Trotzdem ist bis jetzt keine wirkliche Struktur entdeckt worden.

Ist Eulers Entdeckung aus dem 18 Jahrhundert nicht bereits ein deutlicher Hinweis auf eine wirkliche Struktur ?:

"Während er über ein anderes mathematisches Problem nachdachte, fand Euler eine kleine Gleichung, die nur aus Primzahlen bestand.

Eine Reihe zufälliger Primzahlen (in die Zeta-Funktion eingesetzt) führt zu einem ganz einfachen Ergebnis:
pi²/6 .

Die Zahl also, mit deren Hilfe man eines der vollkommensten Gebilde des Universums definiert: den Kreis.
Euler war der erste, der beweisen konnte, dass es einen Zusammenhang zwischen elementaren Gesetzen der Natur und Primzahlen gibt.
http://www.3sat.de/page/?source=/hitec/156496/index.html

eckhart schrieb:Die Zahl also, mit deren Hilfe man eines der vollkommensten Gebilde des Universums definiert: den Kreis. Euler war der erste, der beweisen konnte, dass es einen Zusammenhang zwischen elementaren Gesetzen der Natur und Primzahlen gibt.

Das klingt aber schon wieder arg esoterisch. Klar haben Primzahlen eine Struktur, nur ist noch nicht allzuviel darüber bekannt. Aber das wird schon.

eckhart schrieb:Während er über ein anderes mathematisches Problem nachdachte, fand Euler eine kleine Gleichung, die nur aus Primzahlen bestand.

Was genau meinst du? Euler hatte meines Wissens nach ein Polynom das bis 41 nur Primzahlen ausspuckte. Es ist aber bewiesen, dass es kein Polynom gibt, das ausschließlich Primzahlen ausspuckt. Dagegen gibt es Zahlen wie Mills Konstante, die nachweisbar Primzahlen erzeugen. Die kleinste davon ist nach Definition gerade Mills Konstante.

eckhart schrieb:Eine Reihe zufälliger Primzahlen (in die Zeta-Funktion eingesetzt) führt zu einem ganz einfachen Ergebnis:
pi²/6 .

Ich glaub, da verwechselst du auch was, oder? Die unendliche Reihe über 1/n² ergibt pi²/6, das hatte Euler herausgefunden. Allerdings war das noch etwas geraten, weil er Schritte gemacht hatte, die damals noch nicht bewiesen waren.

haben wir hier vll einen mathematiker oder informatiker unter uns, der mir sagen kann wielange dieser code ca braucht bis er fertig ist?

# *-* encoding utf-8 *-*

n = 10000000

prims = []
i = 1

myfile = open('primzahlen.txt', 'w+')

while (i<=n):
counter = 0
for x in prims:
if not i % x:
counter += 1
if counter > 1:
break
if counter == 1:
prims.append(i)
print >> myfile, i
if i == 1 :
prims.append(i)
print >> myfile, i
i += 1


myfile.close()

edit: bekomme die einrückung leider nicht hin

@Bonzo

kA was fuer ne Sprache das ist aber 'if counter == 1:' sollte vielleicht eher <= heissen weil prims anfangs noch leer ist und so der counter niemals erhoeht wird. ausserdem solltest du mit i=2 anfangen.

ja das hab ich auch gemerkt. allerdings funzt es! nur läufts seit 3 stunden und hab keine lust das jetzt abzubrechen :D - muss man sich die 1 halt wegdenken.

ist python code.

das problem is halt dass die prims liste immer größer wird und die zu testenden zahlen ebenso.
hab solangsam die befürchtung dass das so schnell nicht fertig wird. wenn überhaupt noch zu lebzeiten :D

Mit python würd ich sowas sowieso nicht machen, das braucht für solche Sachen viel zu lange. Nimm irgendwas, was direkt in Maschinencode kompiliert. Es gibt übrigens noch effizientere Algorithmen um Primzahlen zu bestimmen, zum Beispiel Sieb von Atkin.

Wikipedia: Sieve of Atkin#Pseudocode

@HYPATIA

Ist zwar ne sehr nette Idee aber das lohnt doch nicht fuer die Bereiche, die @Bonzo will.
Das Ding ist langsamer als das Sieb von Eratosthenes fuer kleinere Bereiche und wird erst ab richtig grossen Zahlenbereichen interessant (so im Gigabytebereich). Und ich kann mir kaum vorstellen, dass man das Ding ohne Erfahrung schneller optimiert kriegt als ein einfaches Sieb.

@Bonzo
Nur so als Tipp: Probier erstmal was dein Programm fuer die ersten 50 Zahlen macht bevor du das Ding mehrere Stunden laufen laesst.