§ 3.6. Алгоритмы решета числового поля

Отметим, что на практике алгоритм Шнорра—Ленстры никогда активно не использовался. Алгоритм Ленстры для факторизации с помощью эллиптических кривых (о котором см. 4) имеет ту же оценку сложности и так же требует немного памяти, но групповые операции на кривой выполняются значительно быстрее, чем операции в группе классов квадратичных форм. Поэтому алгоритм Ленстры считается значительно более эффективным и активно используется на практике.

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

Заметим, что алгоритм Ленстры—Померанса, как и алгоритм Шнорра—Ленстры, никогда активно не использовался на практике.

§ 3.6. Алгоритмы решета числового поля

Алгоритм решета числового поля для факторизации целых чисел специального вида (special number field sieve, или SNFS) был впервые предложен в 1990 г. в работе [161]. С его помощью было разложено на множители число Ферма F9 = 2512 + 1, записываемое 155 десятичными знаками (см. об этом [162]). Эвристическая оценка сложности составляет Ln [1/3; c] арифметических операций при c = (32/9)1/3 = 1,5263. . . Числа n, к которым применяется SNFS, имеют вид n = re − s, где r N, s Z, r и |s| невелики.

Впоследствии метод был обобщен и применен для факторизации произвольных целых чисел. Он получил название general number field sieve или, сокращенно, GNFS. Оценка сложности также составляет Ln [1/3; c] при некоторой постоянной c.

В настоящее время рекордным значением для натуральных чисел, разложенных с помощью SNFS, является число специального вида,

94 Гл. 3. Факторизация целых чисел с субэкспоненциальной сложностью

записываемое 227 десятичными знаками, см. [265]. Для RSA-чисел n, не имеющих специального вида, рекордные разложения были найдены

в1999 г.: сначала было разложено 140-значное RSA-число (см. [87]),

а затем 155-значное RSA-число (512 битов), см. [88]. На факторизацию этого последнего числа потребовалось около 8400 mips-year1.

Метод решета числового поля и его усовершенствования описаны

вряде работ, см. [107; 110; 111; 112; 159; 162; 163; 203; 204; 205; 226; 227; 290]. В настоящее время, согласно [74], это самый эффективный метод факторизации для чисел n > 10110 (сравнение NFS с методом квадратичного решета см. в конце § 3.4); см. об этом также обзоры [211] и [209].

Фактически решето числового поля не является алгоритмом. Это метод вычисления, состоящий из нескольких этапов, и каждый из этих этапов обслуживается несколькими алгоритмами. Подробное описание SNFS и GNFS выходит далеко за рамки данной книги. Для того, чтобы читатель получил представление о методе решета числового поля и об используемым этим методом средствах, мы схематически опишем факторизацию числа Ферма F9, следуя работе [162].

Далее в этом параграфе мы предполагаем, что читатель знаком с основами алгебраической теории чисел в объеме, например, книги [263].

Обозначим N = F9 = 2512 + 1. Еще в 1903 г. был найден простой делитель p7 = 2424833. Мы обозначим n = N/p7. Это число было далее разложено с помощью SNFS на два сомножителя: n = p49 · p99. Для этого потребовалось около 700 рабочих станций и один суперкомпьютер для решения системы линейных уравнений; работа заняла несколько месяцев. Предполагалось предварительно (хотя это и не проверялось), что n не есть степень простого числа; это допущение в конечном счете оказалось верным.

Схема метода SNFS для n.

1 этап. Выбор факторной базы.

Факторная база состоит из некоторого множества элементов ap Z/nZ, ap = 0, где p пробегает некоторое конечное множество индексов P0. Все ap обратимы в Z/nZ (иначе был бы найден делитель n). Обозначим через ZP0 множество |P0|-мерных векторов:

ZP0 = {( p)p P0 | p Z}.

1Mips (англ.) — сокр. от million instructions per second — миллион команд в секунду (единица измерения быстродействия ЭВМ); year — год, mips-year — единица измерения числа операций за год.

96 Гл. 3. Факторизация целых чисел с субэкспоненциальной сложностью

