Millionär durch Primzahlenformel?

[Gast]

Wenn ich die weltweit gesuchte Formel hätte, mit der ich sagen könnte,
welche die x.-te Primzahl ist, inwiefern könnte ich damit dann sehr schnell sehr viel Geld verdienen?


Was nutzt mir das z.B: bei Verschlüsselungsverfahren wie AES?

[ESAD]

garnichts

[Shink]

Es nutzt vielleicht jemandem etwas bei asymmetrischen Verschlüsselungsverfahren.

Ab und zu werden Preise für wissenschaftliche Themen ausgeschrieben.
Ansonsten könntest du hoffen bei einer rennomierten Universität (ala MIT) als Forschungsassistent aufgenommen zu werden.

[Yavion]

Wenn ich die weltweit gesuchte Formel hätte, mit der ich sagen könnte,
welche die x.-te Primzahl ist, inwiefern könnte ich damit dann sehr schnell sehr viel Geld verdienen?


Was nutzt mir das z.B: bei Verschlüsselungsverfahren wie AES?

Die Formel, bzw ein Algorithmus, der dir sagt, was die n-te Primzah ist, ist nicht das Problem.
Es gibt zwei andere Probleme:
1. Der Algorithmus muss schnell sein (also auch für so Dinge wie X*10^21+1)
2. Er muss korrekt sein. Es gibt recht effektive Verfahren um Primzahlen mit einer gewissen Wahrscheinlichkeit zu generieren. Mersennsche Primzahlen z.B.

Dummerweise kann man damit aber nicht prüfen, ob eine gegebene Zahl Prim ist.

[Gast]

Hallo,

wenn du siwas hast, veröffentliche es. Wenn es von Experten geprüft wurde, bekommst du sicher den Mathematik Nobelpreis und der ist mit >1 Mio dotiert.


Ein Mathematik Lehrstuhl an einer Uni mit gutem Einkommen, sollte die auch sicher sein.

mfg

[Shink]

Wenn es von Experten geprüft wurde, bekommst du sicher den Mathematik Nobelpreis und der ist mit >1 Mio dotiert.
Scherzkeks:freak:

Nur der Vollständigkeit halber: Es gibt keinen Nobelpreis für Mathematik.
http://de.wikipedia.org/wiki/Nobelpreis#Preiskategorien

[Gast]

Scherzkeks:freak:

Nur der Vollständigkeit halber: Es gibt keinen Nobelpreis für Mathematik.
http://de.wikipedia.org/wiki/Nobelpreis#Preiskategorien

Mit "Mathematik-Nobelpreis" meinte er sicherlich die Fields-Medaille.

[Gast]

Die Formel, bzw ein Algorithmus, der dir sagt, was die n-te Primzah ist, ist nicht das Problem.

Doch, denn Formel und Algorithmus ist nicht das gleiche.

Ein Algorithmus kann auch einer Schleife bestehen und alle Zahlen von 1-5 Milliarden durchtesten, ehe er die 73 Millionste Primzahl findet.

Eine Formel ist da anders, du gibst die 73 Millionen für ein x und erhälst dann sofort die 73 Millionste Primzahl.
Das sind Unterschiede wie Tag und Nacht.



Es gibt zwei andere Probleme:
1. Der Algorithmus muss schnell sein (also auch für so Dinge wie X*10^21+1)

Wie schon gesagt, Formel != Algorithmus.



2. Er muss korrekt sein. Es gibt recht effektive Verfahren um Primzahlen mit einer gewissen Wahrscheinlichkeit zu generieren. Mersennsche Primzahlen z.B.

Ja, algorithmische Verfahren mit mehreren durchläufen, aber keine Formel!

[Yavion]

Doch, denn Formel und Algorithmus ist nicht das gleiche.

Ein Algorithmus kann auch einer Schleife bestehen und alle Zahlen von 1-5 Milliarden durchtesten, ehe er die 73 Millionste Primzahl findet.

Eine Formel ist da anders, du gibst die 73 Millionen für ein x und erhälst dann sofort die 73 Millionste Primzahl.
Das sind Unterschiede wie Tag und Nacht.



