PrimeGrid

PrimeGrid

Ziel:	Suche nach (großen) Primzahlen
Kategorie:	Mathematik
Homepage:	http://www.primegrid.com/
Status:	produktiv
Projektadressen
Serverstatus:	PrimeGrid
Forum:	PrimeGrid Forum
SETI.Germany
Team-Statistik:	PrimeGrid
Teambeitritt:	SETI.Germany beitreten
Forenthread:	SETI.Germany Forum
Workunits
321 Prime Search LLR (321)
Frist:	6 Tage
Erster Download:	35 MB
Download:	< 1 kB
Upload:	< 1 kB
Arbeitsspeicher:	40 MB
Betriebssysteme:
Bildschirmschoner:
Checkpoints:
Befehlssatzerweiterungen wie FMA3, AVX und SSE werden automatisch verwendet, sofern von CPU und Betriebssystem unterstützt. 10% Credit-Bonus aufgrund der WU-Laufzeit.
321 Prime Search Sieve (321-Sieve) [angehalten]
Frist:	7 Tage
Erster Download:	10 MB
Download:	< 1 kB
Upload:	< 1 kB
Arbeitsspeicher:	110 MB
Betriebssysteme:
Bildschirmschoner:
Checkpoints:
Derzeit nicht verfügbar, da optimale Siebtiefe für den aktuellen Suchbereich erreicht.
Arithmetic Progression of Primes 27 (AP27)
Frist:	7 Tage (Bis zu 30 Tage)
Betriebssysteme:
Grafikkarten
Bildschirmschoner:
Checkpoints:
Anwengung benötigt mindestens 1,5GB VRAM
Cullen Prime Search LLR (CUL)
Frist:	14 Tage
Erster Download:	35 MB
Download:	< 1 kB
Upload:	< 1 kB
Arbeitsspeicher:	35 MB
Betriebssysteme:
Bildschirmschoner:
Checkpoints:
Befehlssatzerweiterungen wie FMA3, AVX und SSE werden automatisch verwendet, sofern von CPU und Betriebssystem unterstützt. 20% Credit-Bonus aufgrund der WU-Laufzeit.
Cullen/Woodall Prime Search Sieve (CW-Sieve) [angehalten]
Frist:	7 Tage
Erster Download:	15 MB
Download:	< 1 kB
Upload:	< 1 kB
Arbeitsspeicher:	25 MB
Grafikkarten
Bildschirmschoner:
Checkpoints:
Derzeit nicht verfügbar, da optimale Siebtiefe für den aktuellen Suchbereich erreicht.
Extended Sierpinski Problem LLR (ESP)
Frist:	6 Tage
Erster Download:	35 MB
Download:	< 1 kB
Upload:	< 1 kB
Arbeitsspeicher:	35 MB
Betriebssysteme:
Bildschirmschoner:
Checkpoints:
Befehlssatzerweiterungen wie FMA3, AVX und SSE werden automatisch verwendet, sofern von CPU und Betriebssystem unterstützt. 10% Credit-Bonus aufgrund der WU-Laufzeit, weitere 10% Credit-Bonus, da das Subprojekt zum Beweis einer konkreten Vermutung dient.
Generalized Cullen/Woodall Prime Search LLR (GCW)
Frist:	4 Tage (bis zu 30 Tagen)
Betriebssysteme:
Bildschirmschoner:
Checkpoints:
Befehlssatzerweiterungen wie FMA3, AVX und SSE werden automatisch verwendet, sofern von CPU und Betriebssystem unterstützt.
Generalized Cullen/Woodall Sieve (GCW-Sieve)
Frist:	4 Tage (Bis zu 30 Tagen)
Betriebssysteme:
Bildschirmschoner:
Checkpoints:
Generalized Fermat Prime Search n=20 (GFN-Short)
Frist:	19 Tage
Betriebssysteme:
Grafikkarten
Bildschirmschoner:
Checkpoints:
Befehlssatzerweiterungen wie FMA3, AVX und SSE werden von der CPU-Anwendung automatisch verwendet, sofern von CPU und Betriebssystem unterstützt. OpenCL-Anwendung für NVIDIA-Grafikkarten belegt einen CPU-Kern.
Generalized Fermat Prime Search World Record n=22 (GFN-WR)
Frist:	21 Tage
Betriebssysteme:
Grafikkarten
Bildschirmschoner:
Checkpoints:
Nur für GPUs verfügbar! OpenCL-Anwendung für NVIDIA-Grafikkarten belegt einen CPU-Kern, ist jedoch im Allgemeinen schneller als die ebenfalls verfügbare CUDA-Anwendung.
Prime Sierpinski Problem LLR (PSP)
Frist:	21 Tage
Erster Download:	35 MB
Download:	< 1 kB
Upload:	< 1 kB
Arbeitsspeicher:	85 MB
Betriebssysteme:
Bildschirmschoner:
Checkpoints:
Befehlssatzerweiterungen wie FMA3, AVX und SSE werden automatisch verwendet, sofern von CPU und Betriebssystem unterstützt. 35% Credit-Bonus aufgrund der WU-Laufzeit, weitere 10% Credit-Bonus, da das Subprojekt zum Beweis einer konkreten Vermutung dient.
Proth Mega Prime Search LLR (MEGA)
Frist:	4 Tage
Erster Download:	35 MB
Download:	< 1 kB
Upload:	< 1 kB
Arbeitsspeicher:	13 MB
Betriebssysteme:
Bildschirmschoner:
Checkpoints:
Befehlssatzerweiterungen wie FMA3, AVX und SSE werden automatisch verwendet, sofern von CPU und Betriebssystem unterstützt.
Proth Prime Search Extended LLR (PPSE)
Frist:	4 Tage
Erster Download:	35 MB
Download:	< 1 kB
Upload:	< 1 kB
Arbeitsspeicher:	7 MB
Betriebssysteme:
Bildschirmschoner:
Checkpoints:
Befehlssatzerweiterungen wie FMA3, AVX und SSE werden automatisch verwendet, sofern von CPU und Betriebssystem unterstützt.
Proth Prime Search LLR (PPS)
Frist:	4 Tage
Erster Download:	35 MB
Download:	< 1 kB
Upload:	< 1 kB
Arbeitsspeicher:	10 MB
Betriebssysteme:
Bildschirmschoner:
Checkpoints:
Befehlssatzerweiterungen wie FMA3, AVX und SSE werden automatisch verwendet, sofern von CPU und Betriebssystem unterstützt.
Proth Prime Search Sieve (PPS-Sieve)
Frist:	6 Tage
Erster Download:	1 MB
Download:	0 Byte
Upload:	1 kB
Arbeitsspeicher:	50 MB
Betriebssysteme:
Grafikkarten
Bildschirmschoner:
Checkpoints:
Seventeen or Bust LLR (SOB)
Frist:	45 Tage
Erster Download:	35 MB
Download:	< 1 kB
Upload:	< 1 kB
Arbeitsspeicher:	125 MB
Betriebssysteme:
Bildschirmschoner:
Checkpoints:
Befehlssatzerweiterungen wie FMA3, AVX und SSE werden automatisch verwendet, sofern von CPU und Betriebssystem unterstützt. 50% Credit-Bonus aufgrund der WU-Laufzeit, weitere 10% Credit-Bonus, da das Subprojekt zum Beweis einer konkreten Vermutung dient.
Sierpinski/Riesel Base 5 LLR (SR5)
Frist:	15 Tage
Erster Download:	35 MB
Download:	< 1 kB
Upload:	< 1 kB
Arbeitsspeicher:	45 MB
Betriebssysteme:
Bildschirmschoner:
Checkpoints:
Befehlssatzerweiterungen wie FMA3, AVX und SSE werden automatisch verwendet, sofern von CPU und Betriebssystem unterstützt. Im Falle eines Primzahlfundes ca. zehnfache Laufzeit! 10% Credit-Bonus, da das Subprojekt zum Beweis einer konkreten Vermutung dient.
Sophie Germain Prime Search LLR (SGS)
Frist:	4 Tage
Erster Download:	35 MB
Download:	< 1 KB
Upload:	< 1 KB
Arbeitsspeicher:	8 MB
Betriebssysteme:
Bildschirmschoner:
Checkpoints:
Befehlssatzerweiterungen wie FMA3, AVX und SSE werden automatisch verwendet, sofern von CPU und Betriebssystem unterstützt. Im Falle eines Primzahlfundes ca. doppelte Laufzeit!
The Riesel Problem LLR (TRP)
Frist:	6 Tage
Erster Download:	35 MB
Download:	< 1 kB
Upload:	< 1 kB
Arbeitsspeicher:	45 MB
Betriebssysteme:
Bildschirmschoner:
Checkpoints:
Befehlssatzerweiterungen wie FMA3, AVX und SSE werden automatisch verwendet, sofern von CPU und Betriebssystem unterstützt. 10% Credit-Bonus aufgrund der WU-Laufzeit, weitere 10% Credit-Bonus, da das Subprojekt zum Beweis einer konkreten Vermutung dient.
The Riesel Problem Sieve (TRP-Sieve) [ausgesetzt]
Frist:	4 Tage
Erster Download:	21 MB
Download:	< 1 KB
Upload:	< 1 KB
Arbeitsspeicher:	40 MB
Bildschirmschoner:
Checkpoints:
Derzeit nicht verfügbar, da optimale Siebtiefe für den aktuellen Suchbereich erreicht.
The Sierpinski Problem ESP/PSP/SoB Sieve (ESP-Sieve) [ausgesetzt]
Frist:	4 Tage
Erster Download:	5 MB
Download:	< 1 kB
Upload:	< 1 kB
Arbeitsspeicher:	180 MB
Bildschirmschoner:
Checkpoints:
Derzeit nicht verfügbar, da optimale Siebtiefe für den aktuellen Suchbereich erreicht.
Woodall Prime Search LLR (WOO)
Frist:	14 Tage
Erster Download:	35 MB
Download:	< 1 kB
Upload:	< 1 kB
Arbeitsspeicher:	80 MB
Betriebssysteme:
Bildschirmschoner:
Checkpoints:
Befehlssatzerweiterungen wie FMA3, AVX und SSE werden automatisch verwendet, sofern von CPU und Betriebssystem unterstützt. 20% Credit-Bonus aufgrund der WU-Laufzeit.

