News

Weltrekord: Forscher zerlegen riesige Zahl in Primfaktoren RSA768 zerlegt

08. Januar 2010: In einer Gemeinschaftsaktion haben internationale Institute einen 768-Bit-Schlüssel geknackt. Schon bald wollen sie den 1024-Bit-Schlüssel auslesen. Experten warnen vor großen Sicherheitslücken.
Die heute gebräuchlichen Schlüssel zur Sicherung etwa von Kreditkartennummern im Internet könnten nach Erkenntnissen von Forschern schon in einigen Jahren unsicher werden. Ein internationales Team unter Bonner Beteiligung hat jetzt einen 768 Bit langen Schlüssel geknackt. Das sei eine Zahl mit 232 Stellen und damit Weltrekord, teilte die Universität Bonn am Freitag mit.
Damit sind die Forscher dem aktuell gängigen Schlüssel von 1024 Bit schon ein Stück näher gekommen. Die Forscher nutzten ein Computernetzwerk. Auf einem herkömmlichen PC hätte das Knacken dieses Schlüssels nach ihren Angaben rund 2.000 Jahre gedauert.
Viele Verfahren zur Verschlüsselung sensibler Daten beruhen darauf, dass es äußerst schwierig ist, große Zahlen in ihre sogenannten Primfaktoren zu zerlegen. Primfaktoren sind diejenigen Primzahlen, die multipliziert die gesuchte Zahl ergeben. So hat etwa die Zahl 21 die Primfaktoren 3 und 7 (3 mal 7 gleich 21). Drei US-Forscher entwickelten 1977 ein Verfahren zur Datenverschlüsselung und nutzten es später auch kommerziell. Ihre nach ihren Initialen "RSA" genannte Technik steckt inzwischen in jedem Internet-Browser. Ein kleines Programm verschlüsselt dort etwa Kreditkartennummern so, dass böswillige Lauscher mit ihnen nichts anfangen können.
Die jetzt geknackte Zahl trägt die nüchterne Bezeichnung RSA-768, das heißt, sie hat 768 Bit. In Dezimalschreibweise entspricht das 232 Stellen. Damit handelt es sich um das größte Zahlenungetüm von allgemeiner Form, das bislang in seine Primfaktoren zerlegt wurde. "Die Zerlegung eines 1024-Bit-Schlüssels wäre um drei Größenordnungen schwieriger als das jetzt abgeschlossene Projekt", sagte Prof. Jens Franke vom Institut für Mathematik der Universität Bonn. Dennoch werde der erste 1024-Bit-Schlüssel vermutlich noch vor Ende des Jahrzehnts geknackt.
(Quelle: dpa)

47. bekannte Mersenne-Primzahl gefunden

12. Juni 2009: Schon am 12. April 2009 wurde die 47. bekannte Mersennesche Primzahl 2 ^42643801 -1 , eine Zahl mit 12837064 Ziffern von Odd Magnar Strindmo aus Melhus, Norwegen entdeckt. Sie ist die zweitgrößte bekannte Primzahl, "nur" 141.125 Stellen kleiner als die größte Mersenne Primzahl, die letzten August gefunden wurde.

Odd ist ein IT-Profi, dessen Computer im GIMPS-Projekt (Great Internet Mersenne Prime Search) seit 1996 schon 1400 Zahlen getestet haben. Die zum Erfolg führende Berechnung dauerte 29 Tage auf einem Intel Core2Duo 3,0 GHz Rechner.

47. bekannte Mersenne-Primzahl (wahrscheinlich) gefunden

10. Juni 2009: Das GIMPS-Projekt (Great Internet Mersenne Prime Search) vermeldet auf seiner Homepage die Entdeckung der 47. Mersenne'schen Primzahl.

Erster gigantischer Primzahldrilling wahrscheinlich gefunden

12. Oktober 2008: Norman Luhn fand ein Primzahldrilling (wahrscheinlich) mit genau 10047 Stellen. Das Primzahlentupel lautet p=2072644824759 * 2³³³³³ -1, p+2,p+6. Mit freundlicher Unterstützung von Francois Morain aus Frankreich, wird für die dritte Zahl p+6 ein Echtheitszertifikat mittels ECPP berechnet, da es sich im Moment nur um ein wahrscheinliche Primzahl handelt. Eine Rekordauflistung aller bisherigen Primzahlentupel findet man auf der englischsprachigen Webseite http://anthony.d.forbes.googlepages.com/ktuplets.htm