Wie schon gesagt, Formel != Algorithmus.



Ja, algorithmische Verfahren mit mehreren durchläufen, aber keine Formel!

Nö. Aus Sicht eines Computer gibt es da keinen Unterschied. Es ist eine Turing-Maschine und die arbeitet mit Algorithmen, egal wie hüpsch Du sie als Formel aufschreibst.

[Gast]

Auch Formeln kann man iterativ oder rekursiv anschreiben (bzw. manche muss man). Wer glaubt es gibt es gibt nur Formeln mit fester Rechenzeit hat es wohl noch nicht in die Oberstufe geschafft...

mfg,
zgep

[Pinoccio]

Auch Formeln kann man iterativ oder rekursiv anschreiben (bzw. manche muss man). Wer glaubt es gibt es gibt nur Formeln mit fester Rechenzeit hat es wohl noch nicht in die Oberstufe geschafft...

mfg,
zgepAber er hat doch schon eine Formel EINE FORMEL!!!1 für die n.-te Primzahl gefunden!

Damit Geld verdienen? Direkt keins, höchsten Auftrittsgage bei JKB und Co. Verschlüsselung knacken? AES ganz sicher nciht und auch RSA ist nicht durch sowas bedroht. Faktorisirung ist ein anderes Problem.
Was nicht heißt, daß der Weg zur Formel nicht möglicherweise auch Ideen liefert, schneller zu faktorisieren, aber die Formel allein bringt da garnichts.

mfg

[MaxistXXL]

