Сравнительный анализ методов факторизации натуральных чисел

8. Когда все указанные действия будут проведены для всех простых чисел, не превосходящих , следует отбросить все числа , кроме обратившихся в 1 после деления на все степени , не превосходящих . В итоге получится таблица, в которой в столбце будут содержаться все такие значения из интервала , что есть -число, а остальные столбцы будут соответствовать тем значениям , для которых -- квадратичный вычет.

9. Далее используется обобщенный метод факторизации Ферма (метод факторных баз).



1.11 Факторизация с помощью эллиптических кривых

Алгоритм факторизации натурального числа с использованием эллиптических кривых. Данный алгоритм имеет субэкспоненциальное время выполнения. Является третьим по скорости работы после общего метода решета числового поля и метода квадратичного решета.

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

Алгоритм

Дано составное целое нечетное число . Нужно найти его нетривиальный делитель , .

Случайным образом выбирается эллиптическая кривая

где , и некоторая точка на ней. Если попытка разложения окажется неудачной, следует взять другие и и повторить алгоритм сначала.

1. Выбирается целое число , делящееся на степени малых простых чисел (не больших некоторого ), не превосходящих , то есть

где -- наибольший из возможных показателей, при котором .

2. Вычисление (все действия производятся по модулю n)

где -- операция сложения, определенная по групповому закону.

Вычисления проводятся до тех пор, пока при попытке найти число, обратное к не появляется число, не взаимно простое с . Это произойдёт при таком , что , то есть порядок в группе по модулю n является делителем .

3. При применении алгоритма Евклида вместо обращения знаменателя по модулю n, получаем нетривиальный наибольший общий делитель этого знаменателя и n, то есть, собственный делитель числа n.

Обоснование

Если числа p и q -- два простых делителя числа n, то эллиптическая кривая y² = x³ + ax + b (mod n) соответствует двум эллиптическим кривым: по модулю p и по модулю q. Эти две кривые с заданной операцией сложения точек образуют группы, содержащие N_p и N_q элементов, соответственно. По теореме Лагранжа для любой точки Р на исходной кривой по модулю p из равенства для минимального положительного числа k следует, что k делит N_p (в частности, ). Аналогичное утверждение справедливо и для кривой по модулю q. Для случайно выбранной эллиптической кривой порядки N_p и N_q являются случайными числами, близкими к p+1 и q + 1, соответственно (см. ниже). Поэтому маловероятно, что большинство простых делителей N_p и N_q совпадают, и вполне вероятно, что при вычислении eP мы столкнёмся с некоторыми по модулю р, но не по модулю q, или наоборот. Если это так, то kP не существует на исходной кривой, а в вычислениях мы нашли такое v, что либо НОД (v, p) = p, либо НОД (v, q) = q, но не одновременно. Тогда НОД (v, n) является нетривиальным делителем числа n.

1.12 Специальный метод решета числового поля

Специальный метод решета числового поля является методом факторизации целых чисел особого вида. Из него был получен общий метод решета числового поля, являющийся наиболее эффективным алогритмом факторизации больших целых чисел . Метод эффективен для целых чисел вида r^e ± s, где r N s Z, r и s невелики(например Числа Мерсенна).

Эвристическая оценка сложности факторизации числа n выражается формулой:

С помощью SNFS было разложено на множители число Ферма , содержащее 155 десятичных цифр.

Обзор метода

SNFS основан на более простом методе рационального решета. Читателю предлагается ознакомиться с данным методом до изучения SNFS.
SNFS работает следующим образом. Пусть n число для факторизации. Аналогично методу рационального решета, алгоритм SNFS может быть разбит на два шага:

· Нахождение числа мультипликативных соотношений факторной базы Z/nZ, большего чем число элементов в факторной базе.

· Перемножение соотношений между собой таким образом, чтобы степени полученных произведений были одинаковыми, то есть получение соотношений вида a²?b²(mod n). Это в свою очередь приведет к факторизации n: n=НОД(a+b,n)ЧНОД(a-b,n). В случае, если полученное разложение является тривиальным (то есть n=nЧ1), следует искать другие произведения соотношений, удовлетворяющие данному условию.

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

Детали метода

