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

Размещено на http://www.allbest.ru/

Содержание

Введение

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

1.1 Факторизация натурального числа

1.2 Перебор делителей

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

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

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

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

1.7 Метод Лемана

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

1.9 Факторизация методом непрерывных дробей

1.10 Метод квадратичного решета

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

Список используемой литературы

Приложение



ВВЕДЕНИЕ

В настоящее время исследования в области построения быстрых алгоритмов факторизации интенсивно ведутся во всем мире. Ежегодно проводятся десятки конференций по этой тематике, достигаются новые рекорды факторизации длинных чисел, исследуются известные проблемы алгоритмической теории чисел и ставятся новые проблемы. Недавно (в конце 2009 г.) коллективом европейских ученых, возглавляемым Торштеном Кляйнъюнгом, был установлен новый рекорд по разложению 768- битового натурального числа с помощью метода решета числового поля. Предыдущий рекорд в 512-бит был установлен в 2000 г., т.е. переход от 512- битовых к 768-битовым числам потребовал почти 10 лет. Поэтому следующий рекорд в 1024 бита при сохранении прежних темпов роста исследований планируется выполнить не ранее, чем в 2020 г.

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

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

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

1. Рассмотреть алгоритмы факторизации натуральных чисел;

2. Провести сравнительную характеристику методов факторизации по группам сложности;

3. Рассмотреть выбранные методы факторизации на практических примерах;

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

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

В данной работе были рассмотрены следующие методы факторизации натуральных чисел:

Экспоненциальные алгоритмы

- Перебор возможных делителей

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

- с-алгоритм Полларда

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

- метод Лемана

Субэкспоненциальные алгоритмы

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

- метод непрерывных дробей

- метод квадратичного решета

- метод эллиптических кривых

Решето числового поля

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

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

Научная постановка и разработка отдельных сторон исследования темы нашла свое отражение в работах отечественных ученых-математиков. При написании работы были использована учебная и периодическая литература следующих авторов: Панчишкин А.А., Нестеренко Ю.В., Бухштаб А.А. и др.

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

1.1 Факторизация натурального числа

Натуральное число называется простым, если оно делится только на себя и на 1. Число, не являющееся простым, называется составным. Очевидно, что любое простое число, не равное 2, является нечетным. Существуют признаки делимости целых чисел на различные простые числа, например, чтобы число в десятичном виде делилось на 3 и 9 достаточно, чтобы сумма его цифр делилась на 3 и 9 соответственно. Чтобы число делилось на 5, достаточно, что его последняя цифра была 0 или 5. Такие частные признаки делимости можно использовать, если нужно уменьшить множество кандидатов проверки на простоту или отсечь заведомо составные числа. Альтернативным способом получения простых чисел является решето Эратосфена, приписываемое древнегреческому ученому Эратосфену Киренскому, жившему примерно в 276 - 194 г. до н.э. Для нахождения множества простых до заранее выбранной верхней границы B мы сначала выписываем последовательность всех нечетных чисел от 3 до B. Затем выбираем первое число в списке, т.е. тройку, и оставляя его в списке, вычеркиваем все кратные 3, начиная с 6. Потом переходим ко второму числу списка (пятерке) и вычеркиваем его кратные, оставив саму пятерку и т.д., пока не дойдем до конца списка. В оставшемся списке будут только простые числа.

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

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

В данной работе были рассмотрены следующие методы факторизации натуральных чисел:

Экспоненциальные алгоритмы

- Перебор возможных делителей

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

- с-алгоритм Полларда

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

- метод Лемана

Субэкспоненциальные алгоритмы

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

- метод непрерывных дробей

- метод квадратичного решета

- метод эллиптических кривых

Решето числового поля

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

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

Сложность факторизации

В зависимости от сложности алгоритмы факторизации можно разбить на две группы. Первая группа -- экспоненциальные алгоритмы, сложность которых экспоненциально зависит от длины входящих параметров (то есть от длины самого числа в бинарном представлении). Для обозначения их сложности принята O-нотация. Эта нотация позволяет учитывать в функции f (n) лишь наиболее значимые элементы, отбрасывая второстепенные.
Например, в функции при достаточно больших компонента будет значительно превосходить остальные слагаемые, и поэтому характерное поведение этой функции определяется именно этой компонентой. Остальные компоненты можно отбросить и условно записать, что данная функция имеет оценку поведения (в смысле скорости роста ее значений) вида . Фраза «алгоритм факторизации с вычислительной сложностью » означает, что с увеличением параметра , характеризующего количество входной информации алгоритма, время работы алгоритма не может быть ограничено величиной, которая растет медленнее, чем .