Es mit dem ASK (?)-Verfahren in Linearzeit (exakt: O((log n)^(3+epsilon)) möglich, eine Zahl sicher auf Primalität zu prüfen. Man könnte sich also eine beliebige Zahl hernehmen und problemlos testen, auch die Mersenne-Primzahlen. Es wäre durchaus interessant zu wissen, ob das schon bei PRIME95 einzug erhalten hat.

Ob es einen effizienten Algorithmus gibt, der dir die n. Primzahl gibt weiß ich nicht. Ich denke aber, dass dieser die Sicherheit von Verschlüsselungen, die auf Primfaktorzerlegung basieren, erheblich untergraben würde, denn man könnte einfach alle Primzahlen bis zur Wurzel der zu zerlegenden Zahl durchprobieren. Geht jetzt auch schon, aber das finden von aufeinanderfolgenden Primzahlen ist halt aufwändig.

[Pinoccio]

Es mit dem ASK (?)-Verfahren in Linearzeit (exakt: O((log n)^(3+epsilon)) möglich, eine Zahl sicher auf Primalität zu prüfen. Man könnte sich also eine beliebige Zahl hernehmen und problemlos testen, auch die Mersenne-Primzahlen. Es wäre durchaus interessant zu wissen, ob das schon bei PRIME95 einzug erhalten hat.Erstens ist das keine Linearzeit und zweitens (siehe unten) machst du dir falsche Vorstellungen von der Größe der Zahlen.Ob es einen effizienten Algorithmus gibt, der dir die n. Primzahl gibt weiß ich nicht. Ich denke aber, dass dieser die Sicherheit von Verschlüsselungen, die auf Primfaktorzerlegung basieren, erheblich untergraben würde, denn man könnte einfach alle Primzahlen bis zur Wurzel der zu zerlegenden Zahl durchprobieren. Geht jetzt auch schon, aber das finden von aufeinanderfolgenden Primzahlen ist halt aufwändig.Nö. Es gibt über 10^160 Primzahlen mit 512 Bit wie man sie für RSA mit 1024 Bit gebrauchen könnte. Da besteht überhaupt gar keine Chance, die jemals irgendwie zu speichern geschwiege denn alle zu testen.

(Zahlen ausm Kopf geschätz und abgerundet, die wahren Werte liegen deutlich höher/edit: siehe #14)

mfg

[MaxistXXL]

Erstens ist das keine Linearzeit
So? (log n)^3 <= n genau dann, wenn log n <= n^(1/3). Soll ich noch beweisen, dass der Logarithmus asymptotisch langsamer wächst als die 3. Wurzel von irgendwas?


Es gibt über 10^160 Primzahlen mit 512 Bit

Es sind ca 3 * 10^151 Primzahlen. Nicht, dass das einen Unterschied machen würde. Dann hat Primzahlen bestimmen zu können also keinen Einfluss darauf, wie leicht man Zahlen faktorisieren kann. Schade...

[AlSvartr]

Ich glaube hier entsteht die Verwirrung, weil n die geprüfte Zahl ist. Betrachtet man aber die EingabeLÄNGE, also die Anzahl an Bits (oder Trits oder was auch immer ;)), dann ist das ja gerade log n. Mit m=log n als Länge der Eingabe ists also O(m^3) und das ist sicher nicht linear oder sonstwas ;(

[Gast]

Erstens ist das keine Linearzeit und zweitens (siehe unten) machst du dir falsche Vorstellungen von der Größe der Zahlen.Nö. Es gibt über 10^160 Primzahlen mit 512 Bit wie man sie für RSA mit 1024 Bit gebrauchen könnte. Da besteht überhaupt gar keine Chance, die jemals irgendwie zu speichern geschwiege denn alle zu testen.


(10^160*512)/8 sind
58207660913467407226562500000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000 TByte.


Meine Festplatte kann gerademal 1 Tbyte speichern.

[pest]

gibbet schon p(n) liefert n. Primzahl

http://www.matheboard.de/latex2png/latex2png.php?p(n)=1+\sum_{j=1}^{2^n}f(n,\pi(j))

http://www.matheboard.de/latex2png/latex2png.php?f(x,y)=1/2%20(1+\frac{x-y}{|x-y|})

bzw. f(x,y)=0 für x=y

http://www.matheboard.de/latex2png/latex2png.php?\pi(n)=-1+\sum_{i=3}^n%20((i-2)!-i%20\lfloor(%20\frac{(i-2)!}{i})%20\rfloor)


"Explicit formulas exist for the nth prime both as a function of n and in terms of the primes 2, ..., p_(n-1)
(Hardy and Wright 1979, pp. 5-6, 344-345, and 414; Guy 1994, pp. 36-41), a number of which are given below.
However, it should again be emphasized that these formulas are extremely inefficient, and in many (if not all) cases,
simply performing an efficient sieving would yield the primes much more quickly and efficiently."


:tongue:

[BAGZZlash]

Interessante Formeln. Meint


http://www.matheboard.de/latex2png/latex2png.php?f(x,y)=1/2%20(1+\frac{x-y}{|x-y|})


eigentlich

http://www.matheboard.de/latex2png/latex2png.php?f(x,y)=\frac{1}{2}\left(1+\frac{x-y}{|x-y|}\right)

?

Falls ja, gilt dann nicht eigentlich einfach

http://www.matheboard.de/latex2png/latex2png.php?f(x,y)=\begin{cases} 1, & \text{für } x > y \\ 0, & \text{sonst}\end{cases}

gegeben

http://www.matheboard.de/latex2png/latex2png.php?x,y \in \mathbb R ^{+}

?

[Oblivion]

Sobald x-y < 0 folgt f(x,y) = 0
Bei x-y > 0 folgt f(x,y) = 1

Das gilt für ganz R, nicht nur R+

[BAGZZlash]

Sobald x-y < 0 folgt f(x,y) = 0
Bei x-y > 0 folgt f(x,y) = 1

Das gilt für ganz R, nicht nur R+
Ja, so kann man's natürlich auch formulieren. Danke, wollt' ich nur wissen.

[ux-3]

Für die Größenordnung: 10^160 ist weitaus mehr als es (vermutlich) Elementarteilchen im Universum gibt. Selbst Chuck Norris wird die Mittagspause zum Abzählen brauchen!

[Lyka]

nur mal so OT: hat da jemand Pi gesehen? Super Film mit Pi als Allmachts-Zahl.