где qi Q; им соответствуют векторы (q0, q1, q2, q3, q4) Q . Сложение

таких элементов (векторов) проводится покоординатно, а умножение

√

выполняется с помощью соотношения ( 5 2)5 = 2. Мы обозначаем через Norm норму алгебраического числа K в поле K; символом (j) мы обозначаем элемент j ( ), где 1, 2, 3, 4, 5 — все изоморфизмы

Лемма доказана.

Пусть R — коммутативное кольцо с единицей, — кольцевой гомо-

Z [ 2]. Равенство P = ( ) имеет место тогда и только тогда,

когда | Norm | = p и Ψp,c ( ) = 0.

Доказательство. Очевидно, что

ZK / Ker Ψp,c Z/pZ.

√

Поэтому Ker Ψp,c — простой идеал в ZK , содержащий p и 5 2 − c; следовательно, Ker Ψp,c = P.

Если | Norm | = p и Ψp,c ( ) = 0, то P и нормы ( ) и P совпадают,

где 1 и 2 — основные единицы поля K.

Поскольку поле K одноклассное, то любой ненулевой простой идеал P имеет вид P = ( P) для некоторого P ZK. Тогда для любого

100 Гл. 3. Факторизация целых чисел с субэкспоненциальной сложностью

Теперь осуществим первый этап алгоритма — построение факторной базы. Мы выбираем границу гладкости B = 1294973 для n = F9/p7. Рассматриваем все простые числа p B. Для каждого p

После нахождения множества простых идеалов первой степени

√

P = (p, 5 2 − c) мы должны найти P ZK , такие, что P = ( P). Для

этого можно использовать следующий перебор. Рассмотрим множество

такой идеал P единственен, то = P — его образующий. Если же таких P несколько, то — образующий того из них, для которого Ψp,c ( ) = 0 (по утверждению 3.33).

С помощью этого перебора было найдено 49 726 образующих про стых идеалов первой степени. Всего затем было найдено 99 500 образующих простых идеалов первой степени для нашей таблицы пар

Далее можно считать (заменяя при необходимости P на − P), что Norm P > 0.

102 Гл. 3. Факторизация целых чисел с субэкспоненциальной сложностью

Дальнейшее построение соотношений происходит с помощью методов решета. Мы перебираем пары a, b Z, b > 0, такие, что

1)НОД(a, b) = 1;

2)|a + 2103b| = | (a + b )| является B1-гладким числом, за исклю-

чением, может быть, одного простого делителя p1, B1 < p1 < 108;

3) |a5 − 8b5| является B2-гладким, за исключением, может быть, одного простого делителя p2, B2 < p2 < 108.

Если p1 и p2 отсутствуют, то пара a, b дает нам полное соотношение; в противном случае соотношение называется частичным. Заметим, что поскольку Norm(a + b ) = a5 − 8b5, то при p2 = 1 число a + b является B2-гладким.

Лемма 3.39. Пусть a, b Z, (a, b) = 1. Тогда любой простой идеал P кольца ZK , делящий a + b , является простым идеа-

то идеал (a + b ) в кольце ZK раскладывается на простые идеалы следующим образом:

m

Доказательство. Пусть p > 2 — простое число, P— простой идеал, такой, что P | (p) и P | (a + b ). Поскольку (a, b) = 1, то p b. Следовательно, ab−1 (mod p) P, откуда

√

(ab−1 (mod p))2 − 2 = (ab−1 (mod p))2 − 2 5 2 P,

√

5 2 − (2−1 (ab−1)2) (mod p) P.

По утверждению 3.23, Norm(a + b ) = a5 − 8b5. Поскольку a5 − 8b5 ≡ ≡ 0 (mod p), то

(2−1 (ab−1)2)5 − 2 ≡ 0 (mod p).

√

Положим c ≡ 2−1 (ab−1)2 (mod p). По теореме Куммера Q = (p, 5 2 − c) является простым идеалом первой степени, причем Q P. Следовательно, Q = P — простой идеал первой степени.

