Генераторы

Целые числа Блюма

Если р и q - два простых числа, конгруэнтных 3 по модулю 4, то п = рд иногда называют целым числом Блюма. Если п - это целое число Блюма, у каждого квадратичного вычета ровно четыре квадратных корня, один из которых также является квадратом - это главный квадратный корень. Например, главный квадратный корень 139 mod 437 - это 24. Остальные три корня - это 185, 252 и 413.

Если р - простое число, и g меньше, чем р, то g называется генератором по модулю р, если для каждого числа Ъ от 1 тр - 1 существует некоторое число а, что g^a = Ъ (mod/;).

Иными словами, g является примитивом по отношению к р. Например, если р = И, то 2 - это генератор по модулю И:

2¹⁰ = 1024 = 1 (mod И)

2^!= 2 = 2 (mod И)

2⁸ = 256 = 3 (mod И)

2² = 4 = 4 (modll)

2⁴ = 16 = 5 (modll)

2⁹ = 512 = 6 (mod 11)
2⁷ = 128 =7 (mod 11)

2³ = 8 = 8 (modll)
2⁶ = 64 = 9 (modll)

2⁵ = 32 = 10 (mod 11)

Каждое число от 1 до 10 может быть представлено как 2 ^а (jaod p). Для р = 11 генераторами являются 2, 6, 7 и 8. Другие числа не являются генераторами. Например, генератором не является число 3, потому что не сущ е-ствует решения для

3^a = 2 (modll)

В общем случае проверить, является ли данное число генератором, нелегко. Однако задщача упрощается, е с-ли известно разложение на множители для р - 1. Пусть q_u q₂,..., q_n - это различные простые множители р - 1. Чтобы проверить, является ли число g генератором по модулю р, вычислите

gb-^lv*mod p

для всех значений q = q_u q₂,..., q„.

Если это число равно 1 для некоторого q, то g не является генератором. Если для всех значений q рассчитан­ное значение не равно 1, то g - это генератор.

Например, пусть р = И. Простые множители р - 1 = 10 - это 2 и 5. Для проверки того, является ли число 2 генератором, вычислим:

2⁽¹¹-^1)/5 (modll) = 4

2⁽¹¹-^1)/2 (modll) = 10

Ни один из ответов не равен 1, поэтому 2 - это генератор.

Проверим, является генератором ли число 3:

3⁽¹¹-^1)/5 (modll) = 9

3⁽¹¹-^1)/2 (modll) = l

Следовательно, 3 - это не генератор.

При необходимости обнаружить генератор по модулю р просто случайно выбирайте число от 1 до р - 1 и проверяйте, не является ли оно генератором. Генераторов достаточно, поэтому один из них вы, скорее всего, найдете быстро.

Вычисление в поле Галуа

Не тревожьтесь, все это мы уже делали. Если п - простое число или степень большого простого числа, то мы получаем то, что математики называют конечным полем. В честь этого мы используем р вместо п. В действи­тельности этот тип конечного поля настолько замечателен, что математики дали ему собственное имя - поле Галуа, обозначаемое как GF(p). (В честь Эвариста Галуа, французского математика, жившего в девятнадцатом веке и успевшего значительно продвинуть теорию чисел, прежде чем в 20 лет он был убит на дуэли.)

В поле Галуа определены сложение, вычитание, умножение и деление на ненулевые элементы. Существует нейтральный элемент для сложения - 0 - и для умножения - 1. Для каждого ненулевого числа существует еди н-ственное обратное число (это не было бы так, если бы р не было бы простым числом). Выполняются коммута­тивный, ассоциативный и дистрибутивный законы.

Арифметика поля Галуа широко используется в криптографии. В нем работает вся теория чисел, поле с о-держит числа только конечного размера, при делении отсутствуют ошибки округления. Многие криптосистемы основаны на GF(p), тер - это большое простое число.

Чтобы еще более усложнить вопрос, криптографы также используют арифметику по модулю неприводимых многочленов степени и, коэффициентами которых являются целые числа по модулю q, где q - это простое чис­ло. Эти поля называются GY(qn). Используется арифметика по модулю р(х), где р(х) - это неприводимый мно­гочлен степени п.

