Введение
Простая пара (p, 2p+1)
In number theory, a prime number p is a Sophie Germain prime if 2p + 1 is also prime. The number 2p + 1 associated with a Sophie Germain prime is called a safe prime. For example, 11 is a Sophie Germain prime and 2 × 11 + 1 = 23 is its associated safe prime. Sophie Germain primes and safe primes have applications in public key cryptography and primality testing. It has been conjectured that there are infinitely many Sophie Germain primes, but this remains unproven. Sophie Germain primes are named after French mathematician Sophie Germain, who used them in her investigations of Fermat's Last Theorem. One attempt by Germain to prove Fermat’s Last Theorem was to let p be a prime number of the form 8k + 7 and to let n = p – 1. In this case, is unsolvable. Germain’s proof, however, remained unfinished. Through her attempts to solve Fermat's Last Theorem, Germain developed a result now known as Germain's Theorem which states that if p is an odd prime and 2p + 1 is also prime, then p must divide x, y, or z. Otherwise, This case where p does not divide x, y, or z is called the first case. Sophie Germain’s work was the most progress achieved on Fermat’s last theorem at that time. Value Number of digits Time of discovery Discoverer 2618163402417 × 21290000 − 1 388342 February 2016 Dr. James Scott Brown in a distributed PrimeGrid search using the programs TwinGen and LLR 18543637900515 × 2666667 − 1 200701 April 2012 Philipp Bliedung in a distributed PrimeGrid search using the programs TwinGen and LLR183027 × 2265440 − 1 79911 March 2010 Tom Wu using LLR648621027630345 × 2253824 − 1 and 620366307356565 × 2253824 − 1 76424 November 2009 Zoltán Járai, Gábor Farkas, Tímea Csajbók, János Kasza and Antal Járai1068669447 × 2211088 − 1 63553 May 2020 Michael Kwok99064503957 × 2200008 − 1 60220 April 2016 S. Urushihata607095 × 2176311 − 1 53081 September 2009 Tom Wu48047305725 × 2172403 − 1 51910 January 2007 David Underbakke using TwinGen and LLR137211941292195 × 2171960 − 1 51780 May 2006 Járai et al. On 2 Dec 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, and Paul Zimmermann announced the computation of a discrete logarithm modulo the 240 digit (795 bit) prime RSA 240 + 49204 (the first safe prime above RSA 240) using a number field sieve algorithm; see Discrete logarithm records.
В теории чисел простое число p называется простым числом Софи Жермен, если 2p + 1 также является простым числом. Число 2p + 1, связанное с простым числом Софи Жермен, называется безопасным простым числом. Например, 11 является простым числом Софи Жермен, а 2 × 11 + 1 = 23 – его соответствующее безопасное простое число. Простые числа Софи Жермен и безопасные простые числа находят применение в криптографии с открытым ключом и проверке простоты. Предполагается, что существует бесконечно много простых чисел Софи Жермен, но это до сих пор не доказано. Простые числа Софи Жермен названы в честь французской математика Софи Жермен, которая использовала их в своих исследованиях последней теоремы Ферма. Одна из попыток Жермен доказать последнюю теорему Ферма заключалась в том, чтобы взять p – простое число вида 8k + 7 и n = p – 1. В этом случае, уравнение не имеет решений. Однако доказательство Жермен осталось незавершенным. В своих попытках решить последнюю теорему Ферма Жермен разработала результат, известный как теорема Жермен, которая утверждает, что если p – нечетное простое число и 2p + 1 также простое, то p должно делить x, y или z. В противном случае, этот случай, когда p не делит x, y или z, называется первым случаем. Работа Софи Жермен была самым значительным прогрессом в доказательстве последней теоремы Ферма на тот момент. 2 декабря 2019 года Фабрис Будо, Пьеррик Годри, Орор Гильевик, Надя Хенингер, Эммануэль Томе и Поль Циммерман объявили о вычислении дискретного логарифма по модулю 240-значного (795-битного) простого числа RSA 240 + 49204 (первого безопасного простого числа, большего RSA 240) с использованием алгоритма решета числового поля; см. записи дискретных логарифмов.
In number theory, a prime number p is a Sophie Germain prime if 2p + 1 is also prime. The number 2p + 1 associated with a Sophie Germain prime is called a safe prime. For example, 11 is a Sophie Germain prime and 2 × 11 + 1 = 23 is its associated safe prime. Sophie Germain primes and safe primes have applications in public key cryptography and primality testing. It has been conjectured that there are infinitely many Sophie Germain primes, but this remains unproven. Sophie Germain primes are named after French mathematician Sophie Germain, who used them in her investigations of Fermat's Last Theorem. One attempt by Germain to prove Fermat’s Last Theorem was to let p be a prime number of the form 8k + 7 and to let n = p – 1. In this case, is unsolvable. Germain’s proof, however, remained unfinished. Through her attempts to solve Fermat's Last Theorem, Germain developed a result now known as Germain's Theorem which states that if p is an odd prime and 2p + 1 is also prime, then p must divide x, y, or z. Otherwise, This case where p does not divide x, y, or z is called the first case. Sophie Germain’s work was the most progress achieved on Fermat’s last theorem at that time. Value Number of digits Time of discovery Discoverer 2618163402417 × 21290000 − 1 388342 February 2016 Dr. James Scott Brown in a distributed PrimeGrid search using the programs TwinGen and LLR 18543637900515 × 2666667 − 1 200701 April 2012 Philipp Bliedung in a distributed PrimeGrid search using the programs TwinGen and LLR183027 × 2265440 − 1 79911 March 2010 Tom Wu using LLR648621027630345 × 2253824 − 1 and 620366307356565 × 2253824 − 1 76424 November 2009 Zoltán Járai, Gábor Farkas, Tímea Csajbók, János Kasza and Antal Járai1068669447 × 2211088 − 1 63553 May 2020 Michael Kwok99064503957 × 2200008 − 1 60220 April 2016 S. Urushihata607095 × 2176311 − 1 53081 September 2009 Tom Wu48047305725 × 2172403 − 1 51910 January 2007 David Underbakke using TwinGen and LLR137211941292195 × 2171960 − 1 51780 May 2006 Járai et al. On 2 Dec 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, and Paul Zimmermann announced the computation of a discrete logarithm modulo the 240 digit (795 bit) prime RSA 240 + 49204 (the first safe prime above RSA 240) using a number field sieve algorithm; see Discrete logarithm records.
Значение Количество цифр Время открытия Открыватель 2618163402417 × 21290000 − 1 388342 Февраль 2016 Д-р Джеймс Скотт Браун в распределенном поиске PrimeGrid с использованием программ TwinGen и LLR 18543637900515 × 2666667 − 1 200701 Апрель 2012 Филипп Блиедунг в распределенном поиске PrimeGrid с использованием программ TwinGen и LLR 183027 × 2265440 − 1 79911 Март 2010 Том Ву с использованием LLR 648621027630345 × 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 Яраи и др.
In number theory, a prime number p is a Sophie Germain prime if 2p + 1 is also prime. The number 2p + 1 associated with a Sophie Germain prime is called a safe prime. For example, 11 is a Sophie Germain prime and 2 × 11 + 1 = 23 is its associated safe prime. Sophie Germain primes and safe primes have applications in public key cryptography and primality testing. It has been conjectured that there are infinitely many Sophie Germain primes, but this remains unproven. Sophie Germain primes are named after French mathematician Sophie Germain, who used them in her investigations of Fermat's Last Theorem. One attempt by Germain to prove Fermat’s Last Theorem was to let p be a prime number of the form 8k + 7 and to let n = p – 1. In this case, is unsolvable. Germain’s proof, however, remained unfinished. Through her attempts to solve Fermat's Last Theorem, Germain developed a result now known as Germain's Theorem which states that if p is an odd prime and 2p + 1 is also prime, then p must divide x, y, or z. Otherwise, This case where p does not divide x, y, or z is called the first case. Sophie Germain’s work was the most progress achieved on Fermat’s last theorem at that time. Value Number of digits Time of discovery Discoverer 2618163402417 × 21290000 − 1 388342 February 2016 Dr. James Scott Brown in a distributed PrimeGrid search using the programs TwinGen and LLR 18543637900515 × 2666667 − 1 200701 April 2012 Philipp Bliedung in a distributed PrimeGrid search using the programs TwinGen and LLR183027 × 2265440 − 1 79911 March 2010 Tom Wu using LLR648621027630345 × 2253824 − 1 and 620366307356565 × 2253824 − 1 76424 November 2009 Zoltán Járai, Gábor Farkas, Tímea Csajbók, János Kasza and Antal Járai1068669447 × 2211088 − 1 63553 May 2020 Michael Kwok99064503957 × 2200008 − 1 60220 April 2016 S. Urushihata607095 × 2176311 − 1 53081 September 2009 Tom Wu48047305725 × 2172403 − 1 51910 January 2007 David Underbakke using TwinGen and LLR137211941292195 × 2171960 − 1 51780 May 2006 Járai et al. On 2 Dec 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, and Paul Zimmermann announced the computation of a discrete logarithm modulo the 240 digit (795 bit) prime RSA 240 + 49204 (the first safe prime above RSA 240) using a number field sieve algorithm; see Discrete logarithm records.
Свойства
Для безопасных простых чисел не существует специального теста на простоту, как для чисел Ферма и Мерсенна. Однако критерий Поклинтона можно использовать для доказательства простоты числа 2p + 1, если уже доказана простота p.
Подобно тому, как каждый член, кроме последнего, в цепи Каннингема первого рода является простым числом Софи Жермен, каждый член, кроме первого, в такой цепи является безопасным простым числом. Безопасные простые числа, оканчивающиеся на 7, то есть имеющие вид 10n + 7, являются последними членами в таких цепях, когда они встречаются, поскольку 2(10n + 7) + 1 = 20n + 15 делится на 5.
Сильные простые числа
Простое число q называется сильным простым, если q + 1 и q − 1 оба имеют хотя бы один большой (порядка 500 цифр) простой делитель. Для безопасного простого числа 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 Полларда. Однако, с учетом современных технологий факторизации, преимущество использования безопасных и сильных простых чисел представляется незначительным. Аналогичные проблемы возникают и в других криптосистемах, включая обмен ключами Диффи — Хеллмана и подобные системы, которые зависят от безопасности задачи о дискретном логарифме, а не от факторизации целых чисел. По этой причине протоколы генерации ключей для этих методов часто полагаются на эффективные алгоритмы для генерации сильных простых чисел, которые, в свою очередь, опираются на предположение о том, что эти простые числа имеют достаточно высокую плотность. В режиме Софи Жермен было предложено использовать арифметику в конечном поле порядка, равного безопасному простому числу 2128 + 12451, для противодействия слабостям в режиме Галуа/Счетчик при использовании бинарного конечного поля GF(2128). Однако было показано, что 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) без каких-либо гипотез или использования простых чисел Софи Жермен.
Генерация псевдослучайных чисел
Безопасные простые числа, удовлетворяющие определенным соотношениям сравнения, могут быть использованы для генерации псевдослучайных чисел, применимых в моделировании методом Монте-Карло. Аналогично, простые числа Софи Жермен могут быть использованы при генерации псевдослучайных чисел. Десятичное разложение 1/q создаст поток из q − 1 псевдослучайных цифр, если q является безопасным простым числом, соответствующим простому числу Софи Жермен p, при этом p сравнимо с 3, 9 или 11 по модулю 20. Таким образом, "подходящими" простыми числами 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. Следует отметить, что эти цифры не подходят для криптографических целей, поскольку значение каждой цифры может быть выведено из ее предшественницы в потоке цифр.
В популярной культуре
Простые числа Софи Жермен упоминаются в пьесе "Доказательство" и основанном на ней фильме.