Квадратное сито

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

Основная цель

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

Наивный подход к нахождению сравнения квадратов состоит в том, чтобы выбрать случайное число, возвести его в квадрат, разделить на n и надеяться, что наименьший неотрицательный остаток будет идеальным квадратом . Например, $80^{2}\equiv 441=21^{2}{\pmod {5959}}$. Этот подход лишь изредка находит сравнение квадратов для больших n , но когда он все же находит его, чаще всего, сравнение нетривиально и факторизация завершена. Это примерно основа метода факторизации Ферма .

Квадратичное решето — это модификация метода факторизации Диксона . общее время работы, необходимое для квадратичного сита (для факторизации целого числа n Предполагается, что ), составляет

$e^{(1+o(1)){\sqrt {\ln n\ln \ln n}}}=L_{n}\left[1/2,1\right]$

в L-нотации . Константа e является основанием натурального логарифма.

Подход

Чтобы факторизовать целое число n , метод Ферма влечет за собой поиск одного числа a , n ^1/2 < a < n −1 , такой, что остаток a ² разделенное на n - квадрат. Но их трудно найти. решето состоит из вычисления остатка Квадратичное ² / n для нескольких a , а затем найти их подмножество, произведение которого является квадратом. Это даст равенство квадратов.

Например, рассмотрим попытку факторизовать число 1649. У нас есть: $41^{2}\equiv 32,42^{2}\equiv 115,43^{2}\equiv 200{\pmod {1649}}$. Ни одно из целых чисел $32,115,200$ является квадратом, но произведение $32\cdot 200=80^{2}$ представляет собой квадрат. У нас также был

$32\cdot 200\equiv 41^{2}\cdot 43^{2}=(41\cdot 43)^{2}\equiv 114^{2}{\pmod {1649}}$

с $41\cdot 43\equiv 114{\pmod {1649}}$.Наблюдение, что $32\cdot 200=80^{2}$ таким образом, получается сравнение квадратов

$114^{2}\equiv 80^{2}{\pmod {1649}}.$

Следовательно $114^{2}-80^{2}=(114+80)\cdot (114-80)=194\cdot 34=k\cdot 1649$ для некоторого целого числа $k$. Затем мы можем фактор

$1649=\gcd(194,1649)\cdot \gcd(34,1649)=97\cdot 17$

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

Итак, теперь задача свелась к следующему: по заданному набору целых чисел найти подмножество, произведение которого является квадратом. По основной теореме арифметики любое положительное целое число можно однозначно записать как произведение степеней простых чисел . Мы делаем это в векторном формате; например, факторизация 504 в простой степени равна 2 ³ 3 ² 5 ⁰ 7 ¹ , поэтому он представлен вектором экспоненты (3,2,0,1). Умножение двух целых чисел соответствует сложению их векторов экспонент. Число является квадратом, если его вектор показателя четен по каждой координате. Например, векторы (3,2,0,1) + (1,0,0,1) = (4,2,0,2), поэтому (504)(14) — квадрат. Для поиска квадрата необходимо знание только четности чисел в векторах, поэтому достаточно вычислить эти векторы по модулю 2: (1,0,0,1) + (1,0,0,1) = (0 ,0,0,0).Итак, учитывая набор (0,1)-векторов, нам нужно найти подмножество, которое добавляется к нулевому вектору по модулю 2.

Это задача линейной алгебры, поскольку кольцо $\mathbb {Z} /2\mathbb {Z}$ можно рассматривать как поле Галуа порядка 2, то есть мы можем делить на все ненулевые числа (есть только одно, а именно 1) при вычислении по модулю 2.Это теорема линейной алгебры, согласно которой, если векторов больше, чем количество элементов в каждом векторе, всегда существует линейная зависимость . Его можно найти методом исключения Гаусса .Однако простое возведение многих случайных чисел в квадрат по модулю n дает очень большое количество различных простых множителей, а значит, очень длинные векторы и очень большую матрицу. Хитрость заключается в том, чтобы искать числа a такие, что a ² mod n имеет только небольшие простые делители (это гладкие числа ). Их труднее найти, но использование только гладких чисел делает векторы и матрицы меньшими и более удобными. Квадратичное решето ищет гладкие числа, используя метод, называемый просеиванием , обсуждаемый позже, от которого алгоритм получил свое название.