45. und 46. bekannte Mersenne-Primzahlen gefunden

16. September 2008: GIMPS-Projekt (Great Internet Mersenne Prime Search) schreibt auf seiner Seite www.mersenne.org folgendes:

Am 23. August entdeckte ein Computer der UCLA [Universität von Kalifornien, Los Angelos] die 45. bekannte Mersenne'sche Primzahl, 2^43.112.609-1, eine Monsterzahl mit 12.978.189 Ziffern! Die Primzahl erfüllt die Bedingungen des Electronic Frontier Foundation $100,000 Preises für die Entdeckung der ersten Primzahl mit mehr als 10 Millionen Ziffern. Glückwunsch an Edson Smith, der für die Installation und Pflege der GIMPS-Software auf den Computern des UCLA Mathematics Department ist.

Am 6. September fand Hans-Michael Elvenich in Langenfeld bei Köln die 46. bekannte Mersenne'sche Primzahl,
2^37.156.667-1, eine Zahl mit 11.185.272 Ziffern. Sei Colquitt und Welsh im Jahre 1988 2^110.503-1 fanden ist dies die erste Mersene'sche Primzahl, die nicht in der 'richtigen Reihenfolge' gefunden wurde.

Die Jagd nach dem EFF Preis kam damit nach einem Jahrzehnt mit einem knappen Einlauf zu Ende - nur zwei Wochen lagen zwischen den Funden der beiden Primzahlen.

Wie versprochen gibt GIMPS $50.000 des EFF Preises an das UCLA Mathematics Department für die Entdeckung der ersten Primzahlen mit 10 Millionen Stellen. $25.000 werden für wohltätige Zwecke bereitgestellt, und der Rest wird hauptsächlich an die Entdecker der vorhergehenden Mersenne'schen Primzahlen gehen.

In Anerkennung der jeweiligen Entdecker, der GIMPS-Leiter und aller Teilnehmer an der GIMPS werden die Entdeckungen "Edson Smith, George Woltman, Scott Kurowski, et al.", und "Hans-Michael Elvenich, George Woltman, Scott Kurowski, et al." zugeschrieben werden.

Edson Smith arbeitet seit 27 Jahren in der Computerindustrie und seit 10 Jahren als Computing Manager für das UCLA Mathematics Department. Im letzten Herbst ersetzte er die Bildschirmschoner des Computersaals mit prime95 - treffend für ein Mathematics Department. UCLA hat eine lange Geschichte in der Entdeckung von Mersenne'schen Primzahlen. Dr. Raphael Robinson hat 1952 fünf Mersenne'sche Primzahlen am UCLA entdeckt, und Alex Hurwitz fand 1961 noch zwei weitere.

Hans-Michael Elvenich ist ein 44jähriger Elektroingenieur bei Lanxess, einem Spezialchemie-Konzern. Er ist Primzahl-Enthusiast und betreibt die Webseite www.primzahlen.de.

Beide Primzahlen wurden zuerst von Tom Duell (Burlington, MA, USA) und Rob Giltrap (Wellington, Neuseeland), beide von Sun Microsystems, unter Benutzung des Mlucas-Programmes von Ernst Mayer (Cupertino California USA) überprüft. Die Überprüfungen liefen auf den 8 dual-core SPARC64 VI 2.15Ghz CPUs des Sun SPARC Enterprise M5000 Server und den 4 quad-core SPARC64 VII 2.52GHz CPUs eines Sun SPARC Enterprise M8000 Server in Menlo Park, CA, USA. Die erste der Überprüfungen dauerte 13 Tage, die zweite fünf Tage.

Beide Primzahlen wurden unabhängig überprüft, und zwar von Tony Reix von Bull SAS in Grenoble, Frankreich mit den 16 1.6 GHz Itanium2 CPUs eines Bull NovaScale 6160 HPC server und des Glucas-Programmes. Jeff Gilchrist von der Carleton University in Ottawa, Kanada hat auch eine Primzahl überprüft und ist fast fertig mit der Überprüfung der zweiten mit den 16 1.6 GHz Itanium2 CPUs eines Server bei SHARCNET. Auch er benutzt das Glucas-Programme von Guillermo Ballester Valor aus Granada, Spanien.