PrimeGrid bringt die Spannung des Primzahlfindens in den Alltag des normalen Computernutzers. Es gibt ein großes Angebot an Subprojekten, die nach Primzahlen verschiedener Formen suchen. Während einige Subprojekte direkt an der Lösung eines mathematischen Problems arbeiten, jagen andere nach neuen Rekorden. Primzahlen spielen auch eine zentrale Rolle in modernen Verschlüsselungstechniken.

Inhaltsverzeichnis

1 Projektbeginn
2 Challenges
3 Subprojekte
4 Hinweise zur Benutzung von Grafikkarten
- 4.1 Proth Prime Search (Sieve)
- 4.2 Generalized Fermat Prime Search
5 Badges
6 Weblinks

Projektbeginn

Das Projekt startete am 12. Juni 2005, noch unter dem Namen Message@Home, und versuchte, MD5-verschlüsselte Texte wieder zu entschlüsseln. Zu diesem Zeitpunkt diente ein Notebook des Administrators Rytis Slatkevicius als Server. Der Sinn war die Entwicklung und das Testen von PerlBOINC, der in Perl programmierten BOINC-Serverseite.

Bald nahm PrimeGrid unter dem neuen Namen an der RSA Factoring Challenge RSA-640 teil, wobei RSA-640 im November von einem anderen Projekt faktorisiert wurde, und sich PrimeGrid dann RSA-768 widmete. Daraus wurde das Subprojekt primegen, das eine kontinuierliche Datenbank von Primzahlen, also von 2 aufwärts, erstellte, die frei heruntergeladen werden kann. Interessant ist, dass die gleiche Anwendung auch beim Testen von Chess960@home verwendet wurde.