Алгоритм

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

1. Выберите границу гладкости B . Число π( B ), обозначающее количество простых чисел меньше B , будет контролировать как длину векторов, так и количество необходимых векторов.
2. Используйте просеивание, чтобы найти π( B ) + 1 чисел a _i таких, что b _i = ( a _i ² mod n ) является B -гладкой.
3. Фактор b _i и сгенерируйте векторы экспоненты по модулю 2 для каждого из них.
4. Используйте линейную алгебру, чтобы найти подмножество этих векторов, которые добавляются к нулевому вектору. Умножьте соответствующие значения a _i и дайте результату mod n имя a ; аналогичным образом умножьте b _i вместе, что даст B -гладкий квадрат b ² .
5. Теперь у нас осталось равенство a ² = б ² mod n, из которого мы получаем два квадратных корня из ( a ² mod n ), извлекая квадратный корень из целых чисел b ² а именно b , а другой a вычислен на шаге 4.
6. Теперь у нас есть желаемое тождество: $(a+b)(a-b)\equiv 0{\pmod {n}}$. Вычислите НОД n с разницей (или суммой) a и b . В результате получается фактор, хотя это может быть тривиальный фактор ( n или 1). Если фактор тривиален, попробуйте еще раз с другой линейной зависимостью или другим значением .

Оставшаяся часть этой статьи объясняет детали и расширения этого базового алгоритма.

Как QS оптимизирует поиск совпадений

Квадратичное решето пытается найти пары целых чисел x и y ( x ) (где y ( x ) — функция от x ), удовлетворяющих гораздо более слабому условию, чем x. ² ≡ и ² (мод. н ). Он выбирает набор простых чисел, называемый факторной базой , и пытается найти x такой, что наименьший абсолютный остаток от y ( x ) = x. ² mod n полностью факторизуется по факторной базе. Такие значения y называются гладкими по отношению к факторной базе.

Факторизация значения y ( x ), которое разделяется по факторной базе вместе со значением x , называется отношением . Квадратичное решето ускоряет процесс поиска отношений, принимая x близко к квадратному корню из n . Это гарантирует, что y ( x ) будет меньше и, следовательно, будет иметь больше шансов быть гладким.

$y(x)=\left(\left\lceil {\sqrt {n}}\right\rceil +x\right)^{2}-n{\hbox{ (where }}x{\hbox{ is a small integer)}}$

$y(x)\approx 2x\left\lceil {\sqrt {n}}\right\rceil$

Это означает, что y порядка 2 x [ √ n ]. Однако это также означает, что y растет линейно с увеличением x, умноженного на квадратный корень из n .

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

Частичные отношения и циклы

Даже если для некоторого отношения y ( x ) не является гладким, возможно объединить два из этих частичных отношений , чтобы сформировать полное, если два являются y произведениями одного и того же простого числа (простых чисел) вне факторной базы. [Обратите внимание, что это эквивалентно расширению факторной базы.] Например, если факторная база равна {2, 3, 5, 7} и n = 91, существуют частичные отношения:

${21^{2}\equiv 7^{1}\cdot 11{\pmod {91}}}$

${29^{2}\equiv 2^{1}\cdot 11{\pmod {91}}}$

Умножьте их вместе:

${(21\cdot 29)^{2}\equiv 2^{1}\cdot 7^{1}\cdot 11^{2}{\pmod {91}}}$

и умножим обе части на (11 ⁻¹ ) ² форма 91. 11 ⁻¹ по модулю 91 равно 58, поэтому:

$(58\cdot 21\cdot 29)^{2}\equiv 2^{1}\cdot 7^{1}{\pmod {91}}$

