De Wiskunde achter Prime95.

Deze pagina gaat over de wiskunde en de computeralgoritmes die worden gebruikt in de zoektocht naar nieuwe Mersennepriemgetallen.

Een Lijst Vormen
Wat Mersennegetallen betreft, is het eenvoudig te bewijzen dat als 2p-1 een priemgetal is, ook p een priemgetal moet zijn. Dus is de eerste stap in de zoektocht het maken van een lijst met priemexponenten om te testen.

Stelling: Als 2p-1 priem is, dan is ook p priem.

Bewijs:
Stel r en s positief, dan is de veelterm xrs-1 gelijk aan xs keer xs(r-1) + xs(r-1) + ... + xs + 1 (Eenvoudigste voorbeeld: x2-1 = (x-1)(x+1)). Dus als p deelbaar is (stel p = r*s met 1p-1 ook deelbaar (want het is deelbaar door 2s-1). Dus als 2p-1 priem is, dan is ook p priem.

Trial-Factoring (Delers Zoeken)
De volgende stap is het elimineren van exponenten door kleine delers te zoeken. Er zijn zeer efficiŽnte algoritmen om te bepalen of een getal deler is van 2p-1. Neem bijvoorbeeld het volgende algoritme (zonder bewijs). Laten we onderzoeken of 47 deler is van 223-1. Eerst zet je de exponent 23 om naar een binair getal, je krijgt 10111. Je start met het cijfer 1, waarvan je het kwadraat neemt. Bekijk nu de 1ste bit van de exponent en als die 1 is, vermenigvuldig je het kwadraat (dat je eerst berekende) met 2 en bereken je daarvan de rest bij deling door 47. Neem daar weer het kwadraat van, neem nu de volgende bit van de exponent en als die 1 is, vermenigvuldig je het kwadraat weer met 2, neem je daarvan weer de rest, ... Voor het voorbeeld ziet dat er als volgt uit.

Kwadraat Neem telkens de
volgende bit
Vermenigvuldig
eventueel met 2
Neem de rest bij
deling door 47
1*1 = 1 1 0111 1*2 = 2 2
2*2 = 4 0 111 / 4
4*4 = 16 1 11 16*2 = 32 32
32*32 = 1024 1 1 1024*2 = 2048 27
27*27 = 729 1   729*2=1458 1

Dus, 223 = 1 mod 47 (Als dit Chinees lijkt: dit wil zeggen dat de deling van 223 door 47 rest 1 heeft of dat dus 223 = 1+k*47 met k een natuurlijk getal, mod is de afkorting van modulo). Trek nu 1 af van beide kanten, en dan komt er 223-1 = 0 mod 47 (223-1 is deelbaar door 47). Aangezien 47 dus een deler is, is 223-1 geen priemgetal.

Eťn van de mooie eigenschappen van Mersennegetallen is dat elke deler q van 2p-1 van de vorm 2kp+1 is. Bovendien moet q 1 of 7 mod 8 zijn (bij deling door 8 moet de rest 1 of 7 zijn) en kan een efficiŽnt programma gebruik maken van het feit dat elke mogelijke factor q priem moet zijn.

De code van het GIMPS "factoring"-algoritme maakt een aangepaste zeef van Eratosthenes (De zeef van Erathosthenes is een algoritme om priemgetallen te berekenen door van de getallen 2 tot n telkens de veelvouden van de priemgetallen weg te schrappen, beginnend bij de tweevouden, daarna de drievouden, etcÖ De overblijvende getallen zijn priemgetallen.), waarbij elke bit een potentiŽle 2kp+1 deler voorstelt. De zeef elimineert dan alle potentiŽle delers die deelbaar zijn door een priemgetal kleiner dan 40.000 ongeveer. Ook de bits die mogelijke delers voorstellen van de vorm 3 of 5 mod 8 worden verwijderd. Dit proces elimineert ongeveer 95% van de mogelijke delers. De overige kandidaten worden getest met het algoritme dat eerder werd uitgelegd.

Nu is de enige nog resterende vraag hoeveel "trial factoring" er moet gedaan worden? Het antwoord hangt af van 3 variabelen: de kost van het factoriseren (hoeveel tijd neemt het in beslag?), de kans om een factor te vinden, en de kost van een "primality test" (de overige nodige processen om te controleren of het getal priem is).

De gebruikte formule is: de kost om te factoriseren moet kleiner zijn dan de kans om een factor te vinden maal 2 keer de kost van de "primality test" (factorisatiekost < slaagkans * 2 * kost van priemtest). De tijd die gespendeerd wordt moet dus kleiner zijn dan de tijd die naar de verwachting wordt uitgespaard. Als een deler gevonden word, kunnen we zowel de eerste test als de "double-check" test uitsparen.

Als we de data van factorisaties bekijken die vroeger al gemaakt zijn, dan blijkt dat de kans op het vinden van een deler tussen 2x en 2x+1 ongeveer 1/x is. De kost van het factoriseren en de kost van de priemtest worden berekend door het programma te timen. Op dit moment factoriseert het programma tot de volgende limieten:

Exponenten tot Delers zoeken tot
3.960.000 260
5.160.000 261
6.515.000 262
8.250.000 263
13.380.000 264
17.850.000 265
21.590.000 266
28.130.000 267
35.100.000 268
44.150.000 269
57.020.000 270
71.000.000 271
79.300.000 272

P-1 Factoriseren
Er is nog een andere factorisatiemethode die GIMPS gebruikt voor het vinden van delers waardoor het kostelijke priemtesten kan vermijden. Deze methode wordt de methode van Pollard (P-1) genoemd. Als q een deler is van een getal, dan zal het P-1 algoritme deze deler vinden als q zeer deelbaar is - als het dus enkel kleine delers heeft.

Deze methode is nog effectiever als het wordt toegepast op Mersennegetallen. Herinner je dat de deler q van de vorm 2kp+1 is. Het is gemakkelijk om het P-1 algoritme zo aan te passen zodat het de deler q zal vinden als k zeer deelbaar is.

Het P-1 algoritme is redelijk eenvoudig. Neem eerst een grens B1. Het algoritme zal de deler q vinden zolang dat alle delers van k kleiner zijn dan B1. Bereken daarna E - het product van alle priemgetallen kleiner dan B1. Ten derde, bereken je x = 3E*2*p. Controleer ten slotte de grootste gemene deler van x-1 en 2p-1 om te zien of een deler gevonden is.

Er is een uitbreiding van Pollards algoritmme die een tweede grens B2 gebruikt en de deler q zal vinden als k juist ťťn deler heeft tussen B1 en B2 en als alle overige delers van k onder B1 liggen.

GIMPS heeft dit algoritme gebruikt om enkele opmerkelijke delers te vinden. Bijvoorbeeld:

22944999-1 is deelbaar door 341584703073057080643101377.

314584703073057080643101377 is 2 * 53409984701702289312 * 2944999 + 1.

De waarde k, 53409984701702289312 is zeer eenvoudig:

53409984701702289312 = 25 * 3 * 19 * 947 * 7187 * 62297 * 69061.

Hoe kiest GIMPS dan slim de waarden van B1 en B2? We gebruiken een variant van de formule, gebruikt in "trial factoring". We moeten de volgende waarde zo groot mogelijk maken:

Kans om een deler te vinden * 2 * kost van de priemtest - kost van het factoriseren.

De kans om een deler te vinden en de kost van het factoriseren variŽren beide bij verschillende B1 en B2 waarden. De functie van Dickman (zie "Knuth's Art of Computer Programming Vol. 2") wordt gebruikt om de kans om een deler te vinden te bepalen, k heeft dus enkel delers onder B1 of slechts enkel delers onder B1 behalve ťťn tussen B1 en B2. Het programma probeert veel waarden van B1 en als er genoeg geheugen beschikbaar is, verschillende waarden van B2, om aldus de B1 en B2 waarden te kiezen die de formule hierboven zo groot mogelijk maken.

De Lucas-Lehmer Test
De Lucas-Lehmer priemtest is verrassend eenvoudig. Het stelt dat voor P > 2, 2p-1 priem is als en slechts als Sp-2 nul is in de volgende reeks: , . Of dus: met k een natuurlijk getal. Bijvoorbeeld, om te bewijzen dat 27-1 priem is:

S0 = 4
S1 = 4 * 4 - 2 mod 127 = 14
S2 = 14 * 14 - 2 mod 127 = 67
S3 = 67 * 67 - 2 mod 127 = 42
S4 = 42 * 42 - 2 mod 127 = 111
S5 = 111 * 111 - 2 mod 127 = 0

Om de Lucas-Lehmer test zo efficiŽnt mogelijk te kunnen gebruiken, moet men de snelste manier vinden om enorme getallen modulo 2p-1 te kunnen kwadrateren. Sinds de late jaren '60 is het snelste algoritme om grote getallen te kwadrateren het splitsen van de grote getallen in kleine stukken die een rij vormen, daarop de "Fast Fourier Transformatie (FFT)" toe te passen, te kwadrateren en daarop de Omgekeerde FFT ("Inverse Fast Fourier Transform" (IFFT)) toe te passen. Er valt nog veel te vertellen over het gebruik van deze Fast Fourier Transformaties in het programma, maar dit is zware wiskunde en informatica en zou ons te ver brengen mochten we daarop ingaan.

Wat zijn nu de kansen dat de Lucas-Lehmer test een nieuw Mersenne priemgetal vindt? Een simpele benadering is om herhaaldelijk de vaststelling dat de kans om een deler te vinden tussen 2x en 2x+1 ongeveer 1/x is, toe te passen. Bijvoorbeeld, je bent 210000139-1 aan het testen, waarvan "trial factoring" heeft aangetoond dat er geen delers zijn onder 264. De kans dat het priem is, is dan de kans op geen 65-bit factor * de kans op geen 66-bit factor * ... * de kans op geen 5000070-bit factor. Dat is dus . Dit vereenvoudigt tot 64/5000070 of 1 op 78126. Deze eenvoudige benadering is niet helemaal correct. Het zou een formule geven van (hoe ver gefactoriseerd) / (exponent gedeeld door 2). Serieuzere benaderingen tonen echter aan dat de formule gelijk is aan (hoe ver gefactoriseerd - 1) / (exponent maal de constante van Euler (0.577...)). In dit geval, 1 in 91623. Enkele andere niet-bewezen stelling vindt je hier (Caldwell's Primepages).

Double-Checking
Om er zeker van te zijn dat een Lucas-Lehmer priemtest uitgevoerd is zonder fouten, voert GIMPS de priemtest een tweede keer uit. Tijdens elk van beide testen, worden de laatste 64 bits van de laatste Sp-2-waarde bijgehouden. Als deze overeenkomen, dan beschouwt GIMPS de exponent als correct gedoublechecked. Als ze niet dezelfde zijn, dan wordt de priemtest een derde maal uitgevoerd, tot ze wťl overeenkomen.

Uit gegevens van afgewerkte priemtesten blijkt dat bij ongeveer 1.5% van de testen waar geen zware fouten gemeld waren, toch een fout is opgetreden. Voor Lucas-Lehmer testen waar wel een fout was gemeld, was er in 50 % van de gevallen daadwerkelijk een fout opgetreden. Daarbij wordt de "Illegal Sumout" niet als zware fout beschouwd.