Bei Perfectly Scientific, Dr. Crandall's Firma die den von GIMPS verwandten FFT-Algorithmus entwickelt hat, gibt es auch ein Poster mit allen 12,9 bzw, 11,1 Millionen Ziffern das man bestellen kann. Zum Entziffern braucht man allerdings eine große Lupe!

Originaltext:
On August 23rd, a UCLA computer discovered the 45th known Mersenne prime, 2^43,112,609-1, a mammoth 12,978,189 digit number! The prime number qualifies for the Electronic Frontier Foundation's $100,000 award for discovery of the first 10 million digit prime number. Congratulations to Edson Smith, who was responsible for installing and maintaining the GIMPS software on the UCLA Mathematics Department's computers.

On September 6th, the 46th known Mersenne prime, 2^37,156,667-1, a 11,185,272 digit number was found by Hans-Michael Elvenich in Langenfeld near Cologne, Germany! This was the first Mersenne prime to be discovered out of order since Colquitt and Welsh discovered 2^110,503-1 in 1988.

The nearly decade long quest for the EFF award came down to a close race to the finish - with just two weeks separating the discovery of the two primes.

As promised, GIMPS will give $50,000 of the EFF award to the UCLA Mathematics Department for discovering the first 10 million digit prime. $25,000 will go to charity, and most of the remainder will go to discoverers of the previous six Mersenne primes.

In recognition of the individual discoverers, the GIMPS project leaders, and every GIMPS participant's contributions, credit for the two primes goes to "Edson Smith, George Woltman, Scott Kurowski, et al", and "Hans-Michael Elvenich, George Woltman, Scott Kurowski, et al".

Edson Smith has worked in the IT industry for 27 years and the last 10 years as the Computing Manager for the UCLA Mathematics Department. Last Fall he replaced the Lab's screen savers with prime95 - a perfect fit for the Mathematics Department. UCLA has a rich history in the discovery of Mersenne primes. Dr. Raphael Robinson found five Mersenne primes at UCLA in 1952 and Alex Hurwitz found two more in 1961.

Hans-Michael Elvenich is a 44 year old Electrical Engineer working for Aliseca, a chemical company. He is a prime number enthusuast and is the owner and operator of www.primzahlen.de. In German, prime numbers are called "primzahlen".

Both primes were first verified by Tom Duell (Burlington, MA, USA) and Rob Giltrap (Wellington, New Zealand), both of Sun Microsystems, using the Mlucas program by Ernst Mayer of Cupertino California USA. The verifications ran on 8 dual-core SPARC64 VI 2.15Ghz CPUs of a Sun SPARC Enterprise M5000 Server and 4 quad-core SPARC64 VII 2.52GHz CPUs of a Sun SPARC Enterprise M8000 Server in Menlo Park, CA, USA. The first prime verification took 13 days, the second prime took 5 days.

Both primes were also independently verified by Tony Reix of Bull S.A. in Grenoble, France using 16 1.6 GHz Itanium2 CPUs of a Bull NovaScale 6160 HPC server and the Glucas program. Jeff Gilchrist of Carleton University in Ottawa, Canada has also verified one prime and is nearly finished with verifying the other using up to 16 1.6 GHz Itanium2 CPUs of a server at SHARCNET, running the Glucas program by Guillermo Ballester Valor of Granada, Spain.

Perfectly Scientific, Dr. Crandall's company which developed the FFT algorithm used by GIMPS, will make posters you can order containing all 12.9 and 11.1 million digits. You'll need a good magnifying glass to read the tiny, tiny print!

45. und 46. bekannte Mersenne-Primzahlen gefunden

11. - 14. September 2008: Das GIMPS-Projekt (Great Internet Mersenne Prime Search) bestätigt auf seiner Homepage die Entdeckung der 45. Mersenne'schen Primzahl und der 46. Mersenne'schen Primzahl.