Вторая группа -- субэкспоненциальные алгоритмы, это алгоритмы, которые работают более, чем за полиномиальное время («сверх-полиномиальное»), но менее, чем за экспоненциальное время («субэкспоненциальное»). Для обозначения их сложности принята L-нотация:

где N -- число, подлежащее факторизации, и c -- некоторые константы.

· Экспоненциальные алгоритмы

- Перебор возможных делителей -- наиболее тривиальный алгоритм факторизации с вычислительной сложностью .

- с-алгоритм Полларда имеет сложность ;

- метод квадратичных форм Шенкса имеет сложность ;

- метод Лемана имеет сложность

· Субэкспоненциальные алгоритмы

- алгоритм Диксона имеет сложность ;

- метод непрерывных дробей имеет сложность ;

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

- метод эллиптических кривых имеет сложность , где -- наименьшее простое, которое делит .

· Решето числового поля

В настоящее время самыми эффективными алгоритмами факторизации являются вариации решета числового поля:

- Специальный метод решета числового поля со сложностью (метод применим для факторизации чисел только специального вида);

- Общий метод решета числового поля со сложностью (метод применим ко всем числам).

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

Описание наиболее известных методов факторизации натуральных чисел.

факторизация натуральный число алгоритм

1.2 Перебор делителей

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

Описание алгоритма

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

Практическое применение

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

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

Метод факторизации Ферма -- алгоритм факторизации (разложения на множители) нечётного целого числа , предложенный Пьером Ферма (1601-1665) в 1643 году.

Метод основан на поиске таких целых чисел и , которые удовлетворяют соотношению , что ведёт к разложению.

Обоснование

Метод Ферма основан на теореме о представлении числа в виде разности двух квадратов:

Если нечетно, то существует взаимно однозначное соответствие между разложениями на множители и представлениями в виде разности квадратов с , задаваемое формулами

Доказательство

Если задана факторизация , то имеет место соотношение: . Таким образом, получается представление в виде разности двух квадратов.

Обратно, если дано, что , то правую часть можно разложить на множители: .

Описание алгоритма

Для разложения на множители нечётного числа ищется пара чисел таких, что , или . При этом числа и являются множителями , возможно, тривиальными (то есть одно из них равно 1, а другое -- .)

Равенство равносильно , то есть тому, что является квадратом.

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

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

в котором

Если оно является тривиальным и единственным, то -- простое.

На практике значение выражения на -ом шаге вычисляется с учетом значения на -ом шаге:

где

Таким образом, как и метод пробного деления, алгоритм Ферма имеет экспоненциальную оценку и не эффективен для разложения длинных чисел. Можно улучшить метод Ферма, выполнив сначала пробное деление числа n на числа от 2 до некоторой константы B, исключив тем самым малые делители n до B включительно, и только потом выполнить поиск методом Ферма.



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

Обобщение метода Ферма было предложено Морисом Крайчиком (1882-1957). Он предложил рассматривать вместо пар чисел которые удовлетворяют соотношению искать пары чисел, удовлетворяющих более общему уравнению Крайчик заметил, что многие из чисел, получаемых по формуле раскладываются на простые множители, т.е. числа являются гладкими.

Последовательность действий по Крайчику

1. Найти множество пар которые удовлетворяют соотношению

2. Определить полное или частное разложение чисел и на множители для каждой пары

3. Выбрать пары произведение которых удовлетворит соотношению

4. Разложить число на множители.

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

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

с-aлгоритм Джона Полларда, предложенный им в 1975 году, служит для факторизации целых чисел. Он основывается на алгоритме Флойда поиска длины цикла в последовательности и некоторых следствиях из парадокса дней рождений. Алгоритм наиболее эффективен при факторизации составных чисел с достаточно малыми множителями в разложении. Сложность алгоритма оценивается, как .

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

Описание алгоритма

Оригинальная версия

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

1. Будем вычислять тройки чисел

, где .

Причем каждая такая тройка получается из предыдущей.

2. Каждый раз, когда число кратно числу (скажем, ), будем вычислять наибольший общий делитель любым известным методом.

3. Если , то найдено частичное разложения числа , причем .

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

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

Современная версия

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

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

2. Одновременно на каждом i-ом шаге вычисляем для каких-либо , таких, что , например, .

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

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

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

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

Улучшения алгоритма

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

Пусть . Заметим, что если , то , поэтому, если пара дает нам решение, то решение даст любая пара .

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

Эта идея была предложена Ричардом Брентом в 1980 году и позволяет уменьшить количество выполняемых операций приблизительно на 25%.

Еще одна вариация P-метода Полларда была разработана Флойдом. Согласно Флойду, значение обновляется на каждом шаге по формуле , поэтому на шаге i будут получены значения , , и НОД на этом шаге вычисляется для и .

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