Пусть n -- это факторизуемое число. Возьмем неприводимый многочлен f и целое число m, такое что f(m)?0 (mod n) (принципы их выбора будут объяснены в следующем разделе). Пусть б корень f; тогда существует кольцо Z[б]. Тогда существует единственное кольцо гомоморфизма (англ.) ц между Z[б] и Z/nZ, которое отображает б в m. Для простоты полагаем, что Z[б] является факториальным кольцом; метод может быть модифицирован для случая, когда это условие не выполняется, что приведет к дополнительным вычислениям.

Затем создадим две факторных базы, одну для Z[б] и одну для Z. Факторная база Z[б] содержит все простые числа Z[б], чей размер ограничен значением . Факторная база Z, как и в методе рационального решета, состоит из простых чисел до некоторого граничного числа.

Затем ищем такие взаимно простые числа (a,b) что:

· a+bm является гладким по отношению к элементам факторной базы Z (то есть все его простые делители содержатся в факторной базе).

· a+bб является гладким по отношению к элементам факторной базы Z[б];из того как мы выбирали элементы факторной базы, это условие эквивалентно тому, что a+bб делится только на простые числа, меньшие .

Эти пары чисел находятся методом просеивания, аналогичным методу решета Эратосфена; это объясняет название метода решета числового поля.

Для каждой такой пары чисел (a,b) мы можем применить кольцо гомоморфизма ц для факторизации a+bб и каноническое кольцо гомоморфизма от Z до Z/nZ для факторизации a+bm. Приравняв их, получим мультипликативные соотношения для элементов факторной базы Z/nZ. Найдя достаточное количество таких соотношений, перемножаем их между собой, как описано выше.

Ограничения

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

1.13 Общий метод решета числового поля

Суть метода

Метод решета числового поля (как специальный, так и общий) можно представить как усовершенствование более простого метода -- метода рационального решета, либо метода квадратичного решета. Подобные им алгоритмы требуют нахождение гладких чисел порядка . Размер этих чисел экспоненциально растёт с ростом . Метод решета числового поля, в свою очередь, требует нахождения гладких чисел субэкспоненциального относительно размера. Благодаря тому, что эти числа меньше, вероятность того, что число такого размера окажется гладким выше, что и является причиной эффективности метода решета числового поля. Для достижения ускорения вычислений в рамках метода проводятся в числовых полях, что усложняет алгоритм, по сравнению с более простым рациональным решетом.

Основные принципы

· Метод факторизации Ферма для факторизации натуральных нечетных чисел n, состоящий в поиске таких целых чисел x и y, что , что ведет к разложению .

· Нахождение подмножества множества целых чисел, произведение которых -- квадрат

· Составление факторной базы: набора , где p_i -- простые числа такие, что для некоторого B.

· Просеивание выполняется подобно решету Эратосфена (откуда метод и получил своё название). Решетом служат простые числа факторной базы и их степени. При просеивании число не «вычёркиваются», а делится на число из решета. Если в результате число оказалось единицей, то оно B-гладкое.

· Основная идея состоит в том, чтобы вместо перебора чисел и проверки, делятся ли их квадраты по модулю n на простые числа из факторной базы, перебираются простые числа из базы и сразу для всех чисел вида проверяется, делятся ли они на это простое число или его степень.

Алгоритм

Пусть -- нечетное составное число, которое требуется факторизовать.

1. Выберем степень неприводимого многочлена (при не будет выигрыша в сравнении с методом квадратичного решета).

2. Выберем целое такое, что , и разложим n по основанию :

(1)

3. Свяжем с разложением (1) неприводимый в кольце полиномов с целыми коэффициентами многочлен



4. Определим полином просеивания как однородный многочлен от двух переменных и :

(2)

5. Определим второй полином и соответствующий однородный многочлен .

6. Выберем два положительных числа и , определяющих область просеивания (англ. sieve region):

7. Пусть -- корень . Рассмотрим кольцо полиномов . Определим множество, называемое алгебраической факторной базой , состоящее из многочленов первого порядка вида с нормой (2), являющейся простым числом. Эти многочлены -- простые неразложимые в кольце алгебраических целых поля . Ограничим абсолютные значения норм полиномов из константой .

8. Определим рациональную факторную базу , состоящую из всех простых чисел, ограниченных сверху константой .

9. Определим множество , называемое факторной базой квадратичных характеров. Это множество полиномов первого порядка , норма которых - простое число. Должно выполняться условие .

