Lucas–Lehmer–Riesel test

Inom matematik är Lucas–Lehmer–Riesel-testet ett primalitetstest för tal av formen N = k ⋅ 2 ⁿ − 1 ( Rieseltal) med udda k < 2 ⁿ . Testet har utvecklats av Hans Riesel och det är baserat på Lucas–Lehmer primalitetstestet . Det är den snabbaste deterministiska algoritmen som är känd för tal av den formen. För tal av formen N = k ⋅ 2 ⁿ + 1 ( Proth-tal ), antingen tillämpning av Proths sats (en Las Vegas-algoritm ) eller ett av de deterministiska bevisen som beskrivs i Brillhart-Lehmer-Selfridge 1975 (se Pocklington primalitetstest ) används.

Algoritmen

Algoritmen är väldigt lik Lucas–Lehmer-testet , men med en variabel utgångspunkt beroende på värdet på k .

Definiera en sekvens u _i för alla i > 0 genom att:

$u_{i}=u_{i-1}^{2}-2.\,$

Då är N = k ⋅ 2 ⁿ − 1, med k < 2 ⁿ primtal om och endast om den delar u _{n −2} .

Hitta startvärdet

₀ Startvärdet u bestäms enligt följande.

• Om k ≡ 1 eller 5 (mod 6): om 1 (mod 6) och n är jämnt, eller 5 (mod 6) och n är udda, så delar 3 N, och det finns ingen anledning att testa. Annars kan N ≡ 7 (mod 24) och Lucas V(4,1)-sekvensen användas: vi tar ${\displaystyle u_{0}=(2 +{\sqrt {3}})^{k}+(2-{\sqrt {3}})^{k}} ,$ vilket är den k: te termen i den sekvensen. Detta är en generalisering av det vanliga Lucas-Lehmer-testet och reduceras till det när k = 1.
• ₀₀ Annars är vi i fallet där k är en multipel av 3, och det är svårare att välja rätt värde på u . Det är känt att om k = 3 och n ≡ 0 eller 3 (mod 4), kan vi ta u = 5778.

₀ En alternativ metod för att hitta startvärdet u ges i Rödseth 1994. Urvalsmetoden är mycket enklare än den som Riesel använder för fallet med 3 delar k . Hitta först ett P -värde som uppfyller följande likheter för Jacobi-symboler :

$\left({\frac {P-2}{N}}\right)=1\quad {\text{and}} \quad \left({\frac {P+2}{N}}\right)=-1$ .

I praktiken behöver endast ett fåtal P- värden kontrolleras innan ett hittas (5, 8, 9 eller 11 fungerar i cirka 85 % av försöken).

₀ För att hitta startvärdet u från P -värdet kan vi använda en Lucas(P,1)-sekvens, som visas i såväl som sidan 124 av. Den senare förklarar att när 3 ∤ k kan P =4 användas enligt ovan, och ingen ytterligare sökning är nödvändig .

₀ Startvärdet u kommer att vara Lucas- sekvenstermen Vk ( P _{, 1} ) taget mod N. Denna urvalsprocess tar mycket kort tid jämfört med huvudtestet.

Hur testet fungerar

Lucas-Lehmer-Riesel-testet är ett särskilt fall av grupporder-primalitetstestning; vi visar att något tal är primtal genom att visa att någon grupp har den ordning som den skulle ha varit det primtal, och vi gör detta genom att hitta ett element i den gruppen av exakt rätt ordning.

För tester av Lucas-stil på ett tal N arbetar vi i den multiplikativa gruppen av en kvadratisk förlängning av heltalen modulo N ; om N är primtal är ordningen för denna multiplikativa grupp N ² − 1, den har en undergrupp av ordningen N + 1, och vi försöker hitta en generator för den undergruppen.

Vi börjar med att försöka hitta ett icke-iterativt uttryck för u $\displaystyle u_{i}}$ . Följ modellen av Lucas–Lehmer-testet, sätt $u_{i}=a^{2^{i}}+a^{-2^{i}}$ , och genom induktion har vi $u_{i}=u_{i-1}^{2}-2$ .

Så vi kan betrakta oss själva som att vi tittar på den 2 ⁱ :e termen i sekvensen $v(i)=a^{i}+a^{-i}$ . Om a uppfyller en andragradsekvation är detta en Lucas-sekvens och har ett uttryck av formen $v(i)=\alpha v(i-1)+\beta v(i-2)$ . Egentligen tittar vi på k ⋅ 2 ⁱ :e termen i en annan sekvens, men eftersom decimeringar (ta var k: te term som börjar med nolldelen) av en Lucas-sekvens i sig är Lucas-sekvenser, kan vi hantera faktorn k med välja en annan utgångspunkt.

LLR programvara

LLR är ett program som kan köra LLR-testerna. Programmet utvecklades av Jean Penné. Vincent Penné har modifierat programmet så att det kan få tester via Internet. Programvaran används både av enskilda prime searchers och vissa distribuerade datorprojekt inklusive Riesel Sieve och PrimeGrid .

Se även

• Rieselnummer

•   Riesel, Hans (1969). "Lukasiska kriterier för primäriteten av N = h ·2 ⁿ − 1". Beräkningsmatematik . American Mathematical Society. 23 (108): 869–875. doi : 10.2307/2004975 . JSTOR 2004975 .

externa länkar

• Ladda ner Jean Pennés LLR
• Math::Prime::Util::GMP - En del av Perls nteorimodul, denna har grundläggande implementeringar av LLR- och Proth-formtestning, samt några BLS75-bevismetoder.