Это метод факторизации целых чисел, основанный на применении квадратичных форм, разработанный Даниелем Шенксом в 1975 году, как развитие метода факторизации Ферма.

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

Вспомогательные определения

Для того чтобы понять, как реализован этот алгоритм, необходимо узнать минимальные сведения о математических объектах, используемых в данном методе, а именно о квадратичных формах. Бинарной квадратичной формой называется полином от двух переменных и :

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

Для любой неопределенной квадратичной формы можно определить оператор редукции как:

,

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

Результат применения оператора к форме раз записывается в виде . Также определен оператор как:

,

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

Метод получения редуцированной формы, эквивалентной данной, был найден еще Карлом Гауссом и состоит в последовательном применении оператора редукции , пока не станет редуцированной.

Теорема.

Каждая форма эквивалентна некоторой редуцированной форме, и любая редуцированная форма для равна для некоторого положительного . Если - редуцирована, то также редуцирована.

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

Варианты

Идея метода Шенкса состоит в сопоставлении числу , которое надо разложить квадратичной бинарной формы с дискриминантом , с которой потом выполняется серия эквивалентных преобразований и переход от формы к неоднозначной форме . Тогда, будет являться делителем .

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

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

Описание алгоритма

Более подробно алгоритм может быть записан в следующем виде:

Вход: Нечетное составное число , которое требуется факторизовать. Если заменим на Теперь Последнее свойство нужно, чтобы определитель квадратичной формы был фундаментальным, что обеспечивает сходимость метода.

Выход: Нетривиальный делитель .

1. Определим исходную квадратичную форму , с дискриминантом , где .

2. Выполним цикл редуцирований , пока форма не станет квадратной.

3. Вычислим квадратный корень из .

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

1.7 Метод Лемана

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

Алгоритм

Пусть нечетно и .

Шаг 1. Для проверить условие . Если на этом шаге мы не разложили на множители, то переходим к шагу 2.

Шаг 2. Если на шаге 1 делитель не найден и -- составное, то , где -- простые числа, и . Тогда для всех и всех проверить, является ли число квадратом натурального числа. Если является, то для и выполнено сравнение:

или .

В этом случае для проверяется неравенство . Если оно выполнено, то -- разложение на два множителя.

Если алгоритм не нашел разложение на два множителя, то -- простое число.

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

Трудоемкость

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

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

Таким образом трудоемкость всего есть величина .

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

Алгоритм Диксона -- алгоритм факторизации, использующий в своей основе идею Лежандра, заключающуюся в поиске пары целых чисел и таких, что и

Метод Диксона является обобщением метода Ферма.

Описание алгоритма

1. Составить факторную базу , состоящую из всех простых чисел , где .

2. Выбрать случайное и вычисляется .

3. Вычислить .

4. Проверить число на гладкость пробными делениями. Если является -гладким числом, то есть , следует запомнить вектора и :

.

5. Повторять процедуру генерации чисел до тех пор, пока не будет найдено -гладких чисел .

6. Методом Гаусса найти линейную зависимость среди векторов :

и положить:

.

7. Проверить . Если это так, то повторить процедуру генерации. Если нет, то найдено нетривиальное разложение:

1.9 Факторизация методом непрерывных дробей

В теории чисел факторизация методом непрерывных дробей (CFRAC) -- это алгоритм факторизации целых чисел. Это алгоритм общего вида, пригодный для факторизации любого целого n не опирающийся на специальные формы или свойства. Он был найден Д. Г. Лемером и Р. Е. Поверсом в 1931-ем году, и переработан в алгоритм для компьютера Михаэлем А. Моррисоном и Джоном Бриллхартом в 1975-ом.

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

1.10 Метод квадратичного решета

Это метод факторизации больших чисел, разработанный Померанцем в 1981 году. Долгое время превосходил другие методы факторизации целых чисел общего вида, не имеющих простых делителей, порядок которых значительно меньше (для чисел , имеющих простые делители, много меньшие более быстрым является метод факторизации на эллиптических кривых). Метод квадратичного решета представляет собой разновидность метода факторных баз(обобщение метода факторизации Ферма). Этот метод считается вторым по быстроте (после общего метода решета числового поля). И до сих пор является самым быстрым для целых чисел до 100 десятичных цифр и устроен значительно проще, чем общий метод решета числового поля. Это универсальный алгоритм факторизации, так как время его выполнения исключительно зависит от размера факторизуемого числа, а не от его особой структуры и свойств.

Основные цели

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