10. Выполним просеивание многочленов по факторной базе и целых чисел по факторной базе . В результате получим множество , состоящее из гладких пар , то есть таких пар , что НОД(a,b) = 1, полином и число и раскладываются полностью по и соответственно.

11. Найдём такое подмножество , что

12. Определим многочлен

где -- производная

13. Многочлен является полным квадратом в кольце полиномов . Пусть тогда есть корень из и -- корень из .

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

15. Пусть . Найдём пару чисел таких, что . Тогда найдём делитель числа , вычисляя НОД(n, A ± B), как это делается, например, в методе квадратичного решета.



Глава 2. Примеры реализации алгоритмов натуральных чисел и оценка их эффективности

2.1 Примеры разложения натуральных чисел

2.1.1 Метод факторизации Ферма

Пример с малым числом итераций

Возьмем число. Вычислим Для будем вычислять значения функции . Для дальнейшей простоты построим таблицу, которая будет содержать значения и на каждом шаге итерации. Получим:

1	363	19,052
2	576	24

Как видно из таблицы, уже на втором шаге итерации было получено целое значение .

Таким образом имеет место следующее выражение:. Отсюда следует, что

Пример с большим числом итераций

Пусть Тогда или

77	52374	228,854
78	53129	230,497
79	53886	232,134
80	54645	233,763
81	55406	235,385
82	56169	237

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

2.1.2 Метод Крайчика-Ферма

С помощью метода Крайчика-Ферма разложим число Число является первым, чей квадрат больше числа :

Вычислим значение функции для всех , получим

По методу Ферма, нужно было бы продолжать вычисления пока не был бы найден квадрат какого-либо числа. По методу Крайчика-Ферма далее нужно последовательно искать такие , для которых Тогда

Из алгоритма Крайчика-Ферма следует, что все полученные числа можно легко факторизовать.

Действительно:

Очевидно, что произведение полученный четырех чисел будет квадратом: Тогда теперь можно вычислить

Далее с помощью алгоритма Евклида находим .

Таким образом,

2.1.3 С-алгоритм Полларда

Пусть , , , .

i	xi	yi	НОД(|xi ? yi|, 8051)
1	5	26	1
2	26	7474	1
3	677	871	97

Таким образом, 97 - нетривиальный делитель числа 8051. Используя другие варианты полинома , можно также получить делитель 83.

2.1.4 Метод квадратичных форм Шенкса

Применим данный метод для факторизации числа

Цикл №1
Цикл №2

Теперь можно увидеть во втором цикле, что Следовательно число

2.1.5 Алгоритм Лемана

Разберем пример с , тогда для , где , проверяем является ли число делителем числа . Не трудно убедится, что таких нет, тогда переходим к следующему пункту.

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

2.1.6 Алгоритм Диксона

Факторизуем число .

Все найденные числа с соответствующими векторами записываем в таблицу.

337	23814	1	5	0	2	0	0
430	5390	1	0	1	2	1	0
519	96	5	1	0	0	0	0
600	980	2	0	1	2	0	0
670	125	0	0	3	0	0	0
817	39204	2	4	0	0	2	0
860	21560	3	0	1	2	1	0

Решая линейную систему уравнений, получаем, что . Тогда

Следовательно,

.

Получилось разложение

2.1.7 Факторизация с помощью эллиптических кривых

Допустим, нам нужно факторизовать число n = 455839.

Возьмем эллиптическую кривую и точку, лежащую на этой кривой

Попробуем вычислить 10!P:

- Для начала вычислим координаты точки . Тангенс угла наклона касательной в точке P равен:

- Находим координаты точки :

.

- Проверяем, что точка 2P действительно лежит на кривой:

2. Теперь вычислим .

- Тангенс угла наклона касательной в точке 2P составляет

.

Для вычисления 593 / 106 по модулю n можно воспользоваться расширенным алгоритмом Евклида: 455839 = 4300·106 + 39, далее 106 = 2·39 + 28, далее 39 = 28 + 11, далее 28 = 2·11 + 6, далее 11 = 6 + 5, далее 6 = 5 + 1. Откуда получаем, что НОД(455839, 106) = 1, и в обратную сторону: 1 = 6 - 5 = 2·6 - 11 = 2·28 - 5·11 = 7·28 - 5·39 = 7·106 - 19·39 = 81707·106 - 19·455839. Откуда 1/106 = 81707 (mod 455839), таким образом, -593 / 106 = 322522 (mod 455839).

