Mit den Fibonacci Zahlen, eine Primzahl berechnen die 250000 Dollar...

mastermind schrieb:Gibt es denn keine Möglichkeit, das mathematische Problem irgendwie umzuformulieren, und dann mit anderen Mittel heranzugehen?

Nicht direkt. Es gibt aber beispielsweise den sogenannten Primzahlsatz, mit dem versucht abzuschätzen, wie viele Primzahlen sich zwischen 1 und einer beliebigen Zahl n befinden.
Die Folgerungen aus dieser allgemeinen Überlegung, bringen aber nur teilweise gewisse Hinweise, wie Primzahlen geordnet sind bzw. wie oft sie auftreten.

Ich erinnere mich beispielsweise an einen Folgesatz, der aussagte, dass die Verteilungsfunktion des Primzahlsatzes, für hinreichend große n, auch beliebige große konstante Intervalle besitzt.
Oder zu gut deutsch: Zwischen den Primzahlen 11 und 13 oder 23 und 29 sieht man ja, dass es noch eine gewisse Anzahl an Nicht-Primzahlen gibt. Diese Lücken können im Allgemeinen beliebig groß werden. Dementsprechend ist es auch möglich, wenn die Primzahlen nur groß genug sind, dass man zwei aufeinanderfolgende Primzahlen findet zwischen denen eine Million oder eine Milliarde oder noch mehr Nicht-Primzahlen liegen.

Mit der Zeit fand man zwar immer bessere Aussagen darüber, wo sich i.A. eine Primzahl finden lässt, aber dies hilft nur sehr bedingt, letztlich auch diese Primzahlen selbst zu finden.
So gibt es beispielsweise einen Hilfssatz der sagt, dass sich im Intervall von n bis n! eine Primzahl befindet.
Aber auch hier ist wieder zu bedenken, dass diese Intervalle für größer werdende n natürlich auch immer größer werden und somit nur einen groben Hinweis liefern, wo sich letztlich die Primzahl finden lässt.


Das Problem Primzahlen konkret benennen zu wollen führt halt immer wieder auf ein paar grundlegende Überlegungen zurück:
Entweder man benutzt Algorithmen, wie etwa das Sieb von Erathosthenes und arbeitet sich halt systematisch durch die natürlichen Zahlen und schaut nach einer Weile mal nach, was dieses Sieb durchgelassen hat,
oder man stellt sich der allgemeinen Frage, ob Primzahlen neben ihrer sonderbaren Teilbarkeitseigenschaft, noch weitere Eigenschaften besitzen, die es ermöglichen solche Zahlen von allen anderen zu unterscheiden.
Nehmen wir beispielsweise die Zahl 143. Was ist bei dieser Zahl anders als bei der 139?
Gibt es eine Alternative dazu, dass man jetzt nacheinander versucht diese Zahlen durch 3,...,13 zu teilen, in der Hoffnung, dass eine dieser Zahlen eine restlose Division erbringt?
Beispielsweise der Versuch diese Zahlen auf Vielfache oder Potenzen von 2 zurückzuführen, verändert zwar die Darstellung der Zahlen, offenbart aber keine solch allgemeine Eigenschaft, die gesucht sind.

Also entweder gibt es einfach keine andere Möglichkeit als unmittelbar auf restlose Teilbarkeit zu testen oder diese alternative Eigenschaft ist dermaßen gut versteckt, dass wie gesagt schon diverse Mathematikergenerationen ohne Erfolg auf die Suche danach gegangen sind.

BlackFlame schrieb:oder man stellt sich der allgemeinen Frage, ob Primzahlen neben ihrer sonderbaren Teilbarkeitseigenschaft, noch weitere Eigenschaften besitzen, die es ermöglichen solche Zahlen von allen anderen zu unterscheiden.

Man weiß das sie das haben. 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.

Wenn man sich nur auf Siebe verlasten müsste könnte man darauf keine verlässliche Verschlüsselung aufbauen.

Das einzige vernünftige was du mit der Fibonacci machen kannst ist im Roulette eine garantiert verlierende Abstreich Progression spielen.

Du Einstein für Arme.@Christopher101
@interpreter
@BlackFlame
@Heizenberch
@mastermind

@interpreter
Ich weis.
Da ich aber gewisse Methodiken und Sätze der Zahlentheorie erst im Studium kennen und schätzen gelernt habe, so wollte einfach mal ein paar allgemeine Fragestellungen zu Primzahlen erwähnen, weil das so mancher wohl sehr zu unterschätzen scheint und diese Fragestellungen zwar mit heutigen Rechenwerken etwas einfacher handzuhaben sind, man aber so manche grundlegende Problemfrage doch einmal auch theoretisch durchdacht haben sollte. Also am besten durch die Augen der Mathematiker, die sich noch ohne Computer an solchen Überlegungen versucht haben.

