Forum: FPGA, VHDL & Co. pseudozufällige Primzahlen generieren


von highfrequency (Gast)


Lesenswert?

Hallo.
Bekannterweise besteht die Möglichkeit Pseudozufallszahlen per LFSRs zu 
erzeugen.
Kann man auch pseudozufällige Primzahlen hardwareseitig erzeugen?
Wenn ja, würde ich mich über kurze Erklärungen oder Lesetipps freuen.

von highfrequency (Gast)


Lesenswert?

Im Elektronikkompendium steht dazu dass es die Möglichkeit gibt, 
Pseudozufallszahlen zu generieren und anschließend zu testen, ob es sich 
bei der Zahl um eine Primzahl handelt. Wenn nicht, erzeuge neue 
Zufallszahl, so lange bis eine Primzahl erzeugt wurde.

Da stellt sich mir die andere Frage: Wie überprüfe ich hardwareseitig ob 
es sich bei einer Zahl um eine Primzahl handelt?
Das erscheint mir extrem ineffizient.

von Markus F. (mfro)


Lesenswert?

highfrequency schrieb:
> Da stellt sich mir die andere Frage: Wie überprüfe ich hardwareseitig ob
> es sich bei einer Zahl um eine Primzahl handelt?

Das macht die elektronische Hardware genauso wie die biologische: man 
versucht die Zahl durch alle kleineren Zahlen zu teilen. Wenn dabei bei 
jedem Versuch ein Rest bleibt, ist die Zahl eine Primzahl.

highfrequency schrieb:

> Das erscheint mir extrem ineffizient.

Ineffizient? Es gibt keinen anderen Weg, keine Abkürzung für die 
Primfaktorzerlegung. Gerade das macht Primzahlen ja für die 
Kryptographie so interessant.

von Arc N. (arc)


Lesenswert?

highfrequency schrieb:
> Hallo.
> Bekannterweise besteht die Möglichkeit Pseudozufallszahlen per LFSRs zu
> erzeugen.
> Kann man auch pseudozufällige Primzahlen hardwareseitig erzeugen?
> Wenn ja, würde ich mich über kurze Erklärungen oder Lesetipps freuen.


Gegenfrage: Warum sollten sich bspw. die Algorithmen z.B. aus OpenSSL 1) 
nicht in Hardware gießen lassen?

1) Mal in den Quelltexten unter https://github.com/openssl/openssl 
suchen

von Walter K. (walter_k488)


Lesenswert?

Markus F. schrieb:
> Das macht die elektronische Hardware genauso wie die biologische: man
> versucht die Zahl durch alle kleineren Zahlen zu teilen. Wenn dabei bei
> jedem Versuch ein Rest bleibt, ist die Zahl eine Primzahl.

Naja ... es fallen schon mal alle Zahlen mit der letzten Ziffer von 0 
und 2 und 4 und 5 und 6 und 8 durch den Filter, somit sind 60% außen vor

Dh es bleiben nur die Zahlen mit der Endziffer 1, 3, 7 und 9 als 
Primzahlkanditaten

Diese Menge reduzieren wir noch um alle die Zahlen deren Quersumme 3 
oder ein Vielfaches von 3 ergibt - und um die deren letzte 2 Ziffern 
eine Quersumme von 3 oder ganzzahliges Vielfaches davon ergeben ...

von J. S. (engineer) Benutzerseite


Lesenswert?

Das Thema ist hier schon mehrfach in unterschiedlichsten threads 
diskutiert worden: LSFR erzeugen bedingt gute Zufallsfolgen. Die nimmt 
man nur, wenn es auf Gleichverteilung ankommt wie beim Rauschspektrum. 
Zufallszahlen, bei denen auch einzelne Werte mehrfach kommen sollen, 
bevor andere kommen und trotzdem balancierte Verteilung haben, erzeugt 
man mit Vertauschern, also "zufällig" durchlaufend abgefragten Tabellen. 
Damit lässt sich das Auftreten regeln und bestimmen, so nötig.

In eine solche Tabelle könnte man Primzahlen ein bauen. Dann muss nichts 
geprüft werden.

Es gibt dazu eine Reihe von unterschiedlichen Verfahren, implizite 
Zahlenfolgen mit "Verdrehung" zu generieren, die deterministisch sind, 
scheinbar auch nicht voraussagbar, aber trotzdem eine gute Verteilung 
liefern, wie Mersenne, Marsaglia oder z.B. PCG.

Richtigen Zufall gibt es nur mit zufälligem Rauschen wie hier:
Digitaler Rauschgenerator im FPGA

Gfs auch mit Zugriff auf Tabellenwerte und damit einem definierten 
Wertebereich, aber in der Auftrittswahrscheinlichkeit nicht mehr 
vorhersehbar und nicht balanciert. Es kann dann also sein, dass einige 
Werte dauernd kommen und andere nie und nach jedem Einschalten ist das 
Verhalten anders.

von highfrequency (Gast)


Lesenswert?

Markus F. schrieb:
> highfrequency schrieb:
>
>> Das erscheint mir extrem ineffizient.
>
> Ineffizient? Es gibt keinen anderen Weg, keine Abkürzung für die
> Primfaktorzerlegung. Gerade das macht Primzahlen ja für die
> Kryptographie so interessant.

Irgendwie fühle ich mich jetzt ertappt, so viel Lerntransfer sollte man 
halt haben :)

Arc N. schrieb:
> 1) Mal in den Quelltexten unter https://github.com/openssl/openssl
> suchen

Ich bevorzuge Algorithmen in Pseudocode, aber trotzdem danke :)

Zu deiner Gegenfrage: Ja klar, das lässt sich natürlich in Hardware 
gießen.

Walter K. schrieb:
> Naja ... es fallen schon mal alle Zahlen mit der letzten Ziffer von 0
> und 2 und 4 und 5 und 6 und 8 durch den Filter, somit sind 60% außen vor
>
> Dh es bleiben nur die Zahlen mit der Endziffer 1, 3, 7 und 9 als
> Primzahlkanditaten
>
> Diese Menge reduzieren wir noch um alle die Zahlen deren Quersumme 3
> oder ein Vielfaches von 3 ergibt - und um die deren letzte 2 Ziffern
> eine Quersumme von 3 oder ganzzahliges Vielfaches davon ergeben ...