- Учитывая вычисленное s, мы можем вычислить координаты точки 2(2P), так же, как это было сделано выше: 4P = (259851, 116255). Проверяем, что точка действительно лежит на нашей эллиптической кривой.

- Суммируя 4P и 2P, находим .

- Аналогичным образом можно вычислить , , и так далее. Когда дойдем до 8!P заметим, что требуется вычисление обратного элемента к 599 (mod 455839). Так как 455839 делится на 599, то мы нашли искомое разложение: 455839 = 599·761.

2.2 Факторизация в криптографии

Разложение (факторизация) натуральных чисел на множители является трудной вычислительной задачей. Сложность решения этой задачи лежит в основе одного из наиболее известных методов криптографии - методе RSA. Существует большое количество алгоритмов факторизации, среди которых наиболее быстрыми на сегодняшний день методами являются метод квадратичного решета и метод решета числового поля.

RSA (аббревиатура от фамилий Rivest, Shamir и Adleman) -- криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел.

Криптографические системы с открытым ключом используют так называемые односторонние функции, которые обладают следующим свойством:

· Если известно , то вычислить относительно просто

· Если известно , то для вычисления нет простого (эффективного) пути.

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

В основу криптографической системы с открытым ключом RSA положена сложность задачи факторизации произведения двух больших простых чисел. Для шифрования используется операция возведения в степень по модулю большого числа. Для дешифрования за разумное время (обратной операции) необходимо уметь вычислять функцию Эйлера от данного большого числа, для чего необходимо знать разложения числа на простые множители.

В криптографической системе с открытым ключом каждый участник располагает как открытым ключом, так и закрытым ключом. В криптографической системе RSA каждый ключ состоит из пары целых чисел. Каждый участник создаёт свой открытый и закрытый ключ самостоятельно. Закрытый ключ каждый из них держит в секрете, а открытые ключи можно сообщать кому угодно или даже публиковать их. Открытый и закрытый ключи каждого участника обмена сообщениями в криптосистеме RSA образуют «согласованную пару» в том смысле, что они являются взаимно обратными, то есть:

сообщения , где -- множество допустимых сообщений

допустимых открытого и закрытого ключей и

соответствующие функции шифрования и расшифрования , такие что

Алгоритм создания открытого и секретного ключей

RSA-ключи генерируются следующим образом:

1. Выбираются два различных случайных простых числа и заданного размера.

2. Вычисляется их произведение , которое называется модулем.

3. Вычисляется значение функции Эйлера от числа :

4. Выбирается целое число , взаимно простое со значением функции . Обычно в качестве берут простые числа, содержащие небольшое количество единичных бит в двоичной записи, например, простые числа Ферма 17, 257 или 65537.

· Число называется открытой экспонентой.

· Время, необходимое для шифрования с использованием быстрого возведения в степень, пропорционально числу единичных бит в .

· Слишком малые значения , например 3, потенциально могут ослабить безопасность схемы RSA.

5. Вычисляется число , мультипликативно обратное к числу по модулю , то есть число, удовлетворяющее условию:

· Число d называется секретной экспонентой. Обычно, оно вычисляется при помощи расширенного алгоритма Евклида.

6. Пара публикуется в качестве открытого ключа RSA.

7. Пара играет роль закрытого ключа RSA секрете.

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

В программной среде maple реализован ряд алгоритмов факторизации, который включает в себя как отдельные алгоритмы, так и синтез нескольких алгоритмов для более продуктивной факторизации.

Далее приведены списки методов, которые включены в разные версии Maple.

В Maple 6:

'squfof' - метод Квадратичных форм Шенкса;

'pollard' - алгоритм Полларда;

'lenstra' - метод эллиптических кривых Ленстры;

'easy' - без дальнейшей обработки.

В последних версиях Maple:

'mpqs' - множественный полиномиальный метод квадратичного решета;

'morrbril' - алгоритм Брилхарта-Моррисона;

'squfof' - метод квадратичных форм Шенкса;

'pollard' - алгоритм Полларда;

