Suche zwei 100 stellige Primzahlen
M.Braun
für ein Informatik Projekt suche ich 2 100stellige Primzahlen !
Mit diversen Programmen habe ich es auf Grund meiner geringen Rechnerleitung
nicht geschafft entsprechende zu generieren. Daher hoffe ich, dass es evtl.
jemand gibt der eine Internetseite oder sonstige Quellen kennt wo ein paar
sehr große Primzahlen aufgelistet sind.
Danke für Eure Hilfe
Gruß
Martin
Andreas Krennmair
> für ein Informatik Projekt suche ich 2 100stellige Primzahlen !
RSA?
> nicht geschafft entsprechende zu generieren. Daher hoffe ich, dass es evtl.
> jemand gibt der eine Internetseite oder sonstige Quellen kennt wo ein paar
> sehr große Primzahlen aufgelistet sind.
Use Google: http://www.utm.edu/research/primes/largest.html
hth, ak
--
Eat flaming death, minicomputer mongrels!
Thomas Holenstein
> Hallo,
>
> für ein Informatik Projekt suche ich 2 100stellige Primzahlen !
10^100 + 267 und 10^100 + 949.
Thomas
M.Braun
Danke
"Thomas Holenstein" <Mar-2...@hex.ch> schrieb im Newsbeitrag
news:8lzd6ka...@hex.ch...
Arne Binder
> * M.Braun <m.b...@web4tune.net> [de.sci.mathematik]:
> > für ein Informatik Projekt suche ich 2 100stellige Primzahlen !
>
> RSA?
RSA verwendet Zufallszahlen, die laut einem probabilistischen Test zu
nur 99,9...% Primzahlen sind. Tatsächliche Primzahlen zu generieren,
würde viel zu lange dauern und für praktische Anwendungen sind solche
"Wahrscheinlich-Primzahlen" ausreichend.
Arne
Jan Bruns
Arne Binder:
> "Andreas Krennmair":
> > * M.Braun <m.b...@web4tune.net> [de.sci.mathematik]:
> > > für ein Informatik Projekt suche ich 2 100stellige Primzahlen !
> > RSA?
>
> RSA verwendet Zufallszahlen,
> die laut einem probabilistischen Test zu nur 99,9...% Primzahlen sind.
Die Einschränkung ist unrichtig.
> Tatsächliche Primzahlen zu generieren,
> würde viel zu lange dauern und für praktische Anwendungen sind solche
> "Wahrscheinlich-Primzahlen" ausreichend.
Soweit ich weiß, existieren sehr schnelle Methoden, echte Primzahlen
der geforderten Länge zu generieren. Diese sind, soweit ich mich erinnere,
sogar teilw. schneller, als ein anständiger Primtest.
(für Fragen dazu existiert auch sci.crypt)
Gruss
Jan Bruns
Bernhard Helmes
> > Tatsächliche Primzahlen zu generieren,
> > würde viel zu lange dauern und für praktische Anwendungen sind solche
> > "Wahrscheinlich-Primzahlen" ausreichend.
>
> Soweit ich weiß, existieren sehr schnelle Methoden, echte Primzahlen
> der geforderten Länge zu generieren. Diese sind, soweit ich mich erinnere,
> sogar teilw. schneller, als ein anständiger Primtest.
> (für Fragen dazu existiert auch sci.crypt)
Solange es nur um 100 stellige Primzahlen geht, lassen die sich mit
guten Primzahltests gut überprüfen. Auf meinen Computer (Amd 1000)
kann ich 1000 stellige Primzahlen innerhalb einiger Minuten überprüfen
und finden.
Ein möglicher einfacher Primzahltest ist folgender:
Sei p=x^2+1, dann ist ein hinreichendes Kriterium:
a^(p-1)=1 mod p und a^x=/=1 mod p
Viel Spaß bei der Primzahlsuche
Gruß
Bernhard
Jan Bruns
Bernhard Helmes:
> Ein möglicher einfacher Primzahltest ist folgender:
> Sei p=x^2+1, dann ist ein hinreichendes Kriterium:
> a^(p-1)=1 mod p und a^x=/=1 mod p
Was bedeutet die letzte Bedingung?
Gruss
Jan
Arne Binder
>
> Arne Binder:
> > "Andreas Krennmair":
> > > * M.Braun <m.b...@web4tune.net> [de.sci.mathematik]:
> > > > für ein Informatik Projekt suche ich 2 100stellige Primzahlen !
>
> > > RSA?
> >
> > RSA verwendet Zufallszahlen,
> > die laut einem probabilistischen Test zu nur 99,9...% Primzahlen sind.
>
> Die Einschränkung ist unrichtig.
Der Primzahltest (Miller-Rabin-Test) hat eine Wahrscheinlichkeit von 25%,
dass er eine Zahl fälschlicherweise als Primzahl erkennt. In der Praxis
kann man diesen Test 100x ausführen und erhält so eine Fehlerquote von
6,223E-59%. Denk dir eben noch einige 9er bei meinen 99,9...% dazu.
Wieso also unrichtig?
> > Tatsächliche Primzahlen zu generieren,
> > würde viel zu lange dauern und für praktische Anwendungen sind solche
> > "Wahrscheinlich-Primzahlen" ausreichend.
>
> Soweit ich weiß, existieren sehr schnelle Methoden, echte Primzahlen
> der geforderten Länge zu generieren. Diese sind, soweit ich mich erinnere,
> sogar teilw. schneller, als ein anständiger Primtest.
> (für Fragen dazu existiert auch sci.crypt)
Nach meinem Erkenntnisstand (einschlägige Seiten und Informatik-Vorlesung)
wird bei RSA der Rabin-Miller-Test auf Zufallszahlen angewandt, um Primzahlen
zu finden.
Es kann natürlich sein, dass es mitlerweile bessere Wege gibt und diese auch
heute in den RSA-Algorithmen implementiert sind.
Arne
Rudolf Polzer
> "Jan Bruns" <po...@janbruns.de> schrieb im Newsbeitrag news:b66ke4$qhj$02$1...@news.t-online.com...
> > Arne Binder:
> > > "Andreas Krennmair":
> > > > * M.Braun <m.b...@web4tune.net> [de.sci.mathematik]:
> > > > > für ein Informatik Projekt suche ich 2 100stellige Primzahlen !
> >
> > > > RSA?
> > >
> > > RSA verwendet Zufallszahlen,
> > > die laut einem probabilistischen Test zu nur 99,9...% Primzahlen sind.
> >
> > Die Einschränkung ist unrichtig.
>
> Der Primzahltest (Miller-Rabin-Test) hat eine Wahrscheinlichkeit von 25%,
> dass er eine Zahl fälschlicherweise als Primzahl erkennt. In der Praxis
> kann man diesen Test 100x ausführen und erhält so eine Fehlerquote von
> 6,223E-59%. Denk dir eben noch einige 9er bei meinen 99,9...% dazu.
>
> Wieso also unrichtig?
Weil RSA den Miller-Rabin-Test nicht vorschreibt.
Vor einiger Zeit flog hier ein Paper rum, in dem ein polynomieller
(und sicherer) Primzahltest beschrieben war. Könntest dir ja mal den
anschauen.
--
[mpg123d] Just playing: .../ayumi hamasaki/a best/01 a song for xx.mp3
Meine persönliche Präferenzliste ist qmail, postfix, Cholera,
exim, Pest, Schweinepest, Lepra, Tod, sendmail.
[Robin S. Socha in de.comp.os.unix.linux.misc]
Bernhard Helmes
Ich kann dir zwei mögliche Erklärungen geben:
1. Wenn a^x=/=1 mod p und a^(x^2)=1 mod p dann muß die Ordnung der
Zahl p maximal sein und damit muß p prim sein.
Entweder untersucht man für alle Teiler von p-1 bzw. x^2 ob a^teiler
=/= 1 mod p ist oder einfacher ob a^x =/= 1 ist. Wenn a^teiler = 1
wäre, müßte a^x = 1 sein, da der Teiler x teilt.
2. Wenn a^x =/= 1 und a^p-1 = 1 ist, dann existiert eine nichttriviale
x-te Wurzel von p. Dann müßten aber alle möglichen Teiler von p bzw.
von x^2+1 durch x teilbar sein, was aber nicht möglich ist
Ich hoffe, daß dir das weiter hilft,
Gruß
Bernhard
Helmut Richter
> Weil RSA den Miller-Rabin-Test nicht vorschreibt.
>
> Vor einiger Zeit flog hier ein Paper rum, in dem ein polynomieller
> (und sicherer) Primzahltest beschrieben war. Könntest dir ja mal den
> anschauen.
Wenn man die Primzahlen selber machen darf, wie z.B. für RSA, dann
kann man sie auch so bauen, dass sie schon mit einem Aufwand ähnlich
Rabin-Miller als sicher prim bewiesen werden können. Die Idee ist,
dass man von einer Zahl M ausgeht, deren Faktorisierung man kennt,
sich überlegt, für welche k die Zahl 2kM+1 sicher nicht prim sein
kann, und für die restlichen Rabin-Miller laufen lässt, bis man eine
wahrscheinliche Primzahl p gefunden hat. Da für die dann die
Faktorisierung von p-1 bekannt ist, lässt sich die Sache nachträglich
wasserdicht machen.
In der Praxis macht man das zweimal: einmal um ein *primes* M zu
finden und ein zweites Mal, um daraus das p zu generieren.
Primfaktoren p, bei denen einer der Primteiler von p-1 groß ist,
lassen sich nämlich mit manchen Verfahren schlechter aus einem Produkt
herausfischen als andere.
Der Vorschlag aus einem anderen Beitrag, zwei aufeinanderfolgende
Primzahlen zu nehmen, wäre natürlich für RSA kontraproduktiv: das
Produkt zweier aufeinanderfolgender Primzahlen zerfällt ja beim
Hingucken schon in seine Faktoren.
Helmut Richter
Peter Luschny
> das
> Produkt zweier aufeinanderfolgender Primzahlen zerfällt ja beim
> Hingucken schon in seine Faktoren.
2866866364517254166677846561613
SCNR
Gruss Peter
Detlef Mueller
Mathematica sagt:
Timing[FactorInteger[2866866364517254166677846561613]]
{0.06 Second, {{1693182318746371, 1}, {1693182318747503, 1}}}
Helmut Richter
wrote:
Wurzel draus ziehen, auf ganze Zahl aufrunden: 1693182318746937
Von deren Quadrat die zu zerlegende Zahl abziehen: 320356
Daraus die Wurzel: 566
Es ist also:
2866866364517254166677846561613 =
= 1693182318746937² - 566² =
= (1693182318746937 - 566) · (1693182318746937 + 566) =
= 1693182318746371 · 1693182318747503
Das war auf jeden Fall viel weniger Arbeit als es sonst die Zerlegung
einer 31-stelligen Zahl in Primfaktoren ist.
Helmut Richter
Peter Luschny
> > 2866866364517254166677846561613
So ist es. Deshalb haben 'Primzahlknacker' mit
mehrstufiger Strategie immer auch ein Unterprogramm,
das in der Nähe der Wurzel sucht, meist bald nachdem
man sich der kleinen Primfaktoren entledigt hat. Eine
der dabei verwendeten Methoden ist dabei schon sehr alt:
Sie stammt von Pierre de Fermat aus dem Jahr 1643 und
ist deiner nicht unähnlich ;-))
1693182318746371 ist übrigens die kleinste Primzahl,
hinter der sich eine 'Kilo-Gap' auftut. Das kleine
Fragezeichen, das ich dem 'Hingucken' ankleben wollte,
bezieht sich darauf: Wenn man ein 'Mega-Gap' oder
eine 'Giga-Gap' nimmt, ist es dann auch noch durch
'Hingucken' zu sehen? Natürlich durch eine Rechung
wie der vorgeführten.
Bei den 'Gaps', das heißt den primzahlfreien Intervallen,
hat sich in letzter Zeit kräftig was getan. Hier ist
eine kleine Liste:
http://research.microsoft.com/~pleyland/primes/gaps20.htm
Gruss Peter
Jan Bruns
Bernhard Helmes:
> Ich hoffe, daß dir das weiter hilft,
Noch nicht. Vielleicht, wen Du noch schreibst,
was der =/= bedeuten soll. Eine Ganzzahldivision?
Gruss
Jan
Bernhard Helmes
> > Was bedeutet die letzte Bedingung?
> 2. Wenn a^x =/= 1 und a^p-1 = 1 ist, dann existiert eine nichttriviale
> x-te Wurzel von p. Dann müßten aber alle möglichen Teiler von p bzw.
> von x^2+1 durch x teilbar sein, was aber nicht möglich ist
Hoppla, da ist mir ein Fehler unterlaufen:
Wenn eine nichttriviale x-te Wurzel von p existiert und x Teiler von
p-1, dann haben alle mögliche Teiler von p die Form k*x+1 (k aus N).
Dieser Satz, den ich im übrigen sehr schön finde :-), ist sicherlich
bekannt. Ich weiß aber nicht unter welchen Namen er zuerst
veröffentlicht wurde.
Im oberen Beispiel müßte also x^2+1 durch einen Teiler der Form k*x+1
teilbar sein, was aber sicherlich nicht funktionniert, da die Wurzel
von x^2+1 < k*x+1 ist.
Paul Ebermann
Das soll einfach ein Ungleichheitszeichen (bzw.
nicht-Äquivalentheits-Zeichen) sein, denke ich.
Paul