Die beiden Zahlen haben schon erfolgreich die 1. unabhängige Prüfung bestanden. Diese unabhängigen Prüfungen wurden von Tom Duell (Burlington, MA, USA) und Rob Giltrap (Wellington, New Zealand) getätigt.

Wer diese Primzahlen im GIMPS-Netzwerk gefunden hat ist weiterhin unklar. Dies soll Anfang der nächsten Woche erst veröffentlicht werden. Auch über die Größe der Zahlen kann bis dahin nur spekuliert werden.

Später nähere Information hierzu hier aus 1. Hand.

45. und 46. bekannte Mersenne-Primzahlen (wahrscheinlich) gefunden

06. September 2008: Das GIMPS-Projekt (Great Internet Mersenne Prime Search) vermeldet auf seiner Homepage die Entdeckung der 45. Mersenne'schen Primzahl und der 46. Mersenne'schen Primzahl.

45. bekannte Mersenne-Primzahl (wahrscheinlich) gefunden

23. August 2008: Das GIMPS-Projekt (Great Internet Mersenne Prime Search) vermeldet auf seiner Homepage die Entdeckung der 45. Mersenne'schen Primzahl.

Zahlenknacker melden Rekordzerlegung in Primfaktoren

21. Mai 2007: Schon seit Jahren ist es Sport der Mathematiker um Professor Dr. Jens Franke und Dr. Thorsten Kleinjung an der Rheinischen Friedrich-Wilhelm-Universität zu Bonn immer größere Zahlen in Primfaktoren zu zerlegen. Solche großen zusammengesetzten Zahlen, insbesondere die RSA-Zahlen (nach Rivest, Shamir, Adelman) werden für Verschlüsselungsverfahren eingesetzt, und die Firma RSA Laboratories hatte eine Challenge-Liste veröffentlicht, verbunden mit einem – je nach Größe – wachsenden Preisgeld von 10.000 bis 200.000 US-Dollar. Die Bonner waren bei der Rekord-Jagd mehrmals erfolgreich und zerlegten im Dezember 2003 den RSA-576 und im November 2005 RSA-640.
Nun hat sich das japanische Telekommunikationsunternehmen NTT zusammen mit den Bonnern und ihrem Kollegen von der Polytechnischen Hochschule in Lausanne, Arjen Lenstra (übrigens ein Bruder des ebenfalls sehr bekannten Zahlentheoretikers Hendrik Lenstra), an die Aufgabe gemacht, die Mersenne-Zahl 21039–1 genauer zu untersuchen. Die entlarvt sich, wie man spätestens auf den zweiten Blick sieht, als zusammengesetzt, mit 5080711 als einfachem Teiler. Aber über den 307-stelligen Koteiler (siehe unten) wusste man bislang noch nichts. Elf Monate ackerten die Rechner (überwiegend in Japan), bis jetzt eine Zerlegung in zwei 80- und 227-stellige Primzahlen gefunden wurde. Die von Ajren Lenstra und den Bonner Mathematikern entwickelte Methode GNFS (General Number Field Sieve) arbeitete dabei in vier Schritten:


Kandidatensuche (Rechenzeit: 125,7 Opteron-248-Jahre),
Siebberechnung (Rechenzeit 95 Pentium-D-Jahre),
Lineare Algebra (zwei Cluster des NTT mit 146 PCs rechneten zwei Monate)
Wurzelziehen (wenige Stunden auf dem PC-Cluster der Uni Bonn)

Mit 1017 Binärstellen ist der zerlegte Koteiler nahezu genauso groß wie die noch zur Fahndung ausgeschriebene RSA-1024-Zahl. 1024 Bit ist die derzeit übliche Schlüssellänge.

Als Teiler einer Mersenne-Zahl hat der Koteiler jedoch eine bestimmte Struktur, die das Aufspüren weiterer Faktoren vereinfacht. Für zufällige Zahlen, so betont Kleinjung, schafft man es mit ihrer Methode vielleicht, Schlüssel mit 700 Binärstellen in mehreren Monaten zu knacken. Hier steht also als Herausforderung RSA-704 an. Bis man RSA-1024 wirklich knacken kann, wird es nach Kleinjungs Meinung noch viele Jahre dauern.