'lenstra' - метод эллиптических кривых Ленстры;

'mpqsmixed' - 'mpqs', 'morrbril' и 'pollard';

'mixed' - 'morrbril' и 'pollard' (по умолчанию в версиях Maple 11 и более ранних)

'easy' - без дальнейшей обработки;

`Easy' - если данный вариант разложения будет выбран, результатом ifactor будет произведение чисел, которые легко было отделить, а также «_c.m._.n», которое обозначает m-значное составное число, которое не было разложено, где n - уникальный номер данного составного числа.

`Pollard' - метод Полларда, опционально требующий дополнительное целое k (ifactor(n,pollard,k)), которое повышает эффективность метода в том случае, если один из сомножителей имеет форму k*m+1.

В процессе написания данной работы мной была использована платформа Maple 6 для более детального рассмотрения различных алгоритмов факторизации натуральных чисел. Так как моей целью было проанализировать и сравнить некоторые алгоритмы, реализованные в среде Maple, и время их исполнения, я проделал следующие действия (см. Приложение, с.50):

1. Для проверки времени исполнения алгоритмов для неструктурированного числа.

- Сгенерировал два крупных простых числа посредством функций nextprime и prevprime;

- Перемножил их и запустил для полученного числа процедуру ifactor без дополнительных параметров, с параметром squifof, pollard и lenstra. Так как мне нужно было время исполнения, я ипользовал функцию time от ifactor;

- Получил значения для разных алгоритмов. Для алгоритма по умолчанию (алгоритм Моррисона-Брилхарта вместе с алгоритмом Полларда), получил значение 632,795 секунды.

Для squifof это значение было “0.”, то есть малейшие доли секунды. Алгоритм Полларда пришлось остановить на 308ой тысяче секунд(3,56 суток), алгоритм Ленстры дал результат через 20311,795 секунды.

2. Далее я применил алгоритмы для структурированного числа вида k*(2^t+1).

- Взял k равным простому числу 331, а t (степень двойки в выражении) равным 190. Нашёл значение выражения с этими данными;

- Применил ifactor и нашёл время выполнения ifactor от нашего числа. Время выполнения составило 47193,554 секунды;

- Далее я применил алгоритм squifof для числа той же структуры, но с большим показателем степени двойки, t = 9290. Данным алгоритмом число разложилось за 77.5 секунды;

3. В третий раз я взял также структурированное число, но теперь это был факториал от данного числа t.

- Я положил t равным 1221 и получил очень крупное число в 2800 знаков;

- Воспользовавшись алгоритмом Ленстры, я получил время выполнения - всего 0,63 секунды.

Отсюда мы видим, что при изменении структуры числа, алгоритмы ведут себя по-разному. Применяя один и тот же алгоритм, для разложения числа с 2800 знаков требуется примерно в 32000 раз меньше времени, чем для разложения числа с 48 знаками. При этом структура числа различна. В первом случае в числе очень много небольших делителей, а во втором случае их всего два, и оба - крупные простые числа.



2.4 Оценка эффективности алгоритмов факторизации натуральных чисел

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

Алгоритм Ленстры на практике часто используется для выявления (отбрасывания) небольших простых делителей числа. И в этом мы убедились, разложив 32000-значное число 1221! за время в 0,63 секунды. Так как в числе 1221! содержатся все первые 1221 числа, то выявить и отбросить все тривиальные делители не составит труда. Однако если мы работаем с числом, содержащим в себе крупные простые множители, то нам нужно увеличивать количество кривых, так как при увеличении количества кривых шансы найти простой делитель возрастают, тем не менее, зависимость ожидаемого количества эллиптических кривых от количества цифр в искомом делителе экспоненциальна. Метод Полларда очень быстро находит простые факторы малой и средней величины, однако, столкнувшись с крупным простым сомножителем, становится малоэффективным.

Среди алгоритмов факторизации с экспоненциальной сложностью метод квадратичных форм Шенкса считается одним из самых эффективных. Этот алгоритм работает с целыми числами, не превосходящими . Мы знаем, что для 32-разрядных компьютеров алгоритмы, основанные на данном методе, являются безусловными лидерами из алгоритмов факторизации для чисел между до и, вероятно, таковым и останутся. Данный алгоритм может разделить практически любое составное 18-значное число менее чем за миллисекунду. Алгоритм является чрезвычайно простым, красивым и эффективным. Кроме того, методы, базирующиеся на данном алгоритме, используются как вспомогательные при разложении делителей больших чисел.