Математическая теория, стоящая за этим, выходит далеко за рамки этой книги, хотя я и опишу ряд крипт о-систем, использующих ее. Если вы хотите попробовать с неприводимыми многочленами, то GF(2 ³) включает следующие элементы: 0, 1, х, х + 1, х², х² + 1, х² + х, х² + х + 1. Удобный для параллельной реализации алгоритм вычисления обратных значений в GF(2") приведен в [421].

При обсуждении полиномов термин "простое число" заменяется термином " неприводимый многочлен". П о-лином называется неприводимым, если его нельзя представить в виде двух других полиномов (конечно же, кроме 1 и самого полинома). Полином х² + 1 неприводим над целыми числами, а полином х³ + 2 х² + х не явля­ется неприводимым, он может быть представлен как х(х + 1)(х + 1).

Полином, который в данном поле является генератором, называется примитивным или базовым, все его к о-эффициенты взаимно просты. Мы снова вернемся к примитивным полиномам, когда будем говорить о сдвиг о-вых регистрах с линейной обратной связью (см. раздел 16.2).

Вычисления в GF(2") могут быть быстро реализованы аппаратно с помощью сдвиговых регистров с лине й-ной обратной связью. По этой причине вычисления над GF(2") часто быстрее, чем вычисления над СЩр). Так как возведение в степень в GF(2") гораздо эффективнее, то эффективнее и вычисление дискретных логарифмов [180, 181, 368, 379]. Дополнительную информацию об этом можно найти в [140].

Для поля Галуа GF(2") криптографы любят использовать в качестве модулей трехчлены р{х) =х"+х+\, так как длинная строка нулей между коэффициентами при х^п и х позволяет просто реализовать быстрое умножение по модулю [183]. Полином должен быть примитивным, в противном случае математика не будет работать, х" + х + 1 примитивен для следующих значений п, меньших чем 1000 [1649, 1648]:

1, 3, 4, 6, 9, 15, 22, 28, 30, 46, 60, 63, 127, 153, 172, 303, 471, 532, 865, 900

Существуют аппаратные реализации GF(2¹²⁷), где р(х) = х¹²⁷ + х + 1 [1631, 1632, 1129]. Эффективная архи­тектура аппаратуры возведения в степень для GF(2") рассматривается в [147].

11.4 Разложение на множители

Разложить число на множители - значит найти его простые сомножители.

10 = 2*5

60 = 2*2*3*5

252601 = 41*61*101

2113- 1 =3391*23279*65993*1868569*1066818132868207

Разложение на множители является одной из древнейших проблем теории чисел. Этот процесс несложен, но требует времени. Это пока остается так, но ряд сдвигов в этом искусстве все же произошел. Сегодня самым лучшим алгоритмом является:

Решето числового поля чисел (Number field sieve, NFS) [953] (см. также [952, 16, 279]). Решето общего

числового поля - это самый быстрый из известных алгоритм для чисел размером 110 и более разрядов [472, 635]. В своем первоначальном виде он был непрактичен, но за последние несколько лет он был последовательно улучшен [953]. NFS все еще слишком нов, чтобы бить рекорды разложения на множители, но скоро все перем е-нится. Ранняя версия использовалась для разложения на множители девятого числа Ферма: 2512 + 1 [955,954].

Другие алгоритмы, вытесненные NFS:

Квадратичное решето (Quadratic sieve, QS) [1257, 1617, 1259]. Это самый быстрый из известных и чаще всего использовавшийся алгоритм для чисел, длина которых меньше 110 десятичных разрядов [440]. Более б ы-страя версия этого алгоритма называется множественным полиномиальным квадратичным решетом [1453, 302]. Самая быстрая версия называется двойной вариацией множественного полиномиального квадратичного решета с большим простым числом.

Метод эллиптической кривой (Elliptic curve method, ECM) [957, 1112, 1113]. Этот метод использовался для поиска не более, чем 43-разрядных множителей.

Алгоритм Монте-Карло Полларда (Pollard's Monte Carlo algorithm) [1254, 248]. (Этот алгоритм также приведен у Кнута в томе 2 [863].)

Алгоритм непрерывных дробей (Continued fraction algorithm). См. [1123, 1252, 863]. Этот алгоритм не подходит по времени выполнения.

Проверка делением (Trial division). Этот самый старый алгоритм разложения на множители состоит из проверки каждого простого числа, меньшего или равного ква дратному корню из раскладываемого числа.

В качестве хорошего введения в различные алгоритмы разложения на множители, кроме NFS, можно и с-пользовать [251]. NFS лучше всего рассмотрен в [953]. Более старыми рпаботами являются [505, 1602, 1258]. Сведения о параллельном разложении на множители можно найти в [250].

Если число п на множители раскладывается, то эвристическое время выполнения самых быстрых вариантов QS асимптотически равно:

_g(l + 0(l))(ln(n))^(ln((ln(n)))X

NFS намного быстрее, оценка его эвристического времени выполнения:

Дата добавления: 2014-11-29