$14^{2}\equiv 2^{1}\cdot 7^{1}{\pmod {91}}$

создавая полное отношение. Такое полное отношение (полученное объединением частичных отношений) называется циклом . Иногда образование цикла из двух частичных отношений приводит непосредственно к конгруэнтности квадратов, но редко.

Проверка гладкости просеиванием

Есть несколько способов проверить гладкость y s. Наиболее очевидным является пробное разделение , хотя это увеличивает время выполнения этапа сбора данных. Другой метод, получивший некоторое признание, — это метод эллиптических кривых (ECM). процесс, называемый просеиванием На практике обычно используется . Если f ( x ) является полиномом $f(x)=x^{2}-n$ у нас есть

${\begin{aligned}f(x)&=x^{2}-n\\f(x+kp)&=(x+kp)^{2}-n\\&=x^{2}+2xkp+(kp)^{2}-n\\&=f(x)+2xkp+(kp)^{2}\equiv f(x){\pmod {p}}\end{aligned}}$

Таким образом, решение f(x) ≡ 0 (mod p ) для x порождает целую последовательность чисел y, для которой y = f ( x ), все из которых делятся на p . Это нахождение квадратного корня по модулю простого числа, для которого существуют эффективные алгоритмы, такие как алгоритм Шэнкса – Тонелли . (Здесь квадратное решето получило свое название: y — квадратичный многочлен от x , а процесс просеивания работает как решето Эратосфена .)

Решето начинается с обнуления каждой записи в большом массиве A [] байтов. Для каждого p решите квадратное уравнение mod p , чтобы получить два корня α и β , а затем добавьте аппроксимацию log( p ) к каждой записи, для которой y ( x ) = 0 mod p ... то есть A [ kp + α ] и A [ kp + β ]. Также необходимо решить квадратное уравнение по модулю малых степеней p , чтобы распознать числа, делящиеся на малые степени простого факторного числа.

В конце факторной базы любой A [], содержащий значение выше порога примерно log( x ² − n ) будет соответствовать значению y ( x ), которое разделяется по факторной базе. Информация о том, какие именно простые числа делят y ( x ), была утеряна, но она имеет только небольшие множители, и существует много хороших алгоритмов для факторизации числа, которые, как известно, имеют только небольшие множители, такие как пробное деление на маленькие простые числа, SQUFOF , Pollard rho и ECM, которые обычно используются в той или иной комбинации.

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

Пример базового сита

В этом примере будет продемонстрировано стандартное квадратичное решето без логарифмической оптимизации или простых степеней. Пусть число, которое нужно факторизовать, N = 15347, поэтому максимальный квадратный корень из N равен 124. Поскольку N мало, достаточно базового многочлена: y ( x ) = ( x + 124) ² − 15347.

Сбор данных

Поскольку N мало, необходимо только четыре простых числа. Первые четыре простых числа p, для которых 15347 имеет квадратный корень по модулю p, — это 2, 17, 23 и 29 (другими словами, 15347 — это квадратичный вычет по модулю каждого из этих простых чисел). Эти простые числа будут основой для просеивания.

Теперь строим наше сито $V_{X}$ из $Y(X)=(X+\lceil {\sqrt {N}}\rceil )^{2}-N=(X+124)^{2}-15347$ и начнём процесс просеивания для каждого простого числа в базисе, выбирая просеивать первые 0 ≤ X < 100 из Y(X):

${\begin{aligned}V&={\begin{bmatrix}Y(0)&Y(1)&Y(2)&Y(3)&Y(4)&Y(5)&\cdots &Y(99)\end{bmatrix}}\\&={\begin{bmatrix}29&278&529&782&1037&1294&\cdots &34382\end{bmatrix}}\end{aligned}}$

Следующим шагом будет выполнение сита. Для каждого p в нашей факторной базе $\lbrace 2,17,23,29\rbrace$ решить уравнение

$Y(X)\equiv (X+\lceil {\sqrt {N}}\rceil )^{2}-N\equiv 0{\pmod {p}}$