Danke für den Tipp.

von Gustl B. (-gb-)


Lesenswert?

Wieviel Bit sollen die generierten Zahlen haben?

Ich würde die Primzahlen in einer Tabelle hinterlegen, in einem ROM. Und 
da dann beliebig drauf zugreifen und quasi eine Primzahl "ziehen".

Bei 16 Bits sind das 6542 Zahlen, also 13,084 kBytes. Das finde ich 
relativ wenig und man kann wirklich sehr schnell und ohne weitere 
Überprüfung Zahlen generieren.

von Sebastian V. (sebi_s)


Lesenswert?

Markus F. schrieb:
> man
> versucht die Zahl durch alle kleineren Zahlen zu teilen. Wenn dabei bei
> jedem Versuch ein Rest bleibt, ist die Zahl eine Primzahl.

Es reicht bis zur der Quadratwurzel der Zahl (einschließlich) zu testen. 
Wenn man bis dahin keinen Faktor gefunden hat findet man auch keinen 
mehr.

von J. S. (engineer) Benutzerseite


Lesenswert?

highfrequency schrieb:
> Walter K. schrieb:
>> Naja ... es fallen schon mal alle Zahlen mit der letzten Ziffer von 0
>> und 2 und 4 und 5 und 6 und 8 durch den Filter, somit sind 60% außen vor
>>
>> Dh es bleiben nur die Zahlen mit der Endziffer 1, 3, 7 und 9 als
>> Primzahlkanditaten
>>
>> Diese Menge reduzieren wir noch um alle die Zahlen deren Quersumme 3
>> oder ein Vielfaches von 3 ergibt - und um die deren letzte 2 Ziffern
>> eine Quersumme von 3 oder ganzzahliges Vielfaches davon ergeben ...

Das ließe sich auch leicht generisch formulieren, indem man ausser der 2 
gerade Zahlen gar nicht erzeugt und einen parallelen Generator die 
Vielfachen der elementaren Primzahlen wie eben 3,5,7,11,13 etc 
ausblenden lässt.

Das Problem der subtraktiven Synthese, wie sie oben vorgestellt wird, 
dass auch eine Menge Datenmüll erzeugt wird, der weggefiltert werden 
muss. Das wird dann bei höheren Ordnungen recht langsam und in der 
Praxis unbrauchbar.

In den Anwendungen, die mir bisher begegnet sind, in denen dedizierte 
Werte wie eben Primzahlen benötigt wurden, sind die offline erzeugt, 
validiert und dann hinterlegt worden. Das gilt für gemischte und 
getauschte AES-Codes etc...

Es reicht ja nicht, die Zahl zu erzeugen, sie muss auch plausibilisiert 
werden und das ist bei Primzahlen nicht Echtzeit problematisch. Also 
muss ich alles in der design phase checken und dann HABE ich alle 
Lösungen parat.

: Bearbeitet durch User
von highfrequency (Gast)


Lesenswert?

Gustl B. schrieb:
> Wieviel Bit sollen die generierten Zahlen haben?

1024.

Jürgen S. schrieb:
> Es gibt dazu eine Reihe von unterschiedlichen Verfahren, implizite
> Zahlenfolgen mit "Verdrehung" zu generieren, die deterministisch sind,
> scheinbar auch nicht voraussagbar, aber trotzdem eine gute Verteilung
> liefern, wie Mersenne, Marsaglia oder z.B. PCG.

Danke, das sagt mir bisher noch nichts aber darüber werde ich mich 
informieren.

von Sven B. (scummos)


Lesenswert?

Walter K. schrieb:
> Markus F. schrieb:
>> Das macht die elektronische Hardware genauso wie die biologische: man
>> versucht die Zahl durch alle kleineren Zahlen zu teilen. Wenn dabei bei
>> jedem Versuch ein Rest bleibt, ist die Zahl eine Primzahl.
>
> Naja ... es fallen schon mal alle Zahlen mit der letzten Ziffer von 0
> und 2 und 4 und 5 und 6 und 8 durch den Filter, somit sind 60% außen vor
>
> Dh es bleiben nur die Zahlen mit der Endziffer 1, 3, 7 und 9 als
> Primzahlkanditaten
>
> Diese Menge reduzieren wir noch um alle die Zahlen deren Quersumme 3
> oder ein Vielfaches von 3 ergibt - und um die deren letzte 2 Ziffern
> eine Quersumme von 3 oder ganzzahliges Vielfaches davon ergeben ...

Das klingt zwar irgendwie schlüssig, ist aber Unsinn. Diese Dinge sind 
Eigenschaften der gewählten Darstellung der Zahl, nicht der Zahl selbst. 
Dadurch kann man nichts sparen.

Interessant ist vermutlich eher dieses Verfahren: 
https://en.wikipedia.org/wiki/Fermat_primality_test

: Bearbeitet durch User
von Nils P. (torus)


Lesenswert?

Jürgen S. schrieb:
> Das Problem der subtraktiven Synthese, wie sie oben vorgestellt wird,
> dass auch eine Menge Datenmüll erzeugt wird, der weggefiltert werden
> muss. Das wird dann bei höheren Ordnungen recht langsam und in der
> Praxis unbrauchbar.

Da es bislang keine Alternative zu der "Subtraktiven Synthese" gibt wird 
uns wohl nichts weiters übrig bleiben als weiterhin Zufallszahlen zu 
generieren und die durch den Miller-Rabin Test zu schicken.

von Walter K. (walter_k488)


Lesenswert?

Sven B. schrieb:
> Walter K. schrieb
> Naja ... es fallen schon mal alle Zahlen mit der letzten Ziffer von 0
> und 2 und 4 und 5 und 6 und 8 durch den Filter, somit sind 60% außen vor
> Dh es bleiben nur die Zahlen mit der Endziffer 1, 3, 7 und 9 als
> Primzahlkanditaten
> Diese Menge reduzieren wir noch um alle die Zahlen deren Quersumme 3
> oder ein Vielfaches von 3 ergibt - und um die deren letzte 2 Ziffern
> eine Quersumme von 3 oder ganzzahliges Vielfaches davon ergeben ...
>>......
> Das klingt zwar irgendwie schlüssig, ist aber Unsinn. Diese Dinge sind
> Eigenschaften der gewählten Darstellung der Zahl, nicht der Zahl selbst.
> Dadurch kann man nichts sparen.
>