Seit November 2006 unterstützte PrimeGrid das Projekt Twin Prime Search. Der dafür eingesetzte LLR-Wrapper, der in ähnlicher Form auch vom Projekt Riesel Sieve eingesetzt wurde, war die Grundlage für die Aufnahme weiterer Subprojekte in den folgenden Jahren.

Challenges

Informationen und eine Übersicht der Ergebnisse der Challenges gibt es hier: PrimeGrid Challenge Series

Subprojekte

In den Projekteinstellungen kann der User eins oder mehrere der unter BOINC zur Verfügung stehenden Subprojekte auswählen. Die Subprojekte können grob in zwei Kategorien aufgeteilt werden: Primalitätstests und Sieving.

Neuere Intel-CPUs mit den Befehlssatzerweiterungen FMA3 (ab Haswell) und AVX (ab Sandy Bridge) haben bei den LLR-Subprojekten große Vorteile. Ältere CPUs laufen bei den Sieve-Subprojekten effizient, sofern 64-Bit-Systeme eingesetzt werden. Für Proth Prime Search (Sieve), AP27 und Generalized Fermat Prime Search sowie Teile der Project Staging Area können CUDA- und OpenCL-fähige NVIDIA-Grafikkarten und OpenCL-fähige AMD-Grafikkarten eingesetzt werden.

