И снова о простых числах Софи Жермен

Более простой способ проверки простых чисел Софи Жермен на простоту

Год назад я писал о генерации простых чисел Софи Жермен.

Вкратце напомню: p — простое число Софи Жермен, если q = 2p+1, тоже простое число. Простые числа Софи Жермен применяются в криптографии (в частности, в протоколе обмена ключами Диффи–Хеллмана–Меркле).

Ранее я использовал вероятностный метод Рабина–Миллера для проверки обоих чисел (p и q) на простоту. Вероятностная проверка (вкупе с другими тестами, например, решетом Эратосфена и теста на псевдопростоту, основанного на малой теореме Ферма) — не самый быстрый (и не всегда точный) метод.

Как оказалось, есть более простая и эффективная проверка, которую открыл Генри Лифшиц (Henry Lifchitz).

Суть проверки сводится к тому, что если p≥5 является простым числом, то q=2p+1 является простым числом тогда и только тогда, когда q является делителем числа 3^p-1.

Среди преимуществ такого подхода метода можно отметить его простоту. Среди недостатков — при реализации алгоритма с помощью GMP сразу сталкиваешься с тем, что в библиотеке нет функции mpz_pow(res, x, y), такой, чтобы аргументы x и y имели тип mpz_t. Судя по всему, и не будет. В принципе, логично: возведение тройки в степень числа с 4096 разрядами съело больше 4 ГиБ памяти и я снял задачу прежде, чем OOM Killer убил какой-нибудь процесс.

Кому интересно поэкспериментировать, привожу программу, находящую простые числа Софи Жермен до 1,000,000:

Для вычисления степени приведён (но реально не используется) алгоритм addition-chain exponentiation.

Это было решение в лоб, и оно не очень (или очень не) красиво. Если же вспомнить математику, то всё становится гораздо проще. Математику уже затем учить следует, что она ум в порядок приводит (М.В. Ломоносов).

Ведь на самом деле,

(a + b) mod c = a mod c + b mod c

Из этого следует, что

(3^p-1) mod (2p+1) = 3^p mod (2p+1) - 1 mod (2p+1)

Иными словами, если выполняется равенство

3^p mod (2p+1) = 1,

то p — простое число Софи Жермен.

Что это даёт: мы можем использовать оптимизированный алгоритм для вычисления a^b mod c.

В результате получим очень простую программу:

Такие вот пироги
А выигрыш в производительности очень заметен на действительно больших числах.