Wenn das Unsinn ist, dann teste halt alle ungeraden Zahlen - lach

: Bearbeitet durch User
von J. S. (engineer) Benutzerseite


Lesenswert?

Nils P. schrieb:
> Da es bislang keine Alternative zu der "Subtraktiven Synthese" gibt wird
> uns wohl nichts weiters übrig bleiben als weiterhin Zufallszahlen zu
> generieren und die durch den Miller-Rabin Test zu schicken.

Die Frage ist, wie und man man die Wertemenge erzeugt. Das in Echtzeit 
zu machen (so lese Ich den o.g. Ansatz) ist für mich nicht zielführend.

von Gustl B. (-gb-)


Lesenswert?

highfrequency schrieb:
> Gustl B. schrieb:
>> Wieviel Bit sollen die generierten Zahlen haben?
>
> 1024.

Sorry, aber das ist grober Unsinn. Das ist eine Dezimalzahl von über 300 
Stellen. Oder meinst du Primzahlen bis 1024? Also 10 Bits?

von Nils P. (torus)


Lesenswert?

Jürgen S. schrieb:
> Nils P. schrieb:
>> Da es bislang keine Alternative zu der "Subtraktiven Synthese" gibt wird
>> uns wohl nichts weiters übrig bleiben als weiterhin Zufallszahlen zu
>> generieren und die durch den Miller-Rabin Test zu schicken.
>
> Die Frage ist, wie und man man die Wertemenge erzeugt. Das in Echtzeit
> zu machen (so lese Ich den o.g. Ansatz) ist für mich nicht zielführend.

Sobald jemand rausbekommt, wie man Primzahlen vorhersagen kann ist er 
ganz klarer Kandidat für die Field Medallie (Der Nobelpreis für 
Mathematiker).

Bis dahin bleibt nur der Weg Zufallszahlen zu generieren und so lange 
auf Prime zu prüfen bis man glück hat.

Klingt doof und ineffizient, ist aber so.

von highfrequency (Gast)


Lesenswert?

Gustl B. schrieb:
> highfrequency schrieb:
>> Gustl B. schrieb:
>>> Wieviel Bit sollen die generierten Zahlen haben?
>>
>> 1024.
>
> Sorry, aber das ist grober Unsinn. Das ist eine Dezimalzahl von über 300
> Stellen. Oder meinst du Primzahlen bis 1024? Also 10 Bits?

Nein ich meinte schon 1024 Bit, also eine Dezimalzahl von 309 Stellen.
Es geht um RSA-2048.

von Gustl B. (-gb-)


Lesenswert?

Ok, aber will man das dann wirklich auf einem FPGA machen?

Wieviele Primzahlen gibt es bis 2^1024? Kann man das sinnvoll irgendwo 
speichern?

von highfrequency (Gast)


Lesenswert?

Gustl B. schrieb:
> Ok, aber will man das dann wirklich auf einem FPGA machen?

Ich bin mir noch nicht sicher, würde sowas zum ersten mal machen und 
versuche mir daher gerade ein Bild von der Komplexität zu machen.
Das Projekt wäre privater Natur.
Würde es aber schon gerne in die Tat umsetzen.

Gustl B. schrieb:
> Wieviele Primzahlen gibt es bis 2^1024? Kann man das sinnvoll irgendwo
> speichern?

Gute Frage, das weiß ich leider auch nicht.

von Jemand (Gast)


Lesenswert?

Gustl B. schrieb:
> Ok, aber will man das dann wirklich auf einem FPGA machen?
>
> Wieviele Primzahlen gibt es bis 2^1024? Kann man das sinnvoll irgendwo
> speichern?

Etwa 2,53*10^305, also nein.

von Arc N. (arc)


Lesenswert?

Nils P. schrieb:
> Sobald jemand rausbekommt, wie man Primzahlen vorhersagen kann ist er
> ganz klarer Kandidat für die Field Medallie (Der Nobelpreis für
> Mathematiker).

Wenn diese Person weniger als 40 Jahre auf dem Buckel hat ;)

> Bis dahin bleibt nur der Weg Zufallszahlen zu generieren und so lange
> auf Prime zu prüfen bis man glück hat.
>
> Klingt doof und ineffizient, ist aber so.

Richtig, nur muss man u.U. nicht, wie oben im Thread vorgeschlagen, die 
ineffizienteste Variante nehmen (Probedivision), sondern darf das ruhig 
den Anforderungen angepasst auch schneller testen. Imo guter Einstieg 
(und ein paar kurze Hinweise zur Parallelisierbarkeit) in
https://cs.stackexchange.com/questions/23260/when-is-the-aks-primality-test-actually-faster-than-other-tests
Wer tatsächlich bessere Ansätze hat als in den dort aufgeführten 
Algorithmen verwendet, dürfte sehr wahrscheinlich nicht hier solche 
Fragen stellen ;)

von Gustl B. (-gb-)


Lesenswert?

Ja krass sind das viele Zahlen, habe mir das gerade mal angeguckt und 
zuerst selber zahlen mit Python erzeugt und konnte nicht glauben, dass 
es bis 100.000.000 ca. jede 20. Zahl ist die prim ist. 
http://www.michael-holzapfel.de/themen/primzahlen/pz-anzahl.htm hat mir 
dann weitergeholfen. Ich dachte das nimmt deutlich stärker ab mit Größe 
der Zahlen.

Dann bleibt wirklich nur erzeugen und testen.

Aber gab es nicht mal diese Rainbow-Tables? Da wurde das doch auch 
irgendwie gespeichert? Gingen die nicht bis 2^1024?
Gut, da wurden keine Primzahlen gespeichert ...

: Bearbeitet durch User
von Sven B. (scummos)


Lesenswert?

Ich weiß nicht, warum meine Antwort ignoriert wurde, aber sie ist immer 
noch dieselbe: der Fermat-Primzahltest.