найти элементы массива V , которые делятся на p .

Для $p=2$ решать $(X+124)^{2}-15347\equiv 0{\pmod {2}}$ чтобы получить решение $X\equiv {\sqrt {15347}}-124\equiv 1{\pmod {2}}$.

Таким образом, начиная с X=1 и увеличивая на 2, каждая запись будет делиться на 2. Разделив каждую из этих записей на 2, получим

$V={\begin{bmatrix}29&139&529&391&1037&647&\cdots &17191\end{bmatrix}}$

Аналогично для остальных простых чисел p в $\lbrace 17,23,29\rbrace$ уравнение $X\equiv {\sqrt {15347}}-124{\pmod {p}}$ решено. Обратите внимание, что для каждого p > 2 будет 2 результирующих линейных уравнения из-за наличия 2 модульных квадратных корней.

${\begin{aligned}X&\equiv {\sqrt {15347}}-124&\equiv 8-124&\equiv 3{\pmod {17}}\\&&\equiv 9-124&\equiv 4{\pmod {17}}\\X&\equiv {\sqrt {15347}}-124&\equiv 11-124&\equiv 2{\pmod {23}}\\&&\equiv 12-124&\equiv 3{\pmod {23}}\\X&\equiv {\sqrt {15347}}-124&\equiv 8-124&\equiv 0{\pmod {29}}\\&&\equiv 21-124&\equiv 13{\pmod {29}}\\\end{aligned}}$

Каждое уравнение $X\equiv a{\pmod {p}}$ приводит к $V_{x}$ делится на p в точке x = a и каждом p -м значении после этого. Разделив V на p на a , a + p , a +2 p , a +3 p и т. д., для каждого простого числа в базисе находятся гладкие числа, являющиеся произведениями уникальных простых чисел (первых степеней).

$V={\begin{bmatrix}1&139&23&1&61&647&\cdots &17191\end{bmatrix}}$

Любая запись V , равная 1, соответствует гладкому числу. С $V_{0}$, $V_{3}$, и $V_{71}$ равен единице, это соответствует:

Х + 124	И	факторы
124	29	2 0 • 17 0 • 23 0 • 29 1
127	782	2 1 • 17 1 • 23 1 • 29 0
195	22678	2 1 • 17 1 • 23 1 • 29 1

Матричная обработка

гладкие числа Y со свойством Поскольку найдены $Y\equiv Z^{2}{\pmod {N}}$остальная часть алгоритма эквивалентна любому другому варианту метода факторизации Диксона .

Запись показателей произведения подмножества уравнений

${\begin{aligned}29&=2^{0}\cdot 17^{0}\cdot 23^{0}\cdot 29^{1}\\782&=2^{1}\cdot 17^{1}\cdot 23^{1}\cdot 29^{0}\\22678&=2^{1}\cdot 17^{1}\cdot 23^{1}\cdot 29^{1}\\\end{aligned}}$

как матрица ${\pmod {2}}$ дает:

$S\cdot {\begin{bmatrix}0&0&0&1\\1&1&1&0\\1&1&1&1\end{bmatrix}}\equiv {\begin{bmatrix}0&0&0&0\end{bmatrix}}{\pmod {2}}$

Решение уравнения дается левым нулевым пространством , просто

$S={\begin{bmatrix}1&1&1\end{bmatrix}}$

Таким образом, произведение всех трех уравнений дает квадрат (по модулю N).

$29\cdot 782\cdot 22678=22678^{2}$

и

$124^{2}\cdot 127^{2}\cdot 195^{2}=3070860^{2}$

Итак, алгоритм найден

$22678^{2}\equiv 3070860^{2}{\pmod {15347}}$

Проверка результата дает НОД(3070860 - 22678, 15347) = 103, нетривиальный коэффициент равен 15347, а второй равен 149.

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

Множественные полиномы

