"Человек - самое уязвимое место в системе безопасности.."
Главная » Защита информации - Разное » Проверка простых чисел

Проверка простых чисел

Общее

В данной статье вы увидите обзор известных алгоритмов проверки чисел на простоту. На сегодня не существует единого алгоритма для определения всех простых чисел. Все методы проверки делят на две группы: вероятностные проверки и детерминированные. Детерминированные методы определяют точно, является ли число простым. Вероятностные проверки определяют число на простоту с некой вероятностью ошибки. Многократное повторение для одного числа, но с разными переменными, разрешает сделать вероятность ошибки сколь угодно малой величины.

Быстрые тесты для малых чисел и вероятно простые числа

Малые простые числа

Пока не было нужды в генерации больших простых чисел, можно было реализовывать методы проверки без применения вычислительной техники. Первым из таких методов является полный перебор всех возможных делителей. Есть модификация, которая не хуже всего перебора, называется — пробное деление. Он заключается в делении на предыдущие простые числа либо равные корню из этого числа. Для такого метода можно использовать решето Эратосфена.

Малая теорема Ферма

Французский математик Пьер Ферма в 17 веке выдал закономерность, которая лежит в основе почти всех методов проверки на простоту.

Малая теорема Ферма — Если P простое и A — любое целое, то AP = A (mod P). Если P не делит А, то АP-1 = 1 (mod P). На основе такой теоремы, можно создать мощный алгоритм на простоту:

  • Тест Ферма: Для n > 1 выбираем a > и вычисляем An-1 mod n, если результат не 1, то n составное число, если 1, то n — слабо возможно простое по основанию a (a-PRP)

Часть чисел проходящие Тест Ферма являются составными, и их называют псевдопростыми.

Тест Рабина-Миллера

Можно улучшить тест Ферма, заметив, что если n — простое нечетное, то для 1 есть только два квадратных корня по модулю n: 1 и -1. По этому квадратный корень из An-1, A(n-1)/2 равен минус или плюс еденице. Если (n-1)/2 опять нечетно, то можно снова извлечь корень и тд. Первый вариант алгоритма определяет только одно деление:

  • Тест Леманна: Если для любого целого числа А меньшего n не выполняется условие A(n-1)/2 = ± 1 (mod n), то число n — составное. Если это условие выполнено, то число n — возможно простое с вероятностью ошибки не больше 50%.
  • Тест Рабина-Миллера: Запишем (n-1) в виде 2sd, где d нечетно, а s — неотрицательно: n называют сильно возможно простым по основанию A (A-SPRP), если реализуется одно из двух условий:
    • Ad = 1 (mod n)
    • (Ad)2r = -1 (mod n), для любого неотрицательного r < s

В 1980 году была доказана вероятность ошибки теста Рабина-Миллера не превышающая 1/4. Реализуя этот тест T раз для разных оснований, мы получим вероятность ошибки 2-2t

Объединение тестов

Классические тесты

Проверки чисел вида n + 1

Тест заключается в том, что мы должны знать частичное или полное разложение на множители числа n — 1. Разложение на множители n — 1 просто найти, если n имеет определенный вид.

  • Тест Лукаса: N ≥ 3. Если для каждого простого q, делящего n — 1 есть целое А такое что:
    • An-1 = 1 (mod n) и
    • A(n-1)/q ≠ 1 (mod n), то n — простое