Davon abgesehen lohnt es auch, sich mal elliptische Kurven anzuschauen 
-- dafür braucht man keine großen Primzahlen.

von J. S. (engineer) Benutzerseite


Lesenswert?

Nils P. schrieb:
> Sobald jemand rausbekommt, wie man Primzahlen vorhersagen kann ist er
> ganz klarer Kandidat für die Field Medallie (Der Nobelpreis für
> Mathematiker).

Du hast gelesen, dass ich den Unterschied nicht zwischen einerseits 
"Vorhersagen" und andererseits "Schätzen+Prüfen" - sondern an anderer 
Stelle gemacht habe, nämlich bei entweder "FPGA berechnet in Echtzeit 
Primzahlen" oder "FPGA gibt vorberechnete Primzahlen aus"?

Nochmal: Wie man zu den Primzahlen kommt, ist eine Sache. Die 
entscheidende Aufgabe scheint mir aber hier, das zufällige Erzeugen, 
also gesteuerte Ausgeben derselben und zwar in einem gewissen 
Zeitrahmen, darf man annehmen. So habe ich die Aufgabe gelesen und so 
macht sie für die einschlägigen Anwendungen auch Sinn. Da bleibe ich bei 
"Tabelle offline füllen und mit Zufallsadressen zugreifen".

Jemand schrieb:
>> Wieviele Primzahlen gibt es bis 2^1024? Kann man das sinnvoll irgendwo
>> speichern?
>
> Etwa 2,53*10^305, also nein.

Ich glaube, man müsste genauer fragen, wieviele Zahlen es gibt, die 
genau die geforderten 1024 bit haben. Ich weiß nicht auswändig, wie weit 
die Primzahlen aufgedeckt wurden, aber es sollte rauszufinden sein, ob 
und wieviele diese Forderung erfüllen.

In jedem Fall halte ich es für unzweckmäßig die Aufgabe im FPGA zu 
machen. Die Prüfung auf "Prim" oder "nicht Prim" ist eher eine 
Mathematische und daher etwas für C++ und GPU. Besonders die komplexeren 
Testverfahren sollten damit einfacher zu realisieren sein.

von Jemand (Gast)


Lesenswert?

Jürgen S. schrieb:
> Ich glaube, man müsste genauer fragen, wieviele Zahlen es gibt, die
> genau die geforderten 1024 bit haben. Ich weiß nicht auswändig, wie weit
> die Primzahlen aufgedeckt wurden, aber es sollte rauszufinden sein, ob
> und wieviele diese Forderung erfüllen.

Damit halbierst du in etwa die Anzahl an Primzahlen und sorgst dafür, 
dass der Zustand eines weiteren Bits bedingungslos bekannt ist.

Der informationsgehalt dieser ganzen Primzahlen übersteigt übrigens 
Schätzungen über den Informationsgehalt des gesamten Universums bei 
weitem.

von J. S. (engineer) Benutzerseite


Lesenswert?

Ich verstehe, was Du meinst. Du möchtest auf den Wegfall der unteren 
Hälfte der 1024 Bit hinaus. Ich bin aber nicht sicher, ob damit nur ein 
Bit eingeschränkt wird. Ich denke eher, dass im unteren Bereich 
erheblich mehr Primzahlen stecken. Gefühlte 90%!

Ich kann das so nicht beweisen, aber zwischen 0 und 127 gibt es auch 
erheblich mehr, als zwischen 128 und 255, oder?

Jede unten existierende PZ blendet alle Zahlen ihres Vielfachen weiter 
oben aus. Damit wird die Dichte immer geringer und eine Verdopplung der 
Zahlenmenge bringt schon rein optisch bei Weitem keine Verdopplung der 
Wertemenge mehr. Weiter oben dürfte der Effekt eher noch geringer sein.

Ich stelle mal die Behauptung auf, dass die Dichte sogar zunehmend 
geringer wird, also die Zahl der zusätzlichen PZ mit einer immer 
weiteren Verdopplung des Zahlenbereiches nicht nur geringer, sondern 
stärker geringer wird.

Dieses Verhalten müsste sich anhand der bekannten PZ nachprüfen lassen.

Für die Wertegruppe von a) 0 ... 63  b) 64 ... 127 und c) 128 ... 255 
stimmt es schon mal. Die Abweichung der Anzahl der PZ in den höheren 
Gruppen vom Doppelten (was die Vermutung wäre) wird nach oben größer.

Wahrscheinlich steigt die Zahl der PZ irgendwann mal mit jeder 
Verdopplung nur noch etwas mehr, als linear an.

von Jemand (Gast)


Angehängte Dateien:

Lesenswert?

Jürgen S. schrieb:
> Jede unten existierende PZ blendet alle Zahlen ihres Vielfachen weiter
> oben aus. Damit wird die Dichte immer geringer und eine Verdopplung der
> Zahlenmenge bringt schon rein optisch bei Weitem keine Verdopplung der
> Wertemenge mehr. Weiter oben dürfte der Effekt eher noch geringer sein.

Die Dichte sinkt schon, allerdings fällt das nur im kleinen 
Zahlenbereich wirklich auf. Im großen Zahlenbereich linearisiert sich 
das Wachstum weitgehend.
Im Bild die Näherung der Anzahl von 0 bis 2^256.

von Markus F. (mfro)


Lesenswert?

Walter K. schrieb:
> Markus F. schrieb:
>> Das macht die elektronische Hardware genauso wie die biologische: man
>> versucht die Zahl durch alle kleineren Zahlen zu teilen. Wenn dabei bei
>> jedem Versuch ein Rest bleibt, ist die Zahl eine Primzahl.
>
> Naja ... es fallen schon mal alle Zahlen mit der letzten Ziffer von 0
> und 2 und 4 und 5 und 6 und 8 durch den Filter, somit sind 60% außen vor
>
> Dh es bleiben nur die Zahlen mit der Endziffer 1, 3, 7 und 9 als
> Primzahlkanditaten
>
> Diese Menge reduzieren wir noch um alle die Zahlen deren Quersumme 3
> oder ein Vielfaches von 3 ergibt - und um die deren letzte 2 Ziffern
> eine Quersumme von 3 oder ganzzahliges Vielfaches davon ergeben ...

