Числа Софи Жермен

---

Простое число Софи́ Жерме́н — такое простое число ${\displaystyle p}$, что число ${\displaystyle 2p+1}$ также простое. Число ${\displaystyle 2p+1}$, связанное с простым числом Софи Жермен, называется безопасным простым числом. Например, 11 — это простое число Софи Жермен, а 2 × 11 + 1 = 23 — связанное с ним безопасное простое число.

Как и для простых чисел-близнецов, предполагается, что количество простых Софи Жермен бесконечно, но это открытый вопрос теории чисел.

Названы по имени Софи Жермен, которая доказала Великую теорему Ферма для показателей, являющихся простыми этого вида — только в этом случае показатель не делит ни одну из переменных основного уравнения Великой теоремы Ферма.

В криптографии требуются гораздо большие простые числа Софи Жермен, такие как 1 846 389 521 368 + 11⁶⁰⁰.

На 2016 год рекордом является число 2 618 163 402 417·2^1 290 000 − 1 длиной 388 342 десятичные цифры. Его обнаружил Джеймс Скотт Браун, профессор Университета Майами, участник сообщества PrimeGrid. PrimeGrid с 2009 года ведет активный поиск таких простых чисел в одном из своих подпроектов. Но, хотя найденные ими новые простые числа вида k·2^1 290 000 − 1 и анонсируются практически ежедневно, нахождение парного простого числа (k·2^1 290 001 − 1), необходимого для установления нового рекорда, занимает годы.

2 декабря 2019 года Фабрис Будо, Пьеррик Годри, Аврора Гильевич, Надя Хенингер, Эммануэль Томе и Пол Циммерманн объявили о вычислении дискретного логарифма по модулю 240 (795-битного) простого числа RSA-240 + 49204 (первое безопасное простое число больше RSA-240) с использованием алгоритма решета числового поля.

---