Числа Софи Жермен
Эту страницу предлагается объединить со страницей Безопасное простое число. |
Простое число Софи́ Жерме́н — такое простое число , что число также простое. Число , связанное с простым числом Софи Жермен, называется безопасным простым числом. Например, 11 — это простое число Софи Жермен, а 2 × 11 + 1 = 23 — связанное с ним безопасное простое число.
Как и для простых чисел-близнецов, предполагается, что количество простых Софи Жермен бесконечно, но это открытый вопрос теории чисел.
Названы по имени Софи Жермен, которая доказала Великую теорему Ферма для показателей, являющихся простыми этого вида — только в этом случае показатель не делит ни одну из переменных основного уравнения Великой теоремы Ферма.
Первые несколько простых чисел Софи Жермен (меньше 1000) равны:
- 2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179, 191, 233, 239, 251, 281, 293, 359, 419, 431, 443, 491, 509, 593, 641, 653, 659, 683, 719, 743, 761, 809, 911, 953, ... (последовательность A005384)
Следовательно, первые несколько безопасных простых чисел равны:
- 5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619, 1823, 1907, ... (последовательность A005385)
В криптографии требуются гораздо большие простые числа Софи Жермен, такие как 1 846 389 521 368 + 11600.
Наибольшее известное простое число Софи Жермен:
На 2016 год рекордом является число 2 618 163 402 417·21 290 000 − 1 длиной 388 342 десятичные цифры. Его обнаружил Джеймс Скотт Браун, профессор Университета Майами, участник сообщества PrimeGrid. PrimeGrid с 2009 года ведет активный поиск таких простых чисел в одном из своих подпроектов. Но, хотя найден��ые ими новые простые числа вида k·21 290 000 − 1 и анонсируются практически ежедневно, нахождение парного простого числа (k·21 290 001 − 1), необходимого для установления нового рекорда, занимает годы.
| Значение | Число цифр | Время открытия | Исследователь |
|---|---|---|---|
| 2618163402417 × 21290000 − 1 | 388342 | Февраль 2016 | Джеймс Скотт Браун в PrimeGrid используя программу TwinGen и LLR[1] |
| 18543637900515 × 2666667 − 1 | 200701 | Апрель 2012 | Philipp Bliedung в PrimeGrid используя программу TwinGen и LLR[2] |
| 183027 × 2265440 − 1 | 79911 | Март 2010 | Tom Wu используя LLR[3] |
| 648621027630345 × 2253824 − 1 и 620366307356565 × 2253824 − 1 | 76424 | Ноябрь 2009 | Zoltán Járai, Gábor Farkas, Tímea Csajbók, János Kasza и Antal Járai[4][5] |
| 1068669447 × 2211088 − 1 | 63553 | Май 2020 | Michael Kwok[6] |
| 99064503957 × 2200008 − 1 | 60220 | Апрель 2016 | S. Urushihata[7] |
| 607095 × 2176311 − 1 | 53081 | Сентябрь 2009 | Tom Wu[8] |
| 48047305725 × 2172403 − 1 | 51910 | Январь 2007 | David Underbakke используя TwinGen и LLR[9] |
| 137211941292195 × 2171960 − 1 | 51780 | Май 2006 | Járai и др.[10] |
2 декабря 2019 года Фабрис Будо, Пьеррик Годри, Аврора Гильевич, Надя Хенингер, Эммануэль Томе и Пол Циммерманн объявили о вычислении дискретного логарифма по модулю 240 (795-битного) простого числа RSA-240 + 49204 (первое безопасное простое число больше RSA-240) с использованием алгоритма решета числового поля.
Примечания
править- ↑ PrimeGrid's Sophie Germain Prime Search. PrimeGrid. Дата обращения: 29 февраля 2016. Архивировано 9 октября 2022 года.
- ↑ PrimeGrid's Sophie Germain Prime Search. PrimeGrid. Дата обращения: 18 апреля 2012. Архивировано 9 октября 2022 года.
- ↑ The Prime Database: 183027*2^265440-1 Архивная копия от 21 июня 2018 на Wayback Machine. From The Prime Pages.
- ↑ The Prime Database: 648621027630345*2^253824-1 Архивная копия от 26 ноября 2022 на Wayback Machine.
- ↑ The Prime Database: 620366307356565*2^253824-1. Дата обращения: 17 июля 2023. Архивировано 26 ноября 2022 года.
- ↑ The Prime Database: 1068669447*2^211088-1 Архивная копия от 27 ноября 2022 на Wayback Machine From The Prime Pages.
- ↑ The Prime Database: 99064503957*2^200008-1 Архивная копия от 26 ноября 2022 на Wayback Machine From The Prime Pages.
- ↑ The Prime Database: 607095*2^176311-1 Архивная копия от 3 октября 2022 на Wayback Machine.
- ↑ The Prime Database: 48047305725*2^172403-1 Архивная копия от 2 октября 2022 на Wayback Machine.
- ↑ The Prime Database: 137211941292195*2^171960-1 Архивная копия от 5 октября 2022 на Wayback Machine.
Ссылки
править- (SGS) Sophie Germain Prime Search — PrimeGrid.
- The Top Twenty Sophie Germain Primes — Prime Pages[англ.].
- Список простых чисел Софи Жермен — последовательность A005384 в OEIS