Widerspricht sich doch nicht. Das ist nichts anderes als ein 
vereinfachter Test auf Teilbarkeit ohne Rest.

von WasWeissIch (Gast)


Lesenswert?

Sven B. schrieb:
> Ich weiß nicht, warum meine Antwort ignoriert wurde, aber sie ist immer
> noch dieselbe: der Fermat-Primzahltest.

Der ist nicht eindeutig für diese Aufgabe. Wieviele Basen willst du 
nehmen und wie häufig akzeptierst du ein false-Positive?


Entweder naiv durch Durchprobieren, oder:
Seit 2002 (Publikation von AKS) wissen wir, dass Prime in P liegt. Ein 
AKS Test ist schnell implementiert. Jedoch könnte das für relativ kleine 
Primzahlen im Zeitaufwand nachteilig gegenüber dem naiven Test sein. je 
größer die Primzahl allerdings, desto besser.

von Walter K. (walter_k488)


Lesenswert?

Markus F. schrieb:
>> Naja ... es fallen schon mal alle Zahlen mit der letzten Ziffer von 0
>> und 2 und 4 und 5 und 6 und 8 durch den Filter, somit sind 60% außen vor
>>
>> Dh es bleiben nur die Zahlen mit der Endziffer 1, 3, 7 und 9 als
>> Primzahlkanditaten
>>
>> Diese Menge reduzieren wir noch um alle die Zahlen deren Quersumme 3
>> oder ein Vielfaches von 3 ergibt - und um die deren letzte 2 Ziffern
>> eine Quersumme von 3 oder ganzzahliges Vielfaches davon ergeben ...
>
> Widerspricht sich doch nicht. Das ist nichts anderes als ein
> vereinfachter Test auf Teilbarkeit ohne Rest.

ja natürlich --- er reduziert schlicht und einfach die Menge der mit 
einem passenden Algorithmus zu testenden Zahlen.

so wie man solchen einem Algorithmus keine geraden Zahlen zum testen 
anbieten wird, wird man natürlich auch keine ungerade Zahl, die z.B. auf 
5 endet durchlaufen lassen ..oder eben eine, die die anderen 
Quersummenregeln erfüllt

von Der Hocko (Gast)


Lesenswert?

WasWeissIch schrieb:
> dass Prime in P liegt.
Was heisst hier "in P"?

von Alexander F. (alexf91)


Lesenswert?

Der Hocko schrieb:
> WasWeissIch schrieb:
>> dass Prime in P liegt.
> Was heisst hier "in P"?

Das Problem "Prime" liegt in der Komplexitätsklasse "P".
Es gibt also einen Algorithmus (den AKS Test), mit dem in polynomieller 
Zeit (abhängig von der Größe des Problems, in diesem Fall log(N)) 
festgestellt werden kann, ob N eine Primzahl ist.

von Sven B. (scummos)


Lesenswert?

WasWeissIch schrieb:
> Sven B. schrieb:
>> Ich weiß nicht, warum meine Antwort ignoriert wurde, aber sie ist immer
>> noch dieselbe: der Fermat-Primzahltest.
>
> Der ist nicht eindeutig für diese Aufgabe. Wieviele Basen willst du
> nehmen und wie häufig akzeptierst du ein false-Positive?
>
>
> Entweder naiv durch Durchprobieren, oder:
> Seit 2002 (Publikation von AKS) wissen wir, dass Prime in P liegt. Ein
> AKS Test ist schnell implementiert. Jedoch könnte das für relativ kleine
> Primzahlen im Zeitaufwand nachteilig gegenüber dem naiven Test sein. je
> größer die Primzahl allerdings, desto besser.

Der TO möchte Primzahlen für RSA haben, wenn ich das richtig verstehe. 
Die haben mindestens 1024 Bit. Die exakten Methoden funktionieren dafür 
quasi "per definitionem" nicht, sonst wäre das Verfahren nicht sicher. 
Primzahlen dieser Größe generiert man mit dem Fermat-Primzahltest.

100% sicher, dass es eine Primzahl ist bist du dann nicht, das ist 
richtig; du kannst die Parameter des Tests aber so wählen, dass die 
Fehler-Wahrscheinlichkeit z.B. < 10^-20 ist. Das ist praktisch gesehen 
dasselbe.

von meister (Gast)


Lesenswert?

>ja natürlich --- er reduziert schlicht und einfach die Menge der mit
>einem passenden Algorithmus zu testenden Zahlen.

ne eben nicht, da er doch die prüfung ob gerade oder ungerade auch beim 
ERZEUGEN machen muss - du gewinnst gar nix...

von Sven B. (scummos)


Lesenswert?

meister schrieb:
>>ja natürlich --- er reduziert schlicht und einfach die Menge der mit
>>einem passenden Algorithmus zu testenden Zahlen.
>
> ne eben nicht, da er doch die prüfung ob gerade oder ungerade auch beim
> ERZEUGEN machen muss - du gewinnst gar nix...

Das ist sowieso alles völlig irrelevant. Wenn du drei viertel der zu 
überprüfenden Zahlen sparst, sind das gerade mal 2 Bit weniger, also 
1022 statt 1024 Bits. Meinst du, das macht irgendeinen Unterschied bei 
Betrachtung der Frage, ob das mit einem bestimmten Algorithmus 
zeittechnisch machbar ist oder nicht? Nein.

von J. S. (engineer) Benutzerseite


Lesenswert?

Jemand schrieb:
> Die Dichte sinkt schon, allerdings fällt das nur im kleinen
> Zahlenbereich wirklich auf. Im großen Zahlenbereich linearisiert sich
> das Wachstum weitgehend.
Stimmt. Da war ich wohl zu pessimistisch.

Ich habe mir mal etwas Literatur dazu angesehen und gefunden, dass man 
PZ schon in den 1950ern im Bereich 1024 Bit gefundenen hat. Siehe die 
Rekordzahlen im Wiki. Damit dürften die gesuchten Werte eigentlich offen 
liegen. Oder kann man unterstellen, dass in dem Bereich noch nicht alle 
gefunden wurden?

von Sven B. (scummos)


Lesenswert?

