Prvočíslo Sophie Germainové je speciální typ prvočísla. Formálně: prvočíslo p je prvočíslo Sophie Germainové právě tehdy, když je i číslo 2p+1 prvočíslem. Číslo q = 2p+1, které vznikne tímto způsobem, se nazývá bezpečné prvočíslo (safe prime).

Tyto prvočísla jsou pojmenována po francouzské matematičce Sophie Germainové, která je využila při studiu částí Fermatovy věty a přispěla tak k teorii prvočísel.

Příklady

První některá prvočísla Sophie Germainové jsou:

  • 2 (protože 2·2+1 = 5 je prvočíslo)
  • 3 (2·3+1 = 7)
  • 5 (2·5+1 = 11)
  • 11 (2·11+1 = 23)
  • 23, 29, 41, 53, 83, ...

Vlastnosti

  • Pokud je p Sophie Germainovo prvočíslo, pak q = 2p+1 je bezpečné prvočíslo. Naopak ne každé bezpečné prvočíslo má formu 2p+1 s prvočíslem p (ale obvykle ano — definice obou pojmů je vzájemně úzce spjata).
  • Pro p > 2 je p liché a tedy i q liché. Mimo jednoduché výjimky platí, že obě čísla jsou poměrně vzácnější než obecná prvočísla, protože musí současně splňovat dvě podmínky prvočíselnosti.
  • Z hlediska analytické teorie čísel se očekává, že počet prvočísel Sophie Germainové menší než x roste asymptoticky podobně jako konstanty krát x/(ln x)^2; přesný odhad závisí na konjekturách typu Hardyho–Littlewood. Dosud ale nebylo prokázáno, zda jich existuje nekonečně mnoho.
  • Testování, zda je velké číslo Sophie Germainovým prvočíslem, se většinou provádí pomocí moderních algoritmů na testování prvočísel (např. Miller–Rabin, ECPP). Při hledání velmi velkých exemplářů se používají i speciální síta a distribuované výpočty.

Aplikace a význam

  • V kryptografii mají bezpečná prvočísla (tedy primy tvaru 2p+1 s prvočíslem p) význam při konstrukci skupin s velkým prvočíselným podílem. Například protokoly Diffie–Hellman a některé varianty DSA preferují moduly, jejichž modul je bezpečné prvočíslo, protože pak multiplicativní grupa má velkou podskupinu prvočíselného řádu.
  • Sophie Germainová použila související vlastnosti těchto prvočísel při částečných výsledcích k Fermatově větě; z toho důvodu nese toto pojmenování i historický význam v teorii čísel.

Otevřené otázky

  • Nejvýraznější otevřenou otázkou je, zda existuje nekonečně mnoho prvočísel Sophie Germainové. Většina odborníků tomu věří a heuristiky vycházející z konjektur Hardyho–Littlewood tomu nasvědčují, ale formální důkaz dosud neexistuje.
  • Dalšími aktivními oblastmi jsou efektivní algoritmy pro hledání velkých Sophie Germainových prvočísel a zkoumání jejich rozložení v aritmetických posloupnostech.

Existuje bohatá literatura a online databáze věnovaná tabulkám a rekordům těchto prvočísel; pro praktické hledání a ověřování se využívají kombinace sítí, heuristik a rychlých testů prvočíselnosti.