Мы показали также, что для каждого простого числа p = qk, делящего Norm(a + b ), простой идеал Qk в ZK , делящий a + b и qk, определен однозначно по указанной в лемме 3.39 формуле. Отсюда сле-

факторизации нормы Norm(a + b ) = a5 − 8b5 на простые числа следующим образом. Пусть

Тогда по лемме 3.39 Norm P — простое число, и Norm(a + b ) = (Norm P)kP.

P

Пусть P — простой идеал, делящий a + b , Norm P = p — простое число.

входит в разложение идеала (a + b ). Воспользуемся отображением Ψ из доказательства леммы 3.39. Тогда

вычисляем

P

и находим разложение для :

= v0 v1 v2 .

0 1 2

Показатель v0 определяется знаком , а v1 и v2 мы находим с помощью приближенных вычислений, как это было описано ранее.

2) a + 2103b = ± pwp , и это разложение мы находим с помощью

p B1

просеивания, о котором будет сказано чуть позже.

Теперь применим отображение из примера 3.25. Тогда

± pwp = a + 2103b ≡ (a + b ) (mod n) ≡

и это есть соотношение между элементами факторной базы, которое мы построили на 2 этапе алгоритма.

Мы ограничились рассмотрением пары a, b, дающей полное соотношение. Если соотношение частичное, т. е. появляются дополнительные простые числа p1, p2, то далее с помощью некоторой техники исключения из нескольких таких соотношений делают одно полное соотношение. Здесь используется теория графов; мы не рассматриваем эту технику в деталях.

Накопив достаточно много соотношений, мы переходим к 3 этапу алгоритма и находим X Z, X2 ≡ 1 (mod n), с помощью решения системы линейных уравнений над полем Z/2Z. При факторизации n = F9/p7 использовалось структурированное гауссово исключение для решения систем линейных уравнений над Z/2Z (см. об этом гл. 11).

кими числами соответственно. Для этого использовалось просеивание, аналогичное просеиванию в методе квадратичного решета из § 3.4.

(a, b) = 1. В элемент массива с номером a мы заносим достаточно грубо вычисленное значение log |a + 2103b|. Далее для каждого простого числа p, p B1, мы идем по арифметической прогрессии номеров a, для которых a + 2103b ≡ 0 (mod p), т. е. a = a0 (p) + jp, j Z. Из элементов массива с номерами a вычитаем грубо вычисленное значение log p. Аналогичное просеивание делаем для некоторых степеней pk простого числа p: в прогрессии a + 2103b ≡ 0 (mod pk) из элементов массива с номерами a также вычитаем log p.

После того, как мы проведем просеивание по всем p, в нашем массиве образуются некоторые результирующие значения. Если элемент массива с номером a окажется маленьким, то, скорее всего, a + 2103b будет B1-гладким числом. Тогда мы факторизуем a + 2103b пробными делениями на p B1. Если a + 2103b окажется B1-гладким, за исключением, может быть, одного простого p1, B1 < p1 < 108, то мы сохраняем пару a, b в некотором массиве M.

Замечание 3.41. На деле просеивание происходит более тонким способом, но мы не будем здесь это обсуждать. Читатель может обратиться к оригинальной работе [162] за дальнейшими разъяснениями.

Теперь для пар a, b из массива M мы проводим аналогичное просеивание для нахождения B2-гладких чисел a5 − 8b5 = Norm(a + b ). В итоге мы найдем некоторое множество пар a, b, дающих полное или частичное соотношение.

Для факторизации n = F9/p7 было найдено 44 106 полных соотношений и 2 903 999 частичных соотношения. Для этого использовалось около 700 рабочих станций в течение около 5 недель. Было затрачено примерно 340 mips-year. Затем решение системы линейных уравнений над полем Z/2Z заняло около 6 недель на суперкомпьютере. В итоге n разложилось на два множителя, простота каждого из которых была проверена с помощью алгоритма Ленстры—Коена (см. гл. 1). На этом факторизация числа Ферма F9 была завершена.

ла n = F9/p7. Мы опишем выбор числового поля для факторизации