Jürgen S. schrieb:
> Oder kann man unterstellen, dass in dem Bereich noch nicht alle
> gefunden wurden?
Natürlich nicht. Überleg doch mal, wieviele das wären. Wenn jede 
hunderste Zahl eine Primzahl ist, sind das 2^1017. Wenn jede Zahl ein 
Byte brauchen würde zum Auflisten, würdest du für 2^32 Zahlen 4 GB 
Speicher benötigen. Klingt das realistisch, dass man die "alle gefunden" 
hat?

Dazu wäre ja dann RSA-1024 auch völlig kaputt ...

: Bearbeitet durch User
von Alexander F. (alexf91)


Lesenswert?

Jürgen S. schrieb:
> Oder kann man unterstellen, dass in dem Bereich noch nicht alle
> gefunden wurden?

Die Anzahl der Primzahlen in einem Intervall lässt sich abschätzen:
https://en.wikipedia.org/wiki/Prime-counting_function#Inequalities

Für das Intervall von 2^1023 bis 2^1024 ergibt das 1.5e305 Primzahlen.
Im Vergleich dazu gibt es im gesamten Universum weniger als 10^100 
Elementarteilchen.

von highfrequency (Gast)


Lesenswert?

Sven B. schrieb:
> Der TO möchte Primzahlen für RSA haben, wenn ich das richtig verstehe.
> Die haben mindestens 1024 Bit. Die exakten Methoden funktionieren dafür
> quasi "per definitionem" nicht, sonst wäre das Verfahren nicht sicher.
> Primzahlen dieser Größe generiert man mit dem Fermat-Primzahltest.
>
> 100% sicher, dass es eine Primzahl ist bist du dann nicht, das ist
> richtig; du kannst die Parameter des Tests aber so wählen, dass die
> Fehler-Wahrscheinlichkeit z.B. < 10^-20 ist. Das ist praktisch gesehen
> dasselbe.

Ja das hast du richtig verstanden.
Wäre eine Implementierung des Fermat-Primzahltests deiner Meinung nach 
auf einem FPGA in dieser Größenordnung implementierbar, wenn die 
Generierung der Primzahl unter 60 s dauern sollte?
Es geht mir bei dem Projekt nicht um die bestmögliche Effizienz, es 
sollte einfach funktionieren.

von Sven B. (scummos)


Lesenswert?

Kann ich nicht einschätzen, sorry. Kommt sicherlich auch auf das FPGA 
an. RSA-Keys generieren ist aber traditionell relativ langsam und wie 
schnell du einen findest ist auch ein bisschen Glückssache. Wir haben 
hier so eine 400 MHz ARM-Embedded-CPU, die braucht für einen 4096 
Bit-Key zwischen 20 Sekunden und mehreren Minuten. Das kommt aber auch 
darauf an, wieviel Zufall da ist, glaube ich.

Wenn du irgendwie die Wahl hast, nimm elliptische Kurven. Die Schlüssel 
lassen sich super schnell generieren (du brauchst nur Zufallszahlen, 
keine Zufalls-Primzahlen) und sind bei vergleichbarer Sicherheit dazu 
nur weniger als ein fünftel so groß.

Noch ein Hinweis: "pseudozufällig" ist für diese Anwendung nicht was 
du willst! Zum Schlüssel generieren brauchst du echten Zufall.

: Bearbeitet durch User
von Hagen R. (hagen)


Lesenswert?

Ich stimme Sven zu. Wenn du die Wahl hast nimm Elliptische Kurven in 
GF(2^x) und kryptographische Funktionen die auf dem Logarithmus Problem 
basieren. Das hat gleich mehrer Vorteile gegenüber RSA und Konsorten.

1.) wenn man beim RSA keine 100%'tige Kontrolle über den 
Schlüsselerzeugungsprozess hat dann ist es als unsicher einzustufen. Man 
kann nämlich mit modifizierten Schlüsselerzeugungsprozess einen 
sogennannten verdeckten Kanal einbauen über den der Schlüsselerzeuger 
faqst mit Null Aufwand jeden Schlüssel und die damit verschlüsselten 
nachrichten brechen kann. Das Problem mit solchen Verfahren ist es das 
die gleichen mathematischen Bedingungen die RSA erst sicher machen auch 
für diesen verdeckten Kanal gelten und ihn vor Entdeckung schützen. Mit 
anderen Worten: ich würde niemals einem TrustCenter trauen das für mich 
meine RSA Schlüssel erzeugt hat.

Dieses Problem hat man mit Verfahren die auf den Logarithmusproblem 
basieren grundsätzlich nicht.

2.) Den Zufallsschlüssel/Private Key kann man notfalls auch mit dem 
Würfel händisch ermitteln.

3.) Die benutzten Primzahlen sind öffentlich und können mit Hilfe 
spezieller Verfahren ein mathematisch beweisbares und überprüfbares 
Zertifikat erhalten. Somit sind alle sicherheitsrelevanten Informationen 
dem DL öffentlich verifizierbar.

4.) Die benutzten Primzahlen und Elliptischen Kurven werden einmalig 
offline erzeugt.

5.) die Berechnungsoperationen in der GF(2^x) Domain sind für FPGAs 
ideal umsetzbar und hoch parallelisierbar.

6.) diese Berechnungen kommen meist ohne komplexere Operationen aus, wie 
zb. die nötigen Divisionen/Multiplikation in N.

Gruß hagen

von A. F. (chefdesigner)


Lesenswert?

Sven B. schrieb:
> Klingt das realistisch, dass man die "alle gefunden"
> hat?

So langsam verstehe ich, was der TE möchte: Wie sollen ihm ein System 
konstruieren, womit er dann fehlende Primes finden und Meriten abstauben 
kann :-)

Die höchste derzeit bekannte scheint irgendwas mit 70000 Stellen zu 
sein. Dann behaupte ich mal frech, das (2!111111111 - 1) eine Prime ist. 
Wie prüfe ich es nun nach? Gibt es überhaupt einen Rechner, der das 
kann?

von J. S. (engineer) Benutzerseite


Lesenswert?

Alexander F. schrieb:
> Die Anzahl der Primzahlen in einem Intervall lässt sich abschätzen:
> https://en.wikipedia.org/wiki/Prime-counting_function#Inequalities

