Hallo Zusammen,
ich programmiere gerade den RSA-Algorithmus und stehe nun vor dem Problem, dass ich Primzahlen raten muss…
Testen ob es eine Primzahl ist oder nicht, dafür gibts ja mehrere verfahren… solvay-strassen, miller-rabin usw
aber gibts ne formel bei der man ne grosse wahrscheinlichkeit hat eine primzahl zu raten?
hab mal gehört n²+n+17 wäre sowas…
gibts noch was besseres?
lg
Tach,
ich bin nu kein Zahlentheoretiker, aber wenn sonst keiner eine Idee hat:
Meines Wissens ist das momentan schnellste Verfahren, eine Zahl entsprechend zu testen, das AKS-Verfahren, siehe z.B. http://www.cse.iitk.ac.in/users/manindra/algebra/pri…
Sieht auch vernuenftig programmierbar aus. Ansonsten koennten auch starke Pseudoprimzahlen reichen.
Gruss
Paul
ich programmiere gerade den RSA-Algorithmus und stehe nun vor
dem Problem, dass ich Primzahlen raten muss…
aber gibts ne formel bei der man ne grosse wahrscheinlichkeit
hat eine primzahl zu raten?
Hallo,
wenn du damit Verschlüsselung machen willst, ist es keine besonders gute Idee, so eine Formel zu verwenden, weil die dadurch erzeugten Zahlen einfach mit größerer Wahrscheinlichkeit von einem Angreifer durchprobiert werden könnten. Also: jede Primzahl im passenden Größenbereich sollte die gleiche Wahrscheinlichkeit haben, von dir verwendet zu werden.
Nachdem du den Rabin-Miller zum Test der durch die Formel erzeugten Zahlen ohnhin brauchst (und der wirklich recht zügig werkelt), sparst du nur Prozessorzeit zu Lasten der Sicherheit des resultierenden Schlüssels.
Grüße, guidot
Hallo,
wenn du damit Verschlüsselung machen willst, ist es keine
besonders gute Idee, so eine Formel zu verwenden, weil die
dadurch erzeugten Zahlen einfach mit größerer
Wahrscheinlichkeit von einem Angreifer durchprobiert werden
könnten. Also: jede Primzahl im passenden Größenbereich sollte
die gleiche Wahrscheinlichkeit haben, von dir verwendet zu
werden.
Nachdem du den Rabin-Miller zum Test der durch die Formel
erzeugten Zahlen ohnhin brauchst (und der wirklich recht zügig
werkelt), sparst du nur Prozessorzeit zu Lasten der Sicherheit
des resultierenden Schlüssels.Grüße, guidot
Hätte ich auch selbst drauf kommen können, das man die Menge der potentiellen Kandidaten nicht verkleinern sollte, da es ja ein wesentliches Sicherheitskriterium ist…
Falls man das doch tut, könnte man ja gleich kleinere Zahlen nehmen…
Danke Dir für die Erleuchtung
lg ruwn
Hossa 
aber gibts ne formel bei der man ne grosse wahrscheinlichkeit
hat eine primzahl zu raten?
Alle Primzahlen p>3 kann man entweder als 6n-1 oder als 6n+1 darstellen:
6\*1-1 = 5
6\*1+1 = 7
6\*2-1 = 11
6\*2+1 = 13
6\*3-1 = 17
6\*3+1 = 19
6\*4-1 = 23
6\*4+1 = 25 ACHTUNG!!!
6\*5-1 = 29
6\*5+1 = 31
Wie das Beispiel 6*4+1=25 zeigt, gilt aber nicht die Umkehrung. Du kannst also nicht mit Sicherheit sagen, dass 6n-1 bzw. 6n+1 eine Primzahl sein muss!!! Vielmehr liefert dir dieser „Trick“ mögliche Kandidaten für Primzahlen. Ob es wirklich eine Primzahl ist, musst du dann unbedingt noch testen!
hab mal gehört n²+n+17 wäre sowas…
Das ist falsch. Für n=16 ergibt sich:
16² + 16 + 17 = 256 + 33 = 289 = 17*17
Viele Grüße
Hasenfuß
Guten Tag,
ist es denn auch geschickter so zahlen zwischen 2^1024 und 2^1025 -1 zu raten?
Ich wollte jetzt schon irgendeine ungerade Zahl raten.
Mit der formel schliesse ich allerdings noch alle ungeraden Zahlen die durch 3 teilbar sind aus…
so schliesse ich nicht nur jede 2. sondern auch noch jede 6. Zahl aus. Also 4/6 aller zahlen.
was ist denn besser?
eine abfrage:
x mod 2 = 0
zwei abfragen:
x mod 2 =0 && x mod 3 =0
6n +m // m ist dann zufällig +1 oder -1
6n+1 und 6n-1
x mod 2 = 0 wäre eine abfrage womit ich 50% ausschliessen könnte x mod 3 =0 im anschluss, würde wohl nur weitere 16.6% der zahlen ausschliessen, was wohl lange nicht so effektiv ist…
und die beiden formeln zu implementieren kostet wahrscheinlich sowieso zuviel zeit…
danke für die mühe, aber ich glaube, dass es keine zeitvorteil bringt