Primalitätstests

LLR ist ein von Jean Penné entwickeltes Programm, mit dem festgestellt werden kann, ob eine Zahl prim ist oder nicht (Primalitätstest). Je nach Form der zu testenden Zahl kommen verschiedene Algorithmen zur Anwendung. So wird für Zahlen der Form k⋅2ⁿ-1 ein Lucas-Lehmer-Riesel-Test und für k⋅2ⁿ+1 ein Proth-Test durchgeführt.

Das Programm ist sehr CPU-intensiv, schon die kleinste Instabilität des Rechners kann zu Berechnungsfehlern führen. Besonders bei übertakteten Prozessoren ist Vorsicht geboten.

In der aktuellen Version ist die Anwendung Multithread fähig, es können also mehrere Prozessorkerne an einer WU arbeiten. Um Multithreading nutzen zu können, benötig man eine app_config.xml. Wie man diese erstellt, kann hier nachlesen werden.

Folgende LLR-Subprojekte stehen unter BOINC zur Verfügung:

Die verschiedenen Genefer-Versionen von David Underbakke, Yves Gallot, Shoichiro Yamada et al. führen sehr schnelle Tests für verallgemeinerte Fermatzahlen (Generalized Fermat Numbers, GFN) durch. Technisch gesehen können hierbei auch Pseudoprimzahlen gefunden werden, sodass positiv getestete Zahlen anschließend noch mit einem anderen Programm auf Primalität überprüft werden müssen.

In der aktuellen Version ist die CPU-Anwendung für Genefer 21 Multithread fähig, es können also mehrere Prozessorkerne an einer WU arbeiten. Um Multithreading nutzen zu können, benötig man eine app_config.xml. Wie man diese erstellt, kann hier nachlesen werden.

Genefer wird für folgende BOINC-Subprojekte benutzt:

Generalized Fermat Prime Search (Short und World Record)

Die nur für Grafikkarten angebotene Option World Record bietet die Möglichkeit, eine neue Weltrekordprimzahl zu finden.

Zudem gibt es die 'AP26/27 Search', bei der es um die Suche nach Primzahlen mit arithmetischer Progression geht.

AP26 Search

Sieving

Ein Primalitätstest einer großen Zahl dauert mitunter sehr lange. Deshalb prüft man zunächst, ob die zu testenden Zahlen durch (verhältnismäßig) kleine Zahlen teilbar sind. Dazu werden, je nach Form der Primzahlkandidaten, die Programme sr2sieve von Geoff Reynolds und tpsieve von Ken Brazier verwendet. Ist eine Zahl durch eine andere Zahl außer 1 und sich selbst teilbar, ist sie keine Primzahl, somit werden nach und nach einige Primzahlkandidaten ausgesiebt (engl. to sieve = sieben).

Folgende Sieve-Subprojekte stehen aktuell unter BOINC zur Verfügung:

Project Staging Area

Einige Subprojekte sind nicht unter BOINC verfügbar. Teils steht die benötigte Software unter BOINC nicht zur Verfügung, teils sind die Projekte in einem frühen Stadium und behandeln so kleine Zahlen, dass eine Verarbeitung über BOINC ineffizient wäre und zu viel Serverlast verursachen würde. Stattdessen wird für Primalitätstests PRPNet, ein sehr einfach gehaltener Client speziell zur Primzahlsuche, eingesetzt, während beim Sieving das entsprechende Programm direkt vom Benutzer ausgeführt wird (manuelles Sieving).

Folgende Projekte sind Teil der Project Staging Area:

27121 Prime Search
Factorial Prime Search
Generalized Fermat Prime Search (Genefer-Tests und Sieving)
Primorial Prime Search
Proth Prime Search (teilweise Sieving und Suche nach Megaprimzahlen)
WWWW Prime Search

Hinweise zur Benutzung von Grafikkarten

Proth Prime Search (Sieve)