Das habe ich inzwischen auch gefunden. Die Frage wäre jetzt, ob es 
Tabellen mit Besetzungsstatistiken gibt, welche angeben, wo man suchen 
könnte und wie groß die Abdeckung ist.

Und wie die Finder zu den neuen, viel größeren PZ gelangen. Dort werden 
offenbar Bereiche übersprungen. Besonders die einschlägigen 
Binärpotenzen-1 scheinen mir Zufallsfunde. Die testen mit immer höheren 
Potenzen, bis sie was haben.

von Sven B. (scummos)


Lesenswert?

Jürgen S. schrieb:
> Alexander F. schrieb:
>> Die Anzahl der Primzahlen in einem Intervall lässt sich abschätzen:
>> https://en.wikipedia.org/wiki/Prime-counting_function#Inequalities
>
> Das habe ich inzwischen auch gefunden. Die Frage wäre jetzt, ob es
> Tabellen mit Besetzungsstatistiken gibt, welche angeben, wo man suchen
> könnte und wie groß die Abdeckung ist.

Deine Vorstellung davon, wieviele Primzahlen es gibt, ist falsch. Es 
gibt unfassbar viele davon und sie sind sehr gleichmäßig verteilt. So 
eine Tabelle macht keinerlei Sinn.

> Und wie die Finder zu den neuen, viel größeren PZ gelangen. Dort werden
> offenbar Bereiche übersprungen. Besonders die einschlägigen
> Binärpotenzen-1 scheinen mir Zufallsfunde. Die testen mit immer höheren
> Potenzen, bis sie was haben.

Ja, natürlich. Die 2^n-1 Primzahlen heißen Mersenne-Primzahlen, und es 
gibt m.W. sogar spezielle Algorithmen, die eine Zahl genau dieser Form 
auf Primalität überprüfen.

von J. S. (engineer) Benutzerseite


Lesenswert?

Sven B. schrieb:
> Deine Vorstellung davon, wieviele Primzahlen es gibt, ist falsch. Es
> gibt unfassbar viele davon und sie sind sehr gleichmäßig verteilt. So
> eine Tabelle macht keinerlei Sinn.

Ich meinte das anders herum: Eine Tabelle, die angibt, welche Zahlen 
schon gefunden wurden. Diese würde in Verbindung mit der Annahme der 
Gleichverteilung ja gerade offenlegen, wo man noch suchen könnte.

von S. R. (svenska)


Lesenswert?

Jürgen S. schrieb:
> Eine Tabelle, die angibt, welche Zahlen
> schon gefunden wurden.

Auch diese Tabelle ist potentiell beliebig groß.

Manche Primzahlen folgen bestimmten Regeln (wie z.B. die 
Mersenne-Primzahlen), aber dazwischen gibt es immer wieder welche, die 
keinen Regeln folgen (oder für die wir zumindest keine Regeln kennen).

Übrigens verwendet man in der Realität für Krypto keine Primzahlen, 
sondern nur Zahlen, die mit sehr hoher Wahrscheinlichkeit prim sind. Der 
exakte Nachweis würde ja eine Primfaktorzerlegung erfordern, die 
nachvollziehbarerweise schwierig sein soll. :-)

von Sven B. (scummos)


Lesenswert?

Jürgen S. schrieb:
> Sven B. schrieb:
>> Deine Vorstellung davon, wieviele Primzahlen es gibt, ist falsch. Es
>> gibt unfassbar viele davon und sie sind sehr gleichmäßig verteilt. So
>> eine Tabelle macht keinerlei Sinn.
>
> Ich meinte das anders herum: Eine Tabelle, die angibt, welche Zahlen
> schon gefunden wurden. Diese würde in Verbindung mit der Annahme der
> Gleichverteilung ja gerade offenlegen, wo man noch suchen könnte.

Das hat dasselbe Problem. Stell dir vor, du willst in der Sahara 
Sandkörnchen finden, die einen bestimmten Farbton haben. Nicht alle 
haben diesen Farbton, aber sagen wir mal 1% davon. Und jetzt überleg 
mal, wie hilfreich bei diesem Unterfangen eine Tabelle wäre, die für 
jeden Kubikzentimeter Sand auflistet, wieviele solche Sandkörnchen du 
schon gefunden hast ...

> Der exakte Nachweis würde ja eine Primfaktorzerlegung erfordern, die
> nachvollziehbarerweise schwierig sein soll. :-)

Das stimmt übrigens nicht: der Nachweis, dass eine Zahl prim ist, ist 
mit anderen Algorithmen und geringerem Aufwand lösbar als die konkrete 
Zerlegung.

: Bearbeitet durch User
von FPGA-Mann (Gast)


Lesenswert?

Scon mal jemandem aufgefallen, dass der "Hochfrequenz" seit wenigstens 
einer Woche nicht mehr mitliest?

Ich werfe diesbezüglich kurz in die Diskussion ein, wie ein FPGA mit 
seinem begrenzten Speicher und Rechenmöglichkeiten diese großen Zahlen 
handhaben soll.

von Duke Scarring (Gast)


Lesenswert?

FPGA-Mann schrieb im Beitrag #5500180:
> Scon mal jemandem aufgefallen, dass der "Hochfrequenz" seit wenigstens
> einer Woche nicht mehr mitliest?
Wie stellt man das fest?
Das er nicht mehr antwortet sieht man, aber wie erkennt man ausbleibende 
Lesezugriffe?
Außerdem ist es auch völlig unerheblich, ob es den TO noch gibt: Solange 
wie im Thread geschrieben wird, ist eine gewisse Resonanz vorhanden...

Duke

von J. S. (engineer) Benutzerseite


Angehängte Dateien:

Lesenswert?

Sven B. schrieb:
> überleg
> mal, wie hilfreich bei diesem Unterfangen eine Tabelle wäre, die für
> jeden Kubikzentimeter Sand auflistet, wieviele solche Sandkörnchen du
> schon gefunden hast ...

Sie wäre dann hilfreich, wenn sie offenbarte, dass es in Region 1,2,3 
und 5 jeweils 10% rote Sandkörner gibt und in Region 4 nur 3%.
Ich würde dann die Region 4 absuchen.