Для такой проверки нужно знать полное разложение n — 1 на простые множители. Более мощная версия определяет знание не полного, а частичного разложения n — 1 на простые множители. Такой вариант алгоритма был выдан Поклингтоном в 1914 году.

  • Тест Поклингтона: N ≥ 3 и n = FR + 1 (F делит n-1), причем F > R, НОД (F,R) = 1 и известно разложение F на простые множители. Тогда, если для любого простого q, делящего F есть такое целое A > 1, что:
    • An-1 = 1 (mod n) и
    • НОД (A(n-1)/q — 1, n) = 1
  • Теорема Пепина: пусть Fn это n-е число Ферма и n > 1, тогда Fn — простое тогда и только тогда, когда 3(Fn — 1)/2 = 1 (mod Fn
  • Теорема Прота: Пусть n = h × 2k + 1, причем 2k > h. Если есть такое целое A, что A(n-1)/2 = -1 (mod n), то n — простое

На основе теоремы Прота было найдено пятое по величине из известных простых чисел — 28433 × 27830457

Проверки чисел вида n — 1

Здесь рассмотрим числа только определенного вида. 7 из первых 10 позиций по самым большим известным простым числам были найдены с помощью чисел Мерсенна. Числа Мерсенна называют числа вида 2s -1.

Лукасом и Лемером в 1930 году было создано следующее утверждение: пусть s — простое, тогда число Мерсенна n = 2s — 1 является простым тогда, когда S (n — 2) = 0, где S(0) = 4 и S(k+1) = S(k)2 — 2 (mod n). На основе такого факта можно создать проверку на простоту, которая точно скажет нам, является ли для заданного s число Мерсенна простым.

  • Тест Лукаса-Лемера:
    • С помощью пробного деления проверяем, является ли данное s простым, если нет, то получившееся число Мерсенна — составное
    • Задаем S(0) = 4
    • Для k от 1 до s — 2 вычисляем S(k) = S(k-1)2 — 2 (mod n)
    • Если в результате получился 0, то число Мерсенна простое

Неоклассические алгоритмы ARP и ARP-CL

Можно рассматривать числа в виде n2 + n + 1 или n2 — n + 1. А можно рассмотреть число вида nm — 1 для больших m. Тогда любое просто число q такое, что q — 1 делит m, по малой теореме Ферма будет делить nm — 1.

Было представлено, что всегда существует целое число m:

  • m < (log n)log log log n

Эллиптические кривые: ECPP

Современные вариант проверок на простоту основан на теореме Поклингтона, но для эллиптических кривых. Смысл алгоритма заключается в переходе от групп порядка n — 1 и n + 1 к достаточно большему диапазону размеров групп.

AKS

В 2002 году летом индийские математики Аграавал, Саксен и Кайал нашли полиномиальный детерминированный алгоритм проверки числа на простоту. Их метод основан на версии малой теоремы Ферма:

  • Теорема: Пусть A и P взаимно простые целые числа и P > 1. Число P является простым, когда (x — a)p = (xp — a) (mod p)
  • Доказательство: Если p — простое, то p делит биномиальные коэффициенты pCr для r = 1,2 ..p-1. Пусть p — составное, и пусть q — простой делитель p. Пусть qk максимальная степень q которая делит p. Тогда qk не делит pCr и взаимно просто с Ap-q. Отсюда, коэффициент перед xq в левой части требуемого равенства не равен нулю, а в правой равен. Алгоритм для числа n ≥ 23 (странное число получается из одного из требований для корректной работы алгоритма)
if (n is has the form ab with b > 1) then output COMPOSITE
r := 2
while (r < n) {
	if (gcd(n,r) is not 1) then output COMPOSITE
	if (r is prime greater than 2) then {
		let q be the largest factor of r-1
		if (q > 4sqrt(r)log n) and (n(r-1)/q is not 1 (mod r)) then
break
	}
	r := r+1
}
for a = 1 to 2sqrt(r)log n {
	if ( (x-a)n is not (xn-a) (mod xr-1,n) ) then output COMPOSITE
}
output PRIME;

Итоги

ТестТип тестаГде используется
Пробное делениедетерминированныйИз-за большой вычислительной сложности в чистом виде не используется. Пробное деление на маленькие простые числа реализуется во многих тестах как один из шагов
ФермавероятностныйВ чистом виде не реализуется. Может быть одним из первых шагов на проверку простоты для очень больших чисел
ЛеманнаверляьнлсьныйНе используется
Рабина-МиллеравероятностныйВ чистом виде может реализовываться в криптосистемах с открытым ключом для реализации простых ключей длиной 512, 1024 и 2048 бит.
МиллерадетерминированныйНа практике не используется, так как пока не доказана расширенная гипотеза Римана
ЛукасадетерминированныйДля получения больших простых чисел определенного вида
ПоклингтонадетерминированныйДля получения больших чисел с частично известной факторизацией n — 1
ПетинадетерминированныйДля получения больших простых чисел Ферма
ПротадетерминированныйДля получения больших простых чисел определенного вида
Лукаса-ЛемерадетерминированныйДля получения больших простых чисел Мерсенна
APRдетерминированныйВ качестве детерминированной быстрой проверки на простоту
ECPPдетерминированныйВ качестве детерминированной быстрой проверки на простоту
AKSдетерминированныйВ качестве детерминированной полиномиальной проверки на простоту

Из таблицы видно, что разные методы проверки на простоту служат для двух целей:

  • для получения очень больших целый чисел
  • для генерации простых чисел определенного размера для реализации в криптографии

Аналитическую работу провел студент (ГУ МФТИ) кафедры радиотехники Кучин Борис.