Für alle CUDA-fähigen NVIDIA-Grafikkarten verfügbar.
OpenCL-fähige ATI/AMD-Grafikkarten ab der 4000er-Reihe können benutzt werden, sofern der APP-Treiber installiert ist (in aktuellen Treiberpaketen enthalten).

Generalized Fermat Prime Search

Verfügbar für NVIDIA-Grafikkarten ab Compute Capability 1.3 (wegen Double Precision), vgl. Übersicht.
Verfügbar für Double-Precision- und OpenCL-fähige ATI/AMD-Grafikkarten

Für NVIDIA-Grafikkarten kann zwischen der CUDA- und der OpenCL-Anwendung gewählt werden. Üblicherweise ist die OpenCL-Anwendung für neuere Grafikkarten ab GTX 6xx die bessere Wahl.

Für die CUDA-Version gibt es eine zusätzliche Einstellmöglichkeit Block size:

Mit der Standardeinstellung 0 bestimmt die Anwendung automatisch durch einen kleinen Benchmark die schnellste Einstellung.
Starkes Ruckeln lässt sich mitunter mit den Werten 7, 6 oder 5 lindern. Das kann aber die GPU-Auslastung und die Geschwindigkeit deutlich verringern und die CPU-Last erhöhen.

Sogar nicht übertaktete Grafikkarten können bei Generalized Fermat Prime Search Stabilitätsprobleme bekommen. Insbesondere zu hoher Speichertakt führt oft zu Berechnungsfehlern. Gute Kühlung ist unverzichtbar.

Badges

Für einige ausgewählte Meilensteine werden Abzeichen, die sog. Badges, vergeben.

Subprojekt	Bronze	Silber	Gold	Amethyst	Rubin	Türkis	Jade	Saphir	Smaragd
Subprojekt	^10k	^100k	^500k	^1M	^2M	^5M	^10M	^20M	^50M
321 Prime Search LLR (321)
Cullen Prime Search LLR (CUL)
Extended Sierpinski Problem LLR (ESP)
Generalized Cullen/Woodall Prime Search LLR (GCW)
Proth Prime Search LLR (PPS) inkl. PPSE und MEGA
Prime Sierpinski Problem LLR (PSP)
Seventeen or Bust LLR (SOB)
Sierpinski/Riesel Base 5 Problem LLR (SR5)
Sophie Germain Prime Search LLR (SGS)
Twin Prime Search LLR (TPS)
The Riesel Problem LLR (TRP)
Woodall Prime Search LLR (WOO)
321 Prime Search Sieve (321-Sieve)
Cullen/Woodall Prime Search Sieve (CW-Sieve)
Generalized Cullen/Woodall Prime Search Sieve (GCW-Sieve)
Proth Prime Search Sieve (PPS-Sieve)
The Sierpinski Problem ESP/PSP/SoB Sieve (ESP-Sieve)
The Riesel Problem (Sieve)
AP26 Search
Generalized Fermat Prime Search
Project Staging Area

Subprojekt	Doppelt Bronze	Doppelt Silber	Doppelt Gold	Doppelt Amethyst	Doppelt Rubin	Doppelt Türkis	Doppelt Jade	Doppelt Saphir	Doppelt Smaragd
Subprojekt	^100M	^200M	^500M	^1G	^2G	^5G	^10G	^20G	^50G
321 Prime Search LLR (321)
Cullen Prime Search LLR (CUL)
Extended Sierpinski Problem LLR (ESP)
Generalized Cullen/Woodall Prime Search LLR (GCW)
Proth Prime Search LLR (PPS) inkl. PPSE und MEGA
Prime Sierpinski Problem LLR (PSP)
Seventeen or Bust LLR (SOB)
Sierpinski/Riesel Base 5 Problem LLR (SR5)
Sophie Germain Prime Search LLR (SGS)
Twin Prime Search LLR (TPS)
The Riesel Problem LLR (TRP)
Woodall Prime Search LLR (WOO)
321 Prime Search Sieve (321-Sieve)
Cullen/Woodall Prime Search Sieve (CW-Sieve)
Generalized Cullen/Woodall Prime Search Sieve (GCW-Sieve)
Proth Prime Search Sieve (PPS-Sieve)
The Sierpinski Problem ESP/PSP/SoB Sieve (ESP-Sieve)
The Riesel Problem (Sieve)
AP26 Search
Generalized Fermat Prime Search
Project Staging Area