Sagt die Tabelle aber sowas wie 4%,3%,20%, 17%, könnte man unterstellen 
dass 20% so eine Art Limit ist, die Region 4 ziemlich abgegrast ist und 
es sich in den ersten beiden lohnt.

Das ist das klassische Goldsucherproblem. Anhand der Umgebung schätzen 
was lokal zu vermuten ist und plausibilisieren, wie vollständig der 
Wertemenge ist.

Ich möchte doch mal wetten, dass die Tabelle noch nicht konsistent ist, 
also sicher nicht der vermuteten Verlaufsform folgt. Sie wird Lücken 
aufweisen.

Solche Besetzungsstatistiken sehen - egal wie der Verlauf ist - immer 
irgendwie so aus wie im Bild. Selbst in völliger Unkenntnis des 
Prinzipverlaufs (hier sinx +x) sieht man, wo man suchen muss.

von Sven B. (scummos)


Lesenswert?

Jürgen S. schrieb:
> Sven B. schrieb:
>> überleg
>> mal, wie hilfreich bei diesem Unterfangen eine Tabelle wäre, die für
>> jeden Kubikzentimeter Sand auflistet, wieviele solche Sandkörnchen du
>> schon gefunden hast ...
>
> Sie wäre dann hilfreich, wenn sie offenbarte, dass es in Region 1,2,3
> und 5 jeweils 10% rote Sandkörner gibt und in Region 4 nur 3%.
> Ich würde dann die Region 4 absuchen.

Das ist aber schlicht nicht so. Die Sandkörner sind extrem viele und 
extrem gleichmäßig verteilt.

von J. S. (engineer) Benutzerseite


Lesenswert?

Sven B. schrieb:
> Das ist aber schlicht nicht so. Die Sandkörner sind extrem viele und
> extrem gleichmäßig verteilt.

Das Sandkornbeispiel war nicht von mir, bleiben wir mal bei der Frage 
nach den Primzahlen. Gibt es eine Tabelle, die aufzeigt, inwieweit die 
Anzahl der gefundenen Zahlen diejenige erreicht, die durch die 
Abschätzung weiter oben angeführt würde?

Wenn da durchschnittlich nur 1% aufgeführt wären, so wäre das in der Tat 
ohne Information. Aber ist das so?

von Matthias S. (matzes)


Lesenswert?

Walter K. schrieb:
> ...
> Dh es bleiben nur die Zahlen mit der Endziffer 1, 3, 7 und 9 als
> Primzahlkanditaten
>
> Diese Menge reduzieren wir noch um alle die Zahlen deren Quersumme 3
> oder ein Vielfaches von 3 ergibt - und um die deren letzte 2 Ziffern
> eine Quersumme von 3 oder ganzzahliges Vielfaches davon ergeben ...

"deren letzte 2 Ziffern eine Quersumme von 3 oder
 ganzzahliges Vielfaches davon ergeben"?

127?
139?
151?

von Sven B. (scummos)


Lesenswert?

Jürgen S. schrieb:
> Sven B. schrieb:
>> Das ist aber schlicht nicht so. Die Sandkörner sind extrem viele und
>> extrem gleichmäßig verteilt.
>
> Das Sandkornbeispiel war nicht von mir, bleiben wir mal bei der Frage
> nach den Primzahlen. Gibt es eine Tabelle, die aufzeigt, inwieweit die
> Anzahl der gefundenen Zahlen diejenige erreicht, die durch die
> Abschätzung weiter oben angeführt würde?
>
> Wenn da durchschnittlich nur 1% aufgeführt wären, so wäre das in der Tat
> ohne Information. Aber ist das so?

Hm, ich glaube irgendwie ist mein Punkt nicht klar. Ich mache mal ein 
Zahlenbeispiel für die Primzahlen. Wir katalogisieren mal nur 
Primzahlen, die so grob zwischen 2**4095 und 2**4096 liegen, im Bereich 
von RSA 4096-Keys. Jetzt nehmen wir mal an, unsere Tabelle hat 
großzügige 2**64=18446744073709551616 Bereiche, die katalogisiert sind. 
Dazu nehmen wir an, in jedem einzelnen dieser Bereiche würden wir 
soviele Primzahlen kennen, wie wir im kompletten der Menscheit zur 
Verfügung stehenden Speicher abspeichern könnten. Das werden so ganz 
grob 10**18 Stück sein. Von den genannten Primzahlen (unter der Annahme, 
dass jede tausendste Zahl eine Primzahl ist, aber das ist relativ egal) 
haben wir dann sowas wie 10**18 * 2**64 / (2**4096 / 1000) =

tja, ich kann's gar nicht ausrechnen, passt nicht in die 
Floating-Point-Genauigkeit, Moment ...

10**-1189% katalogisiert. Das sind, äh, 
0.0000000000000000000000000000000000000000000000000000000000000000000000 
000000000000000000000000000000000000000000000000000000000000000000000000 
000000000000000000000000000000000000000000000000000000000000000000000000 
000000000000000000000000000000000000000000000000000000000000000000000000 
000000000000000000000000000000000000000000000000000000000000000000000000 
000000000000000000000000000000000000000000000000000000000000000000000000 
000000000000000000000000000000000000000000000000000000000000000000000000 
000000000000000000000000000000000000000000000000000000000000000000000000 
000000000000000000000000000000000000000000000000000000000000000000000000 
000000000000000000000000000000000000000000000000000000000000000000000000 
000000000000000000000000000000000000000000000000000000000000000000000000 
000000000000000000000000000000000000000000000000000000000000000000000000 
000000000000000000000000000000000000000000000000000000000000000000000000 
000000000000000000000000000000000000000000000000000000000000000000000000 
000000000000000000000000000000000000000000000000000000000000000000000000 
000000000000000000000000000000000000000000000000000000000000000000000000 
0000000000000000000000000000000000000001%,  ungefähr.

Für den Prozentsatz in jedem einzelnen Tabellenbereich gilt dasselbe.

: Bearbeitet durch User
von Nepomuk (Gast)


Lesenswert?

oder anders ausgedrückt: Primzahlen der höhren Ränge sind so gut wie gar 
nicht erforscht und bekannt. Man kann praktisch überall welche finden.

Beitrag #5511486 wurde von einem Moderator gelöscht.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.