Ours go to 211: Euler pseudoprimes to 47 prime bases (from Carmichael numbers)

Titel: ONS GAAT TOT 211: EULER PSEUDO-PRIMAIRE GETALLEN TOT 47 PRIMAIRE BASES

Auteurs: Alejandra Alcantarilla Sánchez, Jolijn Cottaar, Tanja Lange, en Benne de Weger.

---

1. Probleemstelling

Veel publieke-sleutel cryptosystemen, zoals RSA en Diffie-Hellman, zijn afhankelijk van het genereren van grote priemgetallen. Omdat het bewijzen dat een willekeurig getal priem is computationeel te duur is, maken implementaties gebruik van probabilistische compositietests, zoals de Solovay-Strassen-test of de Miller-Rabin-test.

• De Test: De Solovay-Strassen-test controleert voor een kandidaat $n$ en een basis $a$ of de Euler-criterium geldt:
  $$\left(\frac{a}{n}\right) \equiv a^{(n-1)/2} \pmod n$$
  waarbij $\left(\frac{a}{n}\right)$ het Jacobi-symbool is.
• Het Risico: Een samengesteld getal dat deze test doorstaat voor een bepaalde basis $a$ wordt een Euler-pseudopriem genoemd, en $a$ wordt een "Euler-leugenaar" (Euler liar).
• De Uitdaging: Hoewel de kans dat een willekeurig samengesteld getal de test doorstaat voor één basis hoogstens 1/2 is, bestaat er een risico op "adversariale" aanvallen. Als een aanvaller getallen kan construeren die de test doorstaan voor vele opeenvolgende priemgetallen als basis, kan deze de gebruiker misleiden om een samengesteld getal als priem te accepteren.

Het doel van dit paper is het vinden van de "beste" Euler-pseudopriemen: samengestelde getallen die de Solovay-Strassen-test doorstaan voor het maximale aantal opeenvolgende priemgetallen als basis, beginnend bij 2.

---

2. Methodologie

De auteurs hanteren een gestructureerde aanpak die begint met theoretische classificatie en eindigt met een geoptimaliseerd zoekalgoritme.

A. Classificatie van Carmichael-getallen

De auteurs stellen dat Carmichael-getallen (samengestelde getallen die $a^{n-1} \equiv 1 \pmod n$ voldoen voor alle $a$ copriem met $n$) de beste kandidaten zijn voor Euler-pseudopriemen. Ze classificeren deze getallen op basis van de Carmichael-lambda functie $\lambda(n)$ en de index $i(n) = (n-1)/\lambda(n)$.

Ze onderscheiden drie klassen:

1. Klasse A: $i(n)$ is even.
   • Resultaat: Deze klasse heeft de theoretisch maximale hoeveelheid Euler-leugenaars: precies $\frac{1}{2}\phi(n)$. Alle leugenaars hebben Jacobi-symbool 1.
2. Klasse B1: $i(n)$ is oneven en er is een "ongelijkheid" in de 2-adische waardes van de priemfactoren.
   • Resultaat: Minder leugenaars dan Klasse A.
3. Klasse B2: $i(n)$ is oneven en alle priemfactoren hebben dezelfde 2-adische waarde.
   • Resultaat: Minst gunstig voor het doorstaan van de test.

Conclusie: De zoektocht focust uitsluitend op Klasse A, omdat deze de hoogste kans biedt om de test voor veel bases te doorstaan.

B. Constructie door Vermenigvuldiging

In plaats van willekeurige getallen te testen, construeren de auteurs grotere pseudopriemen door bestaande Euler-pseudopriemen met elkaar te vermenigvuldigen.

• Voorwaarde: Het product van twee Carmichael-getallen is alleen een Carmichael-getal als aan specifieke voorwaarden wordt voldaan (gebaseerd op Lemma 12 in het paper).
• Strategie: Ze vermenigvuldigen alleen getallen die tot dezelfde maximale basis $a$ door de test komen (bijvoorbeeld twee getallen uit de verzameling epsp(a)).
• Wiskundige onderbouwing (Lemma 13): Als $n_1$ en $n_2$ beide in Klasse A zitten en de test doorstaan tot basis $a$, dan is hun product $n = n_1 n_2$ (als het een Carmichael-getal is) gegarandeerd een Euler-pseudopriem voor de volgende priembasis $b$ (mits $b$ geen factor is van $n$). Dit komt omdat de Jacobi-symbolen voor $b$ bij beide factoren -1 zijn, waardoor hun product 1 wordt, wat overeenkomt met de exponentiële kant van de test.

C. Het Zoekalgoritme

Het algoritme (Algorithm 1) werkt als volgt:

1. Filtering: Start met een lijst van "atomaire" Carmichael-getallen (niet-producten van andere Carmichael-getallen) met priemfactoren > 150 (om kleine factoren te vermijden).
2. Selectie: Houd alleen getallen over die in Klasse A zitten en de test doorstaan tot een bepaalde basis $a$ (bijv. $a \ge 37$).
3. Vermenigvuldiging: Vermenigvuldig paren uit deze lijst.
   • Controleer snel of het product in Klasse A blijft (via 2-adische waardes van $n-1$ en $\lambda(n)$).
   • Controleer of het product vierkantvrij is (squarefree).
   • Controleer of $\lambda(n) | (n-1)$.
4. Validatie: Test het nieuwe product op de volgende priemgetallen. Omdat de theorie garandeert dat het tot de volgende basis doorstaat, begint de test pas bij de basis na de volgende.
5. Iteratie: Herhaal dit proces om getallen te bouwen van hogere orde (bijv. producten van 4, 8, 16 atomaire getallen).

---

3. Belangrijkste Bijdragen

1. Theoretische Classificatie: Een nieuwe, gedetailleerde classificatie van Carmichael-getallen in Klassen A, B1 en B2, met een exacte telling van het aantal Euler-leugenaars per klasse.
2. Constructieve Methode: Het bewijzen en toepassen dat het vermenigvuldigen van Euler-pseudopriemen uit dezelfde "survival-set" (zelfde maximale basis) een efficiënte manier is om grotere pseudopriemen te vinden die nog langer "overleven".
3. Optimalisatie: Het ontwikkelen van een algoritme dat gebruikmaakt van de structuur van Klasse A en 2-adische eigenschappen om de zoekruimte drastisch te verkleinen en berekeningen te versnellen.
4. Nieuwe Sophie Germinus Pseudopriemen: De introductie van een nieuwe klasse samengestelde getallen (producten van Sophie Germain-priemen) als alternatieve kandidaten, hoewel deze minder effectief bleken dan Carmichael-getallen voor dit specifieke doel.

---

4. Resultaten

De auteurs hebben een reeks Euler-pseudopriemen gegenereerd die de Solovay-Strassen-test doorstaan voor een recordaantal opeenvolgende priemgetallen als basis:

• Beste resultaat: Een samengesteld getal van 1230 bits.
• Overleving: Dit getal doorstaat de test voor de eerste 47 priemgetallen als basis.
• Grenswaarde: Het getal overleeft tot en met de basis 211 (wat de 47e priem is).
• Vergelijking:
  • Miller-Rabin heeft een faalkans van maximaal $1/4$ per basis.
  • Solovay-Strassen heeft een faalkans van maximaal $1/2$ per basis.
  • Het gevonden getal overleeft dus 47 bases, wat een enorme prestatie is in de context van probabilistische testen.

De auteurs rapporteren ook de grootte van de gevonden verzamelingen (epsp(a), epsp2(a), etc.) in tabellen, waarbij te zien is dat de hoeveelheid geldige producten exponentieel afneemt naarmate de basis groter wordt, maar dat er steeds nog nieuwe, grotere getallen gevonden kunnen worden door slimme filtering.

---

5. Betekenis en Impact

• Beveiliging van Cryptosystemen: Dit onderzoek onderstreept het risico van het gebruik van probabilistische testen zonder voldoende bases of zonder controle op "adversariale" input. Het toont aan dat het mogelijk is om samengestelde getallen te construeren die extreem goed doen in de Solovay-Strassen-test.
• Validatie van Tests: Het resultaat bevestigt dat de Solovay-Strassen-test, hoewel robuust, kwetsbaar is voor specifieke constructies. Het benadrukt het belang van het gebruik van meerdere bases en het vermijden van voorspelbare patronen bij het genereren van "primes".
• Wiskundige Inzicht: De paper levert een diep inzicht in de structuur van Carmichael-getallen en de verdeling van Euler-leugenaars, wat waardevol is voor de getaltheorie en de cryptografie.
• Praktische Implicatie: Voor ontwikkelaars van cryptosystemen betekent dit dat het genereren van priemgetallen niet alleen gebaseerd mag zijn op het doorstaan van een paar bases, maar dat men rekening moet houden met de mogelijkheid van geconstrueerde pseudopriemen, vooral in scenario's waar de invoer niet volledig willekeurig is.

Kortom, de auteurs hebben een nieuwe grens gezet in het vinden van "slimme" samengestelde getallen die zich als priem gedragen voor een ongekend groot aantal testen, wat zowel een waarschuwing als een prestatie op het gebied van computeralgebra is.