Один из простых методов отыскания равных квадратов заключается в том, чтобы выбрать случайное число, возвести его в квадрат и надеяться, что остаток от деления на n является квадратом какого-либо другого числа. Например, 80² mod 5959 = 441 = 21². Этот способ находит равные квадраты лишь в редких случаях для больших n, но если он действительно найдет эти числа, то можно считать, что факторизация завершена. Этот метод похож на метод факторизации Ферма.

Метод квадратичного решета является модификацией метода разложения на множители Диксона.

Продолжительность расчёта для квадратичного решета (n - факторизуемое число):

.

Подход

Пусть x mod y обозначает остаток от деления x на y. В методе факторизации Ферма в отдельности подбираем число a, чтобы a² mod n являлось квадратом. Но такое число подобрать тяжело. В квадратичном решете мы вычисляем a² mod n для некоторых a, и затем находим такое подмножество, произведение элементов которого является квадратом. Это приведёт к сравнению квадратов.

Например, 41² mod 1649 = 32, 42² mod 1649 = 115, и 43² mod 1649 = 200. Ни один из полученных результатов не является квадратом, но результат произведения (32)(200) = 6400 = 80². С другой стороны, рассмотрев предыдущее произведение по mod 1649, мы получим, что (32)(200) = (41²)(43²) = ((41)(43))². Так как (41)•(43) mod 1649 = 114, мы имеем сравнение квадратов: 114² ? 80² (mod 1649).

Но как мы решаем проблему, фиксируя множество чисел и, находя подмножество, произведение элементов, которого является квадратом? Начнём с понятия вектор показателей степеней. Например, что у нас есть число 504. Его разложение на простые множители имеет следующий вид 504 = 2³3²5⁰7¹. Мы могли бы представить это разложение в виде вектора показателей степеней (3,2,0,1), который фиксирует степени простых чисел 2, 3, 5 и 7, участвующих в разложении. Число 490 по аналогии имело бы вектор (1,0,1,2). Умножение чисел - это то же самое, что и поэлементное сложение их векторов показателей степеней, то есть произведение 504 • 490 имеет вектор (4,2,1,3).

Теперь обратите внимание, что число является квадратом, если каждый элемент в его векторе показателей степеней чётный. К примеру, при сложении векторов (3,0,0,1) и (1,2,0,1) получаем (4,2,0,2). Это говорит нам о том, что произведение чисел 56 • 126 является квадратом. На самом деле, мы не заботимся о точных значениях, получаемых в векторе, до тех пор, пока каждый элемент в результирующем векторе чётный. По этой причине мы берём каждый элемент по mod 2 и выполняем сложение элементов по mod 2: (1,0,0,1) + (1,0,0,1) = (0,0,0,0).

Таким образом, наша задача приняла следующий вид: задано множество векторов (0,1), найти такое подмножество, которое дополняется до нулевого вектора, при использовании сложения по mod 2. Это задача линейной алгебры, то есть необходимо найти линейно зависимые вектора. Из теоремы линейной алгебры следует, что, до тех пор, пока количество векторов больше, чем количество элементов в каждом векторе, такая зависимость должна существовать. Мы можем эффективно находить линейно зависимые векторы, например, поместив исходные векторы, в качестве столбцов матрицы и затем, использовать метод Гаусса, который легко приспособить для работы с целыми числами по mod 2. Как только мы найдём линейно зависимые векторы, мы просто перемножаем числа, соответствующие этим векторам и получаем квадрат, который ищем.

Однако, возведение в квадрат множества случайных чисел по mod n приводит к большому числу различных простых множителей, длинным векторам и большой матрице. Чтобы избавиться от этой проблемы, мы специально ищем числа, такие, что a² mod n имеет только небольшие простые множители (такие числа называются гладкими числами). Их сложнее найти, но использование таких чисел позволяет избежать больших векторов и матриц.

Основная идея метода

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

Множество целых чисел, в котором ищутся -числа (-число -- целое число, делящееся только на простые числа из ) выглядит следующим образом:

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

Алгоритм

1. Выбираются границы и порядка величины (далее обозначается как ), такие что .

2. Для , ,…, по порядку в столбец выписываются целые числа .

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

4. Предполагая, что -- такое нечетное простое число, что -- квадратичный вычет по модулю , решается уравнение для 1,2,… . Значения берутся в порядке возрастания пока не окажется, что уравнение не имеет решений , сравнимых по модулю с каким-либо из чисел в области .

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

Пусть и решения и .

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

6. При добавлении очередной единицы к числу в столбце в п.5, соответствующее число делится на и полученный результат сохраняется.

7. В столбце под при просто ставится 1 против с нечетным и соответствующее делится на 2. При решается уравнение и решение продолжается в том же ключе, как при нечетном .