Bei der Frage nach einem "einfachen" Primzahlalgorithmus denkt mancher möglicherweise an so etwas schönes und simples wie die Rekursionsvorschrift der Fibonacci-Folge, die gerade in ihrer expliziten Darstellung ein interessantes Werkzeug bietet.
Die Primzahlen aber auf so etwas herunterbrechen zu wollen ist halt weitaus schwieriger als man sich das vorstellen mag. Für Neueinsteiger in dieses Thema kann es sicher nicht schaden, wenn man erst einmal beim Sieben und ein paar einfachen Sätzen zum Primzahlsatz anfängt.

BlackFlame schrieb:Die Primzahlen aber auf so etwas herunterbrechen zu wollen ist halt weitaus schwieriger als man sich das vorstellen mag. Für Neueinsteiger in dieses Thema kann es sicher nicht schaden, wenn man erst einmal beim Sieben und ein paar einfachen Sätzen zum Primzahlsatz anfängt.

Schwierig?

Es funktioniert schlicht und ergreifend nicht. Primzahlen sind wie die Atome von Zahlen. Rekursive Algorithmen kann man nur verwenden wenn Dinge auch rekurisv aufgebaut sind. Da aber jede Primzahl nur aus sich selbst und nicht aus anderen Primzahlen besteht, kann man rekursive Algorithmen zur Primzahlberechnung getrost in die Tonne treten. Konsequenterweise sind Primtests iterativ.

@interpreter
Ich muss vielleicht kurz etwas vorwegnehmen:
Wenn ich in den letzten Jahren immer wieder mal auf Primzahlen angesprochen wurde, so kamen immer wieder ähnliche Fragen. Warum ist die Bestimmung von großen Primzahlen so schwierig und zeitaufwändig? Wieso scheint ein Vorhersagemodelle so schwer oder gar unmöglich zu finden zu sein? Warum haben Primzahlen für Verschlüsselungen solch eine Bedeutung? etc.
Manche fragen, die man immer und immer wieder hört, kamen ja auch in dieser Diskussion wieder auf.

Mal eben den Primzahlsatz und alle Folgesätze zu erwähnen, zwischendurch noch zu erklären, was der Integrallogarithmus ist, anschließend noch auf die Primzahlsätze von Fermat, Dirichlet, usw. einzugehen und eigentlich noch lange nicht fertig mit dem Thema zu sein, erschien mir da schon immer etwas abwegig, vor allem wenn ich jemanden vor mir sitzen hatte, für den fast alles, was ich dann erzählt hätte, pures Fachchinenisch gewesen wäre.

Daher versuchte ich dann zu ergründen, was sich jemand vorstellt, wenn er danach fragt, warum man Primzahlen nicht mal so nebenbei in den Griff bekommt.
Im Kontext dieser Diskussion vermute ich mal, dass man, wenn man erstmal den Wikipedia-Artikel zur Fibonacci-Folge überflogen hat, hinsichtlich der Primzahlen auch an erstmal an einen rekursive Lösungsversuch denkt.
Dementsprechend erinnere mich auch daran, wie ich mich vor vielen Jahren an solchen Dingen versucht hatte als ich noch keinen blassen Schimmer von Zahlentheorie und den Ausmaßen der Primzahlproblematik hatte.

Jetzt im einzelnen aufzuzählen, was alles nicht geht, würde eine ganze Weile dauern, so dass ich eben erst einmal ein paar einfache Überlegungen aufbringen wollte, die so manchem vielleicht klar werden lassen, warum es eben doch nicht so einfach ist, wie es im ersten Moment erscheinen mag.