На практике множество разных полиномов используется для y , поэтому, когда y ( x ) начинает становиться большим, что приводит к плохой плотности сглаженного y , этот рост можно сбросить путем переключения полиномов. Как обычно, мы выбираем y ( x ) как квадрат по модулю n , но теперь в виде

$$y(x)=(Ax+B)^{2}-n\qquad A,B\in \mathbb {Z} .$$

$B$ выбирается таким, что $B^{2}=n{\pmod {A}}$, так $B^{2}-n=AC$ для некоторых $C$. Полином y(x) тогда можно записать как $y(x)=A\cdot (Ax^{2}+2Bx+C)$. Если А — квадрат или гладкое число, то только множитель $(Ax^{2}+2Bx+C)$ необходимо проверить гладкость.

Этот подход, называемый Multiple Polynomial Quadratic Sieve (MPQS), идеально подходит для распараллеливания , поскольку каждому процессору, участвующему в факторизации, можно задать n , факторную базу и набор полиномов, и у него не будет необходимости взаимодействовать с центральным процессором. процессор, пока он не завершит просеивание своих полиномов.

Большие простые числа

Одно большое простое число

Если после деления на все множители меньше А оставшаяся часть числа (сомножитель) меньше А ² , то этот сомножитель должен быть простым. По сути, его можно добавить к факторной базе, отсортировав список отношений по кофакторам. Если y(a) = 7*11*23*137 и y(b) = 3*5*7*137, то y(a)y(b) = 3*5*11*23 * 7 ² * 137 ² . Это работает за счет уменьшения порога записей в массиве просеивания, выше которого выполняется полная факторизация.

Более большие простые числа

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

Параметры из реалистичного примера

Чтобы проиллюстрировать типичный выбор параметров для реалистичного примера реальной реализации, включая оптимизацию множественных полиномов и больших простых чисел, инструмент msieve был запущен на 267-битном полупростом процессоре и выдал следующие параметры:

• Ограничение пробного факторинга: 27 бит.
• Интервал сита (на полином): 393216 (12 блоков размером 32768)
• Граница гладкости: 1300967 (50294 простых чисел)
• Количество факторов для коэффициентов полинома A : 10 (см. Множественные полиномы выше).
• Граница большого простого числа: 128795733 (26 бит) (см. Большие простые числа выше).
• Найдено сглаженных значений: 25952 путем прямого просеивания, 24462 путем объединения чисел с большими простыми числами.
• Итоговый размер матрицы: 50294×50414, уменьшен фильтрацией до 35750×35862.
• Найдено нетривиальных зависимостей: 15
• Общее время (на UltraSPARC III 1,6 ГГц): 35 минут 39 секунд.
• Максимальный используемый объем памяти: 8 МБ

Факторинговые записи

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

2 апреля 1994 г. факторизация RSA-129 была завершена с использованием QS. Это было 129-значное число, произведение двух больших простых чисел: одно из 64 цифр, другое из 65 цифр. Факторная база для этой факторизации содержала 524339 простых чисел. Фаза сбора данных заняла 5000 MIPS-лет и осуществлялась распределенным способом через Интернет. Собранные данные составили 2 ГБ . Фаза обработки данных заняла 45 часов на Bellcore (массово-параллельный) компании (теперь Telcordia Technologies ) суперкомпьютере MasPar . Это была крупнейшая опубликованная факторизация с использованием алгоритма общего назначения до тех пор, пока NFS не использовалась для факторизации RSA-130 , завершенной 10 апреля 1996 года. Все числа RSA, факторизованные с тех пор, были факторизованы с использованием NFS.

Текущий рекорд факторизации QS — это 140-значный (463-битный) RSA-140, который был факторизован Патриком Консором в июне 2020 года с использованием примерно 6000 основных часов в течение 6 дней.

Реализации

