Кіріспе
Бастапқы жұп (p, 2p+1)
Сандар теориясында, егер 2p + 1 де жай сан болса, p жай саны Софи Жермен жай саны болып табылады. Софи Жермен жай санымен байланысты 2p + 1 саны қауіпті жай сан деп аталады. Мысалы, 11 – Софи Жермен жай саны, ал 2 × 11 + 1 = 23 – оның қауіпті жай саны. Софи Жермен жай саны мен қауіпті жай сан ашық кілттің криптографиясында және жайлықты тексеруде қолданылады. Софи Жермен жай сандарының саны шексіз көп деген болжам бар, бірақ бұл әлі дәлелденбеген. Софи Жермен жай сандары француз математигі Софи Жерменнің құрметіне аталған, ол оларды Ферманың соңғы теоремасын зерттеуде қолданған. Жерменнің Ферманың соңғы теоремасын дәлелдеуге жасаған әрекеттерінің бірі – p санын 8k + 7 түріндегі жай сан деп алып, n = p – 1 деп қою болды. Бұл жағдайда, шешімі жоқ. Дегенмен, Жерменнің дәлелі толыққанды болған жоқ. Ферманың соңғы теоремасын шешуге жасаған тырастықтары арқылы Жермен қазір Жермен теоремасы деп аталатын нәтижені жасады, онда егер p тақ жай сан болса және 2p + 1 де жай сан болса, онда p, x, y немесе z-ді бөлуі керек. Әйтпесе, p, x, y немесе z-ді бөлмейтін жағдай бірінші жағдай деп аталады. Софи Жерменнің жұмысы сол кезде Ферманың соңғы теоремасы бойынша ең көп прогреске қол жеткізгені болып табылды. Мән Сандар саны Табылған уақыты Ашқан 2618163402417 × 21290000 − 1 388342 2016 жылғы ақпан Доктор Джеймс Скотт Браун TwinGen және LLR бағдарламаларын пайдалана отырып, PrimeGrid-те таратылған іздеуде 18543637900515 × 2666667 200701 2012 жылғы сәуір Филипп Блидунг TwinGen және LLR183027 × 2265440 бағдарламаларын пайдалана отырып, PrimeGrid-те таратылған іздеуде 79911 2010 жылғы наурыз Том Ву LLR648621027630345 × 2253824 − 1 және 620366307356565 × 2253824 − 1 76424 2009 жылғы қараша Зольтан Яраи, Габор Фаркас, Тимеа Чайбок, Янош Каса және Анталь Яраи 1068669447 × 2211088 − 1 63553 2020 жылғы мамыр Майкл Куок 99064503957 × 2200008 − 1 60220 2016 жылғы сәуір С. Урушихата 607095 × 2176311 − 1 53081 2009 жылғы қыркүйек Том Ву 48047305725 × 2172403 − 1 51910 2007 жылғы қаңтар Дэвид Андербакке TwinGen және LLR 137211941292195 × 2171960 − 1 51780 2006 жылғы мамыр Яраи және т.б. 2 желтоқсан 2019 ж. Фабрис Будот, Пьеррик Гаудри, Авроре Гильевич, Надя Хенингер, Эммануэль Томе және Пол Циммерман сандық өріс сүзгісі алгоритмін қолдана отырып, 240 таңбалы (795 бит) жай сан RSA 240 + 49204 (RSA 240-тан жоғары бірінші қауіпті жай сан) модулі бойынша дискретті логарифмді есептегенін жариялады; Дискретті логарифм жазбаларын қараңыз.
Қасиеттері
Ферма және Мерсен алғашқы сандары үшіндей, қауіпсіз алғашқы сандар үшін арнайы алғашқылық тесті жоқ. Дегенмен, егер p алғашқы сан екені дәлелденген болса, Поклингтон критерийі 2p + 1 алғашқы екенін дәлелдеуге қолданылуы мүмкін. Бірінші типтегі Каннингем тізбегіндегі соңғы мүшеден басқа барлық мүшелер Софи Жермен алғашқы саны болғандай, осындай тізбектегі алғашқы мүшеден басқа барлық мүшелер қауіпсіз алғашқы сан болып табылады. 7-ге аяқталатын қауіпсіз алғашқы сандар, яғни 10n + 7 түріндегі сандар, егер олар кездессе, мұндай тізбектерде соңғы мүшелер болып табылады, себебі 2(10n + 7) + 1 = 20n + 15 саны 5-ке бөлінеді.
Just as every term except the last one of a Cunningham chain of the first kind is a Sophie Germain prime, so every term except the first of such a chain is a safe prime. Safe primes ending in 7, that is, of the form 10n + 7, are the last terms in such chains when they occur, since 2(10n + 7) + 1 = 20n + 15 is divisible by 5.
Қатты жай сандар
Егер q + 1 және q - 1 екеуінде де үлкен (шамамен 500 цифр) жай факторлар болса, онда q – күшті жай сан болады. Қауіпті жай сан үшін, q = 2p + 1, q − 1 санының үлкен жай коэффициенті болады, атап айтқанда p, сондықтан қауіпті жай сан q, күшті жай сан болу шарттарының бір бөлігін орындайды. Бір санды, q жай сан ретінде көбейткіштерге жіктеудің кейбір әдістерінің жұмыс уақыты, q - 1 жай факторларының мөлшеріне байланысты. Бұл, мысалы, p − 1 әдісі үшін де дұрыс.
Криптография
Қауіпсіз алғашқы сандар криптографияда да маңызды, өйткені олар Диффи–Хеллман кілт алмасуы сияқты дискретті логарифмге негізделген техникаларда қолданылады. Егер 2p + 1 қауіпсіз алғашқы сан болса, 2p + 1 модульдік бүтін сандардың көбейту тобы үлкен алғашқы реттік кіші топқа ие болады. Әдетте осы алғашқы реттік кіші топ қажет, ал қауіпсіз алғашқы сандарды пайдаланудың себебі – модульдің p-ге қатысты мүмкіндігінше кіші болуы. p = 2q + 1 саны, егер q алғашқы сан болса, қауіпсіз алғашқы сан деп аталады. Осылайша, p = 2q + 1 тек қана q Софи Жермен алғашқы саны болған жағдайда ғана қауіпсіз алғашқы сан болып табылады, сондықтан қауіпсіз алғашқы сандарды табу және Софи Жермен алғашқы сандарын табу есептеу қиындығы тұрғысынан тең. Қауіпсіз алғашқы сан туралы түсінік күшті алғашқы санға дейін күшейтілуі мүмкін, онда p − 1 және p + 1 екеуінің де үлкен алғашқы көбейткіштері бар. Қауіпсіз және күшті алғашқы сандар RSA криптожүйесіндегі құпия кілттердің көбейткіштері ретінде пайдалы болды, өйткені олар жүйені кейбір көбейткіш табу алгоритмдерімен, мысалы, Поллардтың p − 1 алгоритмімен бұзуға жол бермейді. Алайда, қазіргі көбейткіш табу технологиясымен қауіпсіз және күшті алғашқы сандарды пайдаланудың артықшылығы мардымсыз болып көрінеді. Осыған ұқсас мәселелер басқа криптожүйелерде де қолданылады, соның ішінде Диффи–Хеллман кілт алмасуы және дискретті логарифм мәселесінің қауіпсіздігіне, бүтін сандарды көбейткіш табуға қарағанда көбірек тәуелділікте болатын ұқсас жүйелерде. Осы себепті, осы әдістердің кілт жасау протоколдары көбінесе күшті алғашқы сандарды жасау үшін тиімді алгоритмдерге сүйенеді, олар өз кезегінде осы алғашқы сандардың жеткілікті жоғары тығыздыққа ие деген болжамға сүйенеді. Софи Жерменнің санау режимінде, GF(2128) бинарлық шекті өрісін пайдалана отырып, Галуа/санау режиміндегі әлсіздіктерді жою үшін 2128 + 12451 қауіпсіз алғашқы санына тең реттік шекті өрісте арифметиканы пайдалану ұсынылды. Алайда, SGCM GCM сияқты көптеген криптографиялық шабуылдарға осал екені дәлелденді.
A prime number p = 2q + 1 is called a safe prime if q is prime. Thus, p = 2q + 1 is a safe prime if and only if q is a Sophie Germain prime, so finding safe primes and finding Sophie Germain primes are equivalent in computational difficulty. The notion of a safe prime can be strengthened to a strong prime, for which both p − 1 and p + 1 have large prime factors. Safe and strong primes were useful as the factors of secret keys in the RSA cryptosystem, because they prevent the system being broken by some factorization algorithms such as Pollard's p − 1 algorithm. However, with the current factorization technology, the advantage of using safe and strong primes appears to be negligible. Similar issues apply in other cryptosystems as well, including Diffie–Hellman key exchange and similar systems that depend on the security of the discrete logarithm problem rather than on integer factorization. For this reason, key generation protocols for these methods often rely on efficient algorithms for generating strong primes, which in turn rely on the conjecture that these primes have a sufficiently high density. In Sophie Germain Counter Mode, it was proposed to use the arithmetic in the finite field of order equal to the safe prime 2128 + 12451, to counter weaknesses in Galois/Counter Mode using the binary finite field GF(2128). However, SGCM has been shown to be vulnerable to many of the same cryptographic attacks as GCM.
Бастылық сынағы
AKS алғашқылық сынағының алғашқы нұсқасында Софи Жермен алғашқы сандары туралы болжам нашар жағдай күрделілігін O(log¹²n) -ден O(log⁶n) -ге дейін төмендету үшін қолданылады. Қағаздың кейінгі нұсқасы O(log⁷.⁵n) уақыт күрделілігіне ие екені көрсетілді, оны да болжамды пайдалану арқылы O(log⁶n) уақыт күрделілігіне дейін төмендетуге болады. Кейінгі AKS нұсқаларының күрделілігі O(log⁶n) екені дәлелденді, бұл ретте ешқандай болжамдарға немесе Софи Жермен алғашқы сандарына тәуелді емес.
Псевдослучайный сандар генерациясы
Белгілі бір конгруэнцияларды қанағаттандыратын қауіпсіз жай сандар Монте-Карло симуляциясында қолданылатын псевдо-кездейсоқ сандарды жасау үшін қолданылуы мүмкін. Сол сияқты, Софи Жермен жай сандары да псевдо-кездейсоқ сандарды құруда пайдаланылуы мүмкін. Егер q – Софи Жерменнің p жай санының қауіпсіз түрі болса және p саны 20 модулі бойынша 3, 9 немесе 11-ге конгруэнтті болса, онда 1/q-ның ондық кеңейуі q – 1 псевдо-кездейсоқ цифрлар ағынын тудырады. Осылайша, "қолайлы" жай сандар q – 7, 23, 47, 59, 167, 179 және т.б. (p = 3, 11, 23, 29, 83, 89 және т.б. сәйкес келеді). Нәтижесінде, ұзындығы q – 1 цифрдан (бастапқы нөлдерді қоса алғанда) тұратын ағын пайда болады. Мысалы, q = 23 қолданғанда 0, 4, 3, 4, 7, 8, 2, 6, 0, 8, 6, 9, 5, 6, 5, 2, 1, 7, 3, 9, 1, 3 псевдо-кездейсоқ цифрлары туындайды. Бұл цифрлардың криптографиялық мақсаттар үшін қолдануға болмайтынын ескеріңіз, себебі цифрлар ағынындағы әрбір цифрдың мәні оның алдыңғысынан есептеледі.
Танымал мәдениетте
Софи Жермен сандары "Доказательство" пьесасында және одан кейінгі фильмде кездеседі.