@BlackFlame
Ahja .. das waren noch Zeiten.
Auch ich hab mal zur Schulzeit ohne Ahnung von Zahlentheorie versucht statistische Relationen zwischen den Primzahlen zuerfassen. (früher gabs .. ist lange her.. noch kein #Neuland - da hat man seinen Computer nur für sowas benutzt)


Es wurde eingeworfen das 'neuere' Verfahren wie das Elliptic Curve Cryptography keine Primzahlen benötigt. ICh möchte aber darauf Hinweisen das die bekannte asymetrische Verschlüsselung mit Primzahlfaktoren bereits mit gehobenen Schulbildung nachzuvollziehen und sogar mit Stift, Papier und kleinen Primzahlen durchzuführen ist.

Das Primzahlverfahren ist KISS (Keep it simple and stupid) und die Mathematik dazu geht bis in die Antike zurück. Beides Eigenschaften die für das Vertrauen in die Sicherheit und Zuverlassigkeit eines Kryptosystems unerlässlich sind. Das ECC Verfahren ist meines erachtens noch nicht ausreichend getestet, der mathematische Background ist vielfach schwerer zuverstehen und möglicherweise hat der NSA bereits ein Zeroday-exploid in der Hinterhand. Bei jungen Verfahren haben die Schwergewichte der Sicherheitsbranche meist einen Vorsprung zu den öffentlichen Wissenschaften.. seis nur weil die Geheimdienste die besten Experten selber beschäftigen.

Im Übrigen ist es völlig egal für die Sicherheit der Primzahlfaktor Verschlüsselung ob die Primzahlen 'allgemein' bekannt sind oder nicht .. Hauptsache es ist nicht bekannt welche beiden Primzahlen für die Bildung des Schlüsselpaares verwendet wurden.

Rhythm schrieb:Das einzige vernünftige was du mit der Fibonacci machen kannst ist im Roulette eine garantiert verlierende Abstreich Progression spielen.

Is klar. Wer braucht schon Mathe und wozu, gell? Da kommen am Schluss doch eh nur Zahlen und Buchstaben raus :)

@BlackFlame

BlackFlame schrieb:Das Problem Primzahlen konkret benennen zu wollen führt halt immer wieder auf ein paar grundlegende Überlegungen zurück:
Entweder man benutzt Algorithmen, wie etwa das Sieb von Erathosthenes und arbeitet sich halt systematisch durch die natürlichen Zahlen und schaut nach einer Weile mal nach, was dieses Sieb durchgelassen hat,
oder man stellt sich der allgemeinen Frage, ob Primzahlen neben ihrer sonderbaren Teilbarkeitseigenschaft, noch weitere Eigenschaften besitzen, die es ermöglichen solche Zahlen von allen anderen zu unterscheiden.

Richtig...und ich meine da eben nicht die Siebalgorithmen, sondern wirklich einen "Beweis", wenn man das denn so nennen kann. Du hast ja auch schon einige Sätze genannt. Gibt's da eventuell auch irgendwo einen Darstellungssatz? Das wäre ja vielleicht schonmal ein Anfang. Aber vielleicht ist das aber auch die falsche Herangehensweise. Mein Ansatz wäre dann nämlich eben das, was du schon geschrieben hast: Was haben Primzahlen, außer ihrer Eigenschaft, nur durch sich selbst und dem neutralen Element teilbar zu sein, noch so Besonderes an sich, was andere Zahlen nicht haben? Oder: Kann man irgendwo etwas finden (bestimmte Algebren, Sätze etc.), wo man als "Spezialfall" auf Primzahlen kommt?

@mastermind
Zahlentheoretisch ist mir keine Eigenschaft bekannt, die wirklich eindeutig und allgemeingültig ist.
Es gibt bekanntermaßen Möglichkeiten eine gewisse Teilmenge der Primzahlen zu erfassen. Die allgemein bekanntesten dürften wohl die Primzahlzwillinge und die Rückführung auf 2er Potenzen plus 1 sein.
Aber derlei Methoden erfassen eben immer nur Teilmengen und verändern halt auch nur die Darstellung einer Primzahl. Mit Hilfe von 1+2^n bekommt man eben nicht für alle n eine Primzahl heraus und eine Vorschrift zu entwickeln, für welche n nun eine Primzahl herauskommt, ist an sich auch nicht einfacher als direkt alle natürlichen Zahlen zu betrachten.

Ansonsten fällt mir im Zusammenhang mit Primzahlen noch die riemannsche Vermutung ein, welche nach wie vor zu einem der größten mathematischen Probleme der heutigen Zeit gehört.
Allerdings ist die Riemannsche Zetafunktion ein ziemlicher Koloss.

@BlackFlame
Ok...naja, ich finde es schon bemerkenswert, dass gerade diese Zahlen so ein großes Problem aufweisen. Die Riemannsche Vermutung also, muss ich mal nachschauen.

@Charlie806

Charlie806 schrieb am 14.07.2013:Wie kommt man darauf, dass 165580141 = 2789 x 59369 ist?
Gibts da irgendeinen Trick?

Wenn du nur mal schnell ein paar einzelne Zahlen überprüfen willst und dich nicht mit Programmierung herumschlagen willst, dann geh auf www.wolframalpha.com und gib "165580141 divisors" ein. Fertig.

Leider stimmt diese Aussage nicht. Mit den ersten Zahlen stimmts. Aber die 19 ist ebenfalls eine Primzahl, aber die 19. Fibonacci-Zahl ist die 4181 und die ist keine Primzahl!