• PPMPQS и PPSIQS
• mpqs
• SIMPQS, заархивировано 6 мая 2020 г. на Wayback Machine, представляет собой быструю реализацию самоинициализирующегося квадратичного сита с множественными полиномами, написанного Уильямом Хартом. Он обеспечивает поддержку варианта с большими простыми числами и использует реализацию блока Джейсона Пападопулоса Ланчоса для этапа линейной алгебры. SIMPQS доступен как команда qsieve в пакете компьютерной алгебры SageMath , является частью Fast Library for Number Theory или может быть загружен в исходной форме. SIMPQS оптимизирован для использования на машинах Athlon и Opteron, но будет работать на наиболее распространенных 32- и 64-битных архитектурах. Он полностью написан на C.
• апплет факторинга Дарио Альперна, который использует квадратичное решето при выполнении определенных условий.
• Пакет компьютерной алгебры PARI/GP включает реализацию самоинициализирующегося квадратичного сита с множественными полиномами, реализующего вариант с большими простыми числами. Он был адаптирован Томасом Папаниколау и Ксавье Робло на основе сита, написанного для проекта LiDIA. Схема самоинициализации основана на идее из диссертации Томаса Сосновского.
• Вариант квадратичного сита доступен в пакете компьютерной алгебры MAGMA . Он основан на реализации Арьена Ленстры 1995 года, использованной в его программе «факторинг по электронной почте».
• msieve — реализация квадратичного решета с множественным полиномом с поддержкой одиночных и двойных больших простых чисел, написанная Джейсоном Пападопулосом. Доступны исходный код и двоичный файл Windows.
• YAFU , написанный Беном Бухроу, вероятно, является самой быстрой доступной реализацией квадратичного решета. Например, RSA-100 был учтен менее чем за 15 минут на четырех ядрах процессора Xeon 6248 с частотой 2,5 ГГц. Все критически важные подпрограммы используют инструкции AVX2 или AVX-512 SIMD- для процессоров AMD или Intel. Он использует блочный код Ланцоша Джейсона Пападопулоса. Доступны исходный код и двоичные файлы для Windows и Linux.
• Ariel , простая реализация квадратичного решета на Java для дидактических целей.
• Библиотека java-math-library содержит, вероятно, самое быстрое квадратичное решето, написанное на Java (преемник PSIQS 4.0).
• Java QS — проект Java с открытым исходным кодом, содержащий базовую реализацию QS. Выпущено 4 февраля 2016 года Ильей Газманом.
• C Quadratic Sieve — факторизатор, полностью написанный на C и содержащий реализацию самоинициализирующегося квадратичного решета. Проект вдохновлен факторизатором FLINT Уильяма Харта. Исходный код, выпущенный в 2022 году Мишелем Леонардом, не опирается на внешнюю библиотеку, он способен разлагать 240-битные числа за минуту и ​​300-битные числа за 2 часа.
• Пакет RcppBigIntAlgos Джозефа Вуда обеспечивает эффективную реализацию квадратичного сита с множественными полиномами для языка программирования R. Он написан на C++ и способен легко факторизовать 100-значные полупростые числа . Например, 300-битное полупростое число (91 цифра) было учтено за 1 час, а RSA-100 — менее чем за 10 часов на MacBook Air с процессором Apple M2.

См. также

• Факторизация эллиптической кривой Ленстры
• тест на простоту

Ссылки

• Крэндалл, Ричард ; Померанс, Карл (2001). «Раздел 6.1: Метод факторизации квадратичного сита». Простые числа: вычислительная перспектива (1-е изд.). Спрингер. стр. 227–244. ISBN  0-387-94777-9 .
• Вагстафф, Сэмюэл С. младший (2013). Радость факторинга . Провиденс, Род-Айленд: Американское математическое общество . стр. 195–202. ISBN  978-1-4704-1048-3 .
• Контини, Скотт Патрик (1997). Факторизация целых чисел с помощью самоинициализирующегося квадратичного решета (PDF) (магистерская диссертация). Университет Джорджии. Архивировано из оригинала (PDF) 5 апреля 2015 г. Описывает множество деталей практической реализации.

Другие внешние ссылки

• Справочная статья «Алгоритм факторизации квадратичного решета». Эрика Ландквиста