Заключение

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

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

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

В данной работе мы рассмотрели некоторые алгоритмы факторизации натуральных чисел, а также провели сравнительную характеристику оных по группам структур. На практических примерах мы убедились в эффективности и целесообразности применения одних методов перед другими, опять же с учётом структуры данного числа.

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

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



Список литературы

1. A. Heck. Introduction to Maple. Springer-Verlag, third edition, 2003.

2. Бухштаб А.А. Теория чисел. -- М.: Учпедгиз, 1960.

3. Василенко О. Н. В19 Теоретико-числовые алгоритмы в криптографии. - М.:МЦНМО, 2003.--328 с. ISBN 5-94057-103-4.

4. Ишмухаметов Ш.Т. Методы факторизации натуральных чисел: учебное пособие. Казань: Казан. Ун-т, 2011. 190 с.

5. Д. Кнут Раздел 4.5.4. Разложение на простые множители // Искусство программирования = The Art of Computer Programming. -- 3-е изд. -- М.: Вильямс, 2007. -- Т. 2. Получисленные алгоритмы. -- С. 425--468. -- 832 с.

6. Макаренко А.В., Пыхтеев А.В., Ефимов С.С. Параллельная реализация и сравнительный анализ алгоритмов факторизации в системах с распределённой памятью.

7. Манин Ю.И., Панчишкин А.А. Введение в современную теорию чисел. М.: МЦНМО, 2009.

8. Ю. И. Манин, А. А. Панчишкин. I.2.3. Разложение больших чисел на множители // Введение в теорию чисел.-- М.: ВИНИТИ, 1990. -- Т. 49. -- С. 72--106. -- 341 с.

9. Молчанова Л.А. Введение в Maple. Учебно-методическое пособие. - Владивосток: Изд-во Дальневост. Ун-та, 2006. - 36 С.

10. Ю. В. Нестеренко. Глава 4.7. Как раскладывают составные числа на множители // Введение в криптографию / Под ред. В. В. Ященко. -- Питер, 2001. -- 288 с.

11. http://www.maplesoft.com - официальный сайт компании Maplesoft, производителя Maple.

12. http://www.exponenta.ru - образовательный математический сайт.

13. http://www.wikipedia.org/ - свободная энциклопедия.



Приложение

> restart;

> p:=nextprime(476523189475631579423453); (23 знака)

q:=prevprime(957532186478621546879541); (23 знака)

> n:=p*q;(48 знаков)

> time(ifactor(n));

> time(ifactor(n,squifof));

> time(ifactor(n,pollard)); (остановлено на 308 тысяче секунд ожидания)

Warning, computation interrupted

> time(ifactor(n,lenstra));

> restart;

> p:=nextprime(476523189475631579); (17 знаков)

q:=prevprime(957532186478621546879548756); (26 знака)

> n:=p*q;(45 знаков)

> time(ifactor(n));

> time(ifactor(n,squifof));

> time(ifactor(n,lenstra));

>

>

> restart;

> p:=nextprime(4765231894756315791);(19 знаков)

q:=prevprime(9575321869491284011);(19 знаков)

t:=nextprime(1112154682);(10 знаков)

> n:=p*q*t;(52 знака)

> time(ifactor(n));

> time(ifactor(n,squifof));

> time(ifactor(n,lenstra));

> restart;

k:=nextprime(320);t:=190;

> n:=k*(2^t)+1;(60 знаков)

> time(ifactor(n));

> k:=nextprime(320);t:=160;

n:=k*(2^t)+1; (52 знака)

> time(ifactor(n));

> k:=nextprime(320);t:=150;

n:=k*(2^t)+1;(48 знаков)

> time(ifactor(n));

> k:=nextprime(320);t:=9290;

n:=k*(2^t)+1;



> time(ifactor(n,squifof));

> k:=nextprime(3);t:=1221;

n:=t!;

time(ifactor(n,lenstra));

> p:=nextprime(4761523466525157654535):

q:=nextprime(1182212457245723424513):

n:=p*q;

> time(ifactor(n,lenstra));

Размещено на Allbest.ru