Een Sophie Germain priemgetal is een priemgetal p met de eigenschap dat 2p+1 ook een priemgetal is. De tweede priemfactor q=2p+1 wordt gewoonlijk een veilig priemgetal genoemd. De naam verwijst naar de Franse wiskundige Sophie Germain, die bijdragen leverde aan de getaltheorie en na wie deze klasse priemgetallen is vernoemd. Het begrip is eenvoudig te formuleren, maar leidt tot diepe vragen en praktische toepassingen.
Definitie en voorbeelden
Formeel: p is een Sophie Germain priemgetal als p en q=2p+1 beide priem zijn. Enkele kleine voorbeelden zijn p=2 (want 2·2+1=5), p=3 (2·3+1=7), p=5 (11), p=11 (23) en p=23 (47). Er zijn vele grotere voorbeelden, en computers hebben honderden miljoenen van dergelijke priemgetallen gevonden binnen grote bereiken, maar het bewijs voor oneindigheid ontbreekt.
Kenmerken en rekenkundige beperkingen
Sophie Germain priemgetallen voldoen aan bepaalde congruentievoorwaarden: elk p>3 dat een Sophie Germain priem is, voldoet aan p≡2 (mod 3). Dit volgt omdat als p≡1 (mod 3) dan 2p+1≡0 (mod 3) en dus niet priem kan zijn. Vergelijkbare uitsluitingen bestaan voor andere kleine moduli: als p voldoet aan 2p+1≡0 (mod r) voor een klein r, dan is dat congruentieklasse uitgesloten. Zulke rekenkundige beperkingen verminderen de mogelijke residuklassen maar bewijzen niet het einde van de rij.
Relatie met veilige priemgetallen en crypto
De getallen q=2p+1 die bij Sophie Germain priemgetallen horen, noemt men veilige priemgetallen. Een veilige priem q heeft een grote priemfactor (p) van q−1, wat in cryptografische protocollen zoals Diffie–Hellman en sommige varianten van de discrete logaritme veiligere groepen oplevert. Daarom zijn Sophie Germain priemgetallen van praktisch belang bij het genereren van cryptografische sleutels: men zoekt eerst p zodat q=2p+1 ook priem is, en gebruikt dan q of de grote orde p als groepsgrootte.
Geschiedenis, bekendheid en open problemen
De studie van dit type priemgetallen gaat terug naar de 19e eeuw en draagt de naam van Sophie Germain. Een van de belangrijkste open vragen is of er oneindig veel Sophie Germain priemgetallen zijn. Heuristieken uit de analytische priemgetaltheorie, vergelijkbaar met die voor tweelingpriemgetallen, voorspellen dat er naar schatting asymptotisch veel van deze priemgetallen zijn, met een dichtheid van orde x/(log x)^2 tot constanten. Tot op heden is dat echter niet bewezen.
Onderzoek en praktische aanwijzingen
Computers en gedistribueerde projecten hebben vele honderden miljoenen voorbeelden opgespoord en gebruiken speciale tests voor grote priemgetallen. In theoretisch onderzoek speelt het onderwerp een rol in het begrijpen van het gedrag van priemgetallen in lineaire polynomen en in het formuleren van meer algemene conjecturen over vormen ap+b. Voor aanvullende informatie over de definitie en eigenschappen zie meer uitleg.
- Voorbeeld: p=29 geeft q=59 — beide priem.
- Notabel: voor p>3 geldt p≡2 (mod 3).
- Toepassing: gebruikte stap bij het maken van veilige cryptografische groepen.