Allerdings wird es jetzt kein Preisgeld mehr geben, die Auslobung der RSA Laboratories ist inzwischen ausgelaufen. Wer dennoch ein bisschen experimentieren will, hier die von NTT, Kleinjung, Lenstra und Co zerlegte 307-stellige Zahl:


115942057407257306436980714887689464075389979170201772498686835353882248385
996675660800060954080051794720539932612302048744028604353028619141014409345
351233471273967988850226307575280937916602855510550042581077117617761009413
797078797380618700843777718682868088984471282200293520180607475545154137071
1023817


und die Lösung:


5585366661993629126074920465831594496864
6527018488637648010052346319853288374753
×
2075818194644238276457048137035946951629
3970800739520988120838703792729090324679
3823431438841448348825340533447691122230
2815832769652537609141018910524199389933
4109711624358962065972167481161749004803
659735573409253205425523689

(Quelle: www.heise.de)

44. bekannte Mersenne-Primzahl gefunden

12. September 2006: Am 4. September entdecken Dr. Curtis Cooper und Dr. Steven Boone, beide Professoren an der Central Missouri State Universität die 44. bekannte Mersenne Primzahl, 2^32.582.657-1. Damit entdeckte das CMSU Team zum zweiten Mal hintereinander die größte bekannte Primzahl.

Diese Zahl hat 9808358 Dezimalstellen und verpasst damit knapp das Preisgeld von 100000$. Der Electronic Frontier Foundation $100,000 Preis wird erst bei größer 10000000 Dezimalstellen gezahlt.

Lightning strikes twice. On September 4, 2006, in the same room just a few feet away from their last find, Dr. Curtis Cooper and Dr. Steven Boone's CMSU team broke their own world record, discovering the 44th known Mersenne prime, 2^32,582,657-1. The new prime at 9,808,358 digits is 650,000 digits larger than their previous record prime found last December. However, the new prime falls short of the 10 million digits required for GIMPS to claim the Electronic Frontier Foundation $100,000 award.
(Quelle: www.Mersenne.org)

44. bekannte Mersenne-Primzahl (wahrscheinlich) gefunden

4. September 2006: Das GIMPS-Projekt (Great Internet Mersenne Prime Search) vermeldet auf seiner Homepage die Entdeckung der 44. Mersenne'schen Primzahl.

Erst wenn ihre Primalität durch eine unabhängige Berechnung bestätigt ist, wird die Zahl bekannt gegeben. Dies wird meist innerhalb von 10 Tagen geschehen.

Vielleicht ist nun das Preisgeld vergeben für eine Primzahl mit mindestens 10.000.000 Dezimalstellen.

On September 4, 2006, a computer reported finding the 44th known Mersenne prime. Verification will begin shortly, probably taking a week or so to complete. If it is verified, this will be GIMPS' tenth prime!

43. Mersenne-Primzahl gefunden

Am 15. Dezember entdecken Dr. Curtis Cooper und Dr. Steven Boone, beide Professoren an der Central Missouri State Universität die 43. Mersenne Primzahl, 2^30402457-1. Das CMSU Team ist sehr erfolgreich im GIMPS Project. Nun ist es die größte bekannte Primzahl.

Die neue Primzahl hat 9.152052 Ziffern. Damit ist klar, dass der Millennium Award für die erste Primzahl jenseits der 10-Millionen-Ziffern-Schallmauer immer noch nicht vergeben werden wird. Die neue Primzahl ist in nur 5 Tagen von Tony Reix of Bull S.A. in Grenoble, Frankreich überprüft worden. Benutzt wurden dazu 16 Itanium2 1.5 GHz CPUs eines Bull NovaScale 6160 HPC im Bull Grenoble Research Center, mit einem Programm Glucas von Guillermo Ballester Valor Granada, Spanien.

43. Mersenne-Primzahl (wahrscheinlich) gefunden

Ein Teilnehmer der Great Internet Mersenne Prime Search scheint die 43. Mersennesche Primzahl gefunden zu haben. Wie ihre Vorgänger ist die vermutete Primzahl von der Form 2n-1, wobei n selbst notwendigerweise eine Primzahl ist. Bis zum 25. Dezember wird die Primeigenschaft nun überprüft; wie üblich werden anschließend erst die Zahl und weitere Einzelheiten bekannt gegeben.
Quelle: www.heise.de

Bisher ist über die Zahl nur bekannt, dass sie, im Gegensatz zu sonstigen neuen Mersenneprimzahlentdeckungen, kleiner als die zuletzt entdeckte Mersenneprimzahl ist. Damit ist klar, dass der Millennium Award für die erste Primzahl jenseits der 10-Millionen-Ziffern-Schallmauer immer noch nicht vergeben werden wird.

Weltrekord: Forscher zerlegen riesige Zahl in Primfaktoren RSA200 zerlegt

Forscher der Universität Bonn und des Centrum voor Wiskunde en Informatica (CWI) aus den Niederlanden haben mit Rechnerunterstützung durch das Bundesamt für Sicherheit in der Informationstechnik (BSI) einen neuen Weltrekord im Faktorisieren aufgestellt: die Zerlegung der Zahl RSA200. Die Sicherheit bestimmter Verfahren zur elektronischen Signatur beruht auf der Schwierigkeit, sehr große Zahlen in ihre Primfaktoren zu zerlegen. Das trifft insbesondere auf den weit verbreiteten RSA-Signaturalgorithmus zu, der 1977 von Ron Rivest, Adi Shamir und Len Adleman am Massachusetts Institute of Technology (MIT) entwickelt wurde. Das BSI untersucht kontinuierlich, welche Signaturverfahren den Vorgaben des deutschen Signaturgesetzes genügen, und dafür ist auch eine Abschätzung des Aufwandes für solche Primfaktorzerlegungen erforderlich. Die Zahl RSA200 hat 200 Dezimalstellen und ist das Produkt zweier Primzahlen. Sie wurde von der amerikanischen Firma RSA Security unter Geheimhaltung der Faktoren veröffentlicht, die Herausforderung bestand darin, diese beiden Zahlen zu finden. Am jetzt aufgestellten Weltrekord waren Professor Dr. Jens Franke, Dr. Thorsten Kleinjung und Friedrich Bahr von der Universität Bonn, Peter Montgomery und Herman te Riele vom CWI aus Amsterdam sowie das BSI beteiligt.

42. Mersenne-Primzahl gefunden

Freitag 18.Februar 2005
Dr. Martin Nowak, ein Augenarzt aus Michelfeld, hat 2^25.964.951- 1 mit dem GIMPS-Mersenne-Programm auf einem seiner Praxiscomputer als prim nachgewiesen. Die Zahl besitzt 7.816.230 Dezimalziffern. Insgesamt 24 PCs arbeiten im Augenzentrum des Arztes in ihrer "Freizeit" für das Internet-Projekt GIMPS. Ein 16-fach-Itanium-2-System (Bull NovaScale 5000 HPC) brauchte nur fünf Tage, um die Primalität der nunmehr 42. bekannten Mersenne-Primzahl zu bestätigen.
(as/c't)

41. Mersenne-Primzahl gefunden

Mittwoch 2.Juni 2004
Die Entdeckung einer neuen Rekord-Primzahl vermeldet ein internationales Computerprojekt zur Primzahlsuche. Die Zahl besitzt 7235733 Stellen und lässt sich als 2 ^24.036.583 - 1 schreiben.

Der Privatrechner eines amerikanischen IT-Beraters brauchte zwei Wochen, um die besonderen Eigenschaften des Zahlenriesen zu enthüllen.

41. Mersenne-Primzahl (wahrscheinlich) gefunden

Samstag 15. Mai 2004:
(http://www.mersenne.org) Am 15. Mai hat wieder ein teilnehmender Rechner der Great Internet Mersenne Prime Search (GIMPS) Erfolg signalisiert. Nach ersten Prüfungen sieht es ganz danach aus, dass tatsächlich eine neue Mersennesche Primzahl gefunden wurde.

Diese bislang 41. Mersenne-Primzahl ist aber möglicherweise kleiner als die größte derzeit bekannte Mersenne-Primzahl 2^20.996.011-1 mit über sechs Millionen Dezimalziffern. Noch waren nämlich nicht alle Exponenten kleiner als 20.996.011 überprüft. Projektleiter George Woltman gab die neue Zahl noch nicht offiziell bekannt, sondern er wartet erst einmal den Validierungslauf auf einem anderen Rechner ab, kodiert mit anderer Software. Angesichts der Größe der Zahl kann das noch ein paar Wochen dauern.

40. Mersenne-Primzahl entdeckt

Dienstag 2. Dezember 2003:
Nun ist es quasi amtlich, die 40. bekannte Mersenne-Primzahl und damit die größte derzeit bekannte Primzahl überhaupt ist 2^20.996.011-1, eine Zahl mit 6.320.430 Dezimalstellen. Unabhängige Verifikationsläufe von George Woltman und Guillermo Valor konnten das von einem Teilnehmer des GIMPS-Projektes (Great Internet Mersenne Prime Search) vor etwa zwei Wochen gefundene Ergebnis auf anderen Rechnerarchitekturen mit anderen Algorithmen verifizieren, so dass die Primalität nun als gesichert gelten kann. Entdeckt wurde die neue Mersenne-Primzahl von dem Pentium-4-Rechner des Chemiestudenten Michael Shafer aus Michigan.
Ob die Zahl allerdings auch wirklich M₄₀ ist und nicht M₄₁ oder M₄₂ ist noch unklar, denn nicht über alle Exponenten unterhalb von 20996011 gibt es schon Erkenntnisse über die Primalität der zugehörenden Mersennezahl 2n-1. Mit dem Erfolg baut die GIMPS den Vorsprung des Mersenne-Lagers vor der konkurrierende Fermat-Gemeinde GFPS, weiter aus, die zwar bei weitem die meisten Zahlen in der Top100-Liste der Primzahlen aufweisen kann, die aber mit der am 23. September 2003 gefundenen generalisierten Fermat-Zahl 1372930^{2^17}+1 mit "nur" 804,474 Dezimalstellen derzeit nur den sechsten Platz hinter fünf führenden Mersenne-Primzahlen einnimmt. Diese wurden allesamt von GIMPS entdeckt, deren circa 60.000 Teilnehmer ein Rechennetz (primenet) mit etwa 9,5 Billionen Gleitkommaoperationen pro Sekunde (9,5 TeraFlops) ermöglichen, das etwa Platz 4 der Supercomputer-Top500-Liste entspräche.
Für das von der Electronic Frontier Foundation ausgelobte Preisgeld ist die gefundene Mersenne-Primzahl trotz ihrer rund 6 Millionen Ziffern aber noch zu klein, sie muss schon als erste mehr als 10 Millionen Ziffern aufweisen können, damit die Entdecker 100.000 Dollar einheimsen können.

Es war nicht die 40. Mersenne-Primzahl

Montag 16. Juni 2003:
(www.mersenne.org/prime.htm) 40th Mersenne prime not found On June 1st a possible Mersenne prime was reported to the server. Unfortunately, two independent verification runs proved the number was composite. This was the first false positive report in 7 years. We are studying ways to reduce the chance that cpu or memory errors can cause a false positive report.

Die Anfang Juni vom PrimeNet-Server der Great International Mersenne Prime Search (GIMPS) entdeckte 40. Mersenne-Primzahl war keine, hat sich jetzt herausgestellt. Am 1. Juni hatte das Projekt die Tatsache der Entdeckung zunächst unter Vorbehalt und ohne Nennung der Zahl gemeldet. Wie sich durch zwei unabhängige Prüfungen herausgestellt hat, war das die erste falsche Positivmeldung in sieben Jahren. Das Projekt prüft nun, wie man in Zukunft durch Prozessor- oder Speicherfehler verursachte Fehlentdeckungen vermeiden kann.

Neuer Algorithmus gefunden

Montag 12. August 2002:
(www.ntvcnn.de) Indische Forscher haben (wollen) nach eigenen Angaben ein 2.200 Jahre altes mathematisches Rätsel gelöst (haben): Die Computerwissenschaftler entwickelten eine Methode zur Bestimmung von Primzahlen.
Ihr neuer Algorithmus könne erstmals fehlerfrei berechnen, ob es sich bei einer Zahl um eine Primzahl handele, erklärten die Manindra Agrawal, Neeraj Kayal und Nitin Saxena vom Indischen Institut für Technologie in Kanpur.
http://www.cse.iitk.ac.in/news/primality.html
9 seitige Erklärung (engl.) PDF-Datei Primality.pdf

Uni Bonn: Primzahlenrekord mit Linux-Rechnern

Montag 4. Februar 2002:
(tecChannel.de) Mathematikern der Universität Bonn ist es nach eigenen Angaben gelungen, eine Zahl mit 158 Stellen in ihre Primfaktoren zu zerlegen, das sei neuer Weltrekord. Bei dem Versuch kamen keine Supercomputer, sondern handelsübliche Rechner mit Linux zum Einsatz.
Der bisherige Rekord stammt aus dem Jahr 1999. Damals gelang es einem internationalen Wissenschaftler-Team eine 155-stellige Zahl zu zerlegen. Das sei auch praktisch eine relevante Schranke gewesen, teilten die Bonner-Mathematiker mit: Damalige Verschlüsselungen basierten meist auf 512-stelligen Binärzahlen; 512 Binärstellen entsprechen aber 155 Stellen im Dezimalsystem.
Zahlreiche Verschlüsselungsverfahren beruhen auf einer mathematischen Asymmetrie: Die Multiplikation von zwei Zahlen benötigt kaum Rechenzeit. Die Zerlegung einer Zahl in ihre Teiler ist um viele Größenordnungen aufwendiger. Die heute eingesetzten Codierungsverfahren verwenden in der Regel Schlüssel mit über 512 Bit. "Sie sind durch unseren Rekord nicht gefährdet", erklärt Professor Dr. Jens Franke vom Institut für Mathematik an der Universität Bonn , der zusammen mit Dr. Thorsten Kleinjung und Friedrich Bahr die 158-Stellen geknackt hat.
Um große Zahlen in Primfaktoren zu zerlegen, werden in der Regel Supercomputer eingesetzt. "Unser Rekord ist der erste dieser Art, bei dem ein Netzwerk handelsüblicher Linux-Rechner zum Einsatz kam", so Professor Franke. Jeder Einzelcomputer arbeitete dabei parallel an der Lösung eines Teilaspektes.
"Solche parallelisierten Programme sind selbst für sehr viel größere Projekte einsetzbar", erklärt der Mathematiker. Gerade in der Endphase müssen die einzelnen Rechner ihre Ergebnisse extrem schnell miteinander abgleichen und neue Teilaufgaben verteilen. Zur Lösung dieser Aufgabe hatten die Mathematiker auf das Know-how der Bonner Abteilung für wissenschaftliches Rechnen und numerische Simulation zurückgegriffen.
Zusätzliche Informationen finden Sie in den Kryptographie-Grundlagen . (uba)

20-Jähriger entdeckt größte bekannte Primzahl

Ein Mathematik-Enthusiast aus Kanada hat mit Hilfe eines weltumspannenden Computernetzwerks die größte bekannte Primzahl gefunden: Die Zahl 2^13.466.917- 1 hat 4.053.946 Stellen und ist wie alle Primzahlen nur durch 1 und sich selber teilbar. Der Entdecker ist der 20-jährige Michael Cameron, der mit seinem Computer am so genannten GIMPS-Projekt teilnimmt, meldet das amerikanische Wissenschaftsmagazin "Science" in seiner Online-Ausgabe. Dieses Netzwerk von Freiwilligen aus aller Welt nutzt die Rechenkapazität von Computern, an denen gerade nicht gearbeitet wird, für die Suche nach immer größeren Primzahlen. Ähnliche Projekte gibt es auch für die Suche nach außerirdischem Leben oder neuen Medikamenten gegen Aids.
Die neue Superprimzahl löst den mit zwei Millionen Stellen wesentlich kleineren bisherigen Rekordhalter ab, den GIMPS-Teilnehmer vor zweieinhalb Jahren ausfindig gemacht hatten. Ein Supercomputer soll den Fund diese Woche noch bestätigen. Auch wenn der Nutzen selbst für Zahlentheoretiker gering ist, soll die Suche nach noch größeren Primzahlen weitergehen.

zurück