Processing math: 100%

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

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

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


 Алгоритм пытается найти такие квадраты чисел, которые равны по модулюn (факторизуемое число), что часто приводит к факторизации n.Алгоритм работает в два этапа: этап сбора данных, где он собираетинформацию, которая может привести к равенству квадратов; и этапобработки данных, где он помещает всю собранную информацию в матрицу иобрабатывает её для получения равенства квадратов. Первый этап можетбыть легко распараллелен на много процессов, но второй этап требуетбольшие объемы памяти и его трудно распараллелить.
 Один из простых методов отыскания равных квадратов заключается в том,чтобы выбрать случайное число, возвести его в квадрат и надеяться, чтоостаток от деления на n является квадратом какого-либо другого числа.Например, 802(mod5959)=441=212. Этот способ находит равныеквадраты лишь в редких случаях для больших n, но если он действительнонайдет эти числа, то можно считать, что факторизация завершена. Этотметод похож на метод факторизации Ферма.
 Метод квадратичного решета является модификацией метода разложения намножители Диксона.
 Продолжительность расчёта для квадратичного решета (n - факторизуемоечисло):
O(exp((1+o(1))lognloglogn)).

Подход


 Пусть x mod y обозначает остаток от деления x на y. Вметоде факторизации Ферма в отдельности подбираем число a, чтобыa2 mod n являлось квадратом. Но такоечисло подобрать тяжело. В квадратичном решете мы вычисляемa2 mod n для некоторых a, и затемнаходим такое подмножество, произведение элементов которого являетсяквадратом. Это приведёт к сравнению квадратов.
 Например, 412 mod 1649 = 32, 422 mod1649 = 115, и 432 mod 1649 = 200. Ни один изполученных результатов не является квадратом, но результат произведения(32)(200) = 6400 = 802. С другой стороны, рассмотревпредыдущее произведение по mod 1649, мы получим, что (32)(200) =(412)(432) =((41)(43))2. Так как (41)∙(43) mod 1649 = 114, мыимеем сравнение квадратов: 1142 ≡802 (mod 1649).
 Но как мы решаем проблему, фиксируя множество чисел и, находяподмножество, произведение элементов, которого является квадратом?Начнём с понятия вектор показателей степеней. Например, у нас есть число504. Его разложение на простые множители имеет следующий вид 504 =23325071.Мы могли бы представить это разложение в виде вектора показателейстепеней (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приводит к большому числу различных простых множителей,длинным векторами большой матрице. Чтобы избавиться от этой проблемы, мы специально ищемчисла, такие, что a2 mod n имеет тольконебольшие простые множители (такие числа называются гладкими числами).Их сложнее найти, но использование таких чисел позволяет избежатьбольших векторов и матриц.

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


 В качестве факторной базы B берется множество простых чисел, состоящееиз p=2 и всех таких нечетных простых чисел p, не превосходящихзаданной границы P (которая выбирается из соображений оптимальности),что n — квадратичный вычет по модулю p.
 Множество S целых чисел, в котором ищутся B-числа (B-число —целое число, делящееся только на простые числа из B) выглядитследующим образом:
S={t2n|[n]+1t[n]+A}
 Далее, вместо того, чтобы брать одно за другим s\isinS, и делить егона простые числа из B, берутся одно за другим каждое p\isinB ипроверяется делимость на p (и его степени) одновременно для всехs\isinS. Для построения списка всех простых p, не превосходящихA, можно использовать решето Эратосфена.

Алгоритм


 1. Выбираются границы P и A порядка величиныelognloglogn (далее обозначается как L(n)), такиечто $P 2. Для t=[n]+1, [n]+2,\ldots,[n]+A по порядку в столбец выписываются целыечисла t2n.
 3. Для каждого нечетного простого числа pP вычисляется символЛежандра - проверяется условие (np)=1. Если ононе выполняется, p удаляется из факторной базы.
 4. Предполагая, что p — такое нечетное простое число, что n —квадратичный вычет по модулю p, решается уравнениеt2n(modpβ) для β= 1,2,\ldots . Значенияβ берутся в порядке возрастания пока не окажется, что уравнение неимеет решений t, сравнимых по модулю pβ с каким-либо из чиселв области[n]+1t[n]+A.
 Пусть β — наибольшее из таких чисел, для которых в указаннойобласти найдется число t со свойством t2n(modpβ).
 Пусть t1 и t2 решения t2n(modpβ) иt2t1(modpβ).
 5. При том же значении p просматривается список значений t2n,полученный в п.2. В столбце, соответствующем p, ставится 1 против всехзначений t2n, для которых t отличается от t1 на некотороекратное p. После этого 1 заменяется на 2 для всех таких значенийt2n, что t отличается от t1 на кратное p2 и т. д. доβ. Затем то же самое проделывается с t2 вместо t1.Наибольшее возможное число в столбце — β.
 6. При добавлении очередной единицы к числу в столбце в п.5,соответствующее число t2n делится на p и полученный результатсохраняется.
 7. В столбце под p=2 при n1(mod8) просто ставится 1 противt2n с нечетным t и соответствующее t2n делится на 2. Приn1(mod8) решается уравнение t2=n(mod2β) ирешение продолжается в том же ключе, как при нечетном p.
 8. Когда все указанные действия будут проведены для всех простых чисел,не превосходящих P, следует отбросить все числа t2n, кромеобратившихся в 1 после деления на все степени p, не превосходящих P.В итоге получится таблица, в которой в bi столбце будут содержатьсявсе такие значения t из интервала[[n]+1,[n]+A],что t2n есть B-число, а остальные столбцы будут соответствоватьтем значениям pP, для которых n — квадратичный вычет.
 9. Далее используется обобщенный метод факторизации Ферма (методфакторных баз).

Как метод квадратичного решета оптимизирует поиск равныхквадратов


 Метод квадратичного решета пытается найти пары целых чисел x иy(x) (где y(x) - функция от x) удовлетворяющихгораздо более слабым условием чем x2y2 (mod n). Он выбирает множествопростых чисел называемых факторной базой, и пытается найтиx такой, что самый маленький остаток y(x) =x2 mod n раскладывается на множителифакторной базы. Такие x называются гладкими по отношению кфакторной базе.
 Факторизацией значения y(x) над факторной базой вместе со значением xназывается зависимостью. Квадратическое решето ускоряет процесспоиска зависимостей путём выбора x близко к квадратному корню изn. Это гарантирует что число y(x) будет меньше, и поэтомуимеет больше шансов быть гладким.
y(x)=(n+x)2n (where x is a small integer)
y(x)2xn
 Другой способ увеличения вероятности быть гладким числом заключается вувеличении размера факторной базы. Однако, тогда необходимо найти покрайней мере на одну гладкую связь больше чем количество простыхчисел в базе, чтобы гарантировать существование линейной зависимости.

Пример


 Этот пример демонстрирует стандартное квадратичное решето безлогарифмических оптимизаций. Допустим нам нужно факторизовать числоN = 15347, следовательно наименьшее число, квадрат которогобольше N, равно 124. Значит y(x) = (x +124)2 − 15347.

Сборданных


 Так как N мало, то необходимо только 4 простых числа. Первые 4простых числа p для которых у 15347 есть квадратный корень помодулю p, равны 2, 17, 23, и 29 (Другими словами, 15347 являетсяквадратичным вычетом для этих простых чисел). Эти числа будут базисомдля квадратичного решета.
 Сейчас мы строим наше решето VX изY(X)=(X+N)2N=(X+124)215347 и начнем спросеивания процесса для каждого простого числа в базисе, выбираядля просеивания первые Y(X) 0 ≤ X \textless 100 :
V=[Y(0)Y(1)Y(2)Y(3)Y(4)Y(5)Y(99)]=[292785297821037129434382]
 Следующим шагом является выполнение просеивания. Для каждого р внашей факторной базе {2,17,23,29} решаем уравнение
Y(X)(X+N)2N0(modp)
 чтобы найти записи в массиве V которые делятся на p.
 Для p=2 решаем (X+124)2153470(mod2) чтобы получитьрешение X153471241(mod2).
 Таким образом, начиная с X=1 с шагом 2, каждая запись будет делиться на2. Деление каждой из записей на 2 дает

V=[29139529391103764717191]
 Аналогично для оставшихся простых чисел p в{17,23,29}равенствоX15347124(modp) решено. Обратитевнимание, что для каждого p \textgreater 2 будет 2 результирующихлинейных уравнения, из-за наличия двух квадратных корней по модулю.

 \{begin\{align\}
 \texttt X \& \{equiv \{sqrt\{15347\} - 124 \& \{equiv 8 - 124 \& \{equiv 3\{pmod\{17\} \{\{\\\texttt   \&                           \& \{equiv 9 - 124 \& \{equiv 4\{pmod\{17\} \{\{\\\texttt X \& \{equiv \{sqrt\{15347\} - 124 \& \{equiv 11 - 124 \& \{equiv 2\{pmod\{23\} \{\{\\\texttt   \&                           \& \{equiv 12 - 124 \& \{equiv 3\{pmod\{23\} \{\{\\\texttt X \& \{equiv \{sqrt\{15347\} - 124 \& \{equiv 8  - 124 \& \{equiv 0\{pmod\{29\} \{\{\\\texttt   \&                           \& \{equiv 21 - 124 \& \{equiv 13\{pmod\{29\} \{\{
 \{end\{align\}
 Каждое равенство Xa(modp) приводит к тому, что Vxделится на p при x=a, a+p,a+2p, и т.д.. Делением V на p в a,a+p, a+2p, a+3p, и т.д., длякаждого простого числа в базисе находим гладкие числа.

V=[11392316164717191]
 Элемент из V который равен 1 соответствует гладкому числу. Таккак V0, V3, и V71 раняются 1, то:
X + 124Yfactors
1242920 • 170 •230 • 291
12778221 • 171 •231 • 290
1952267821 • 171 •231 • 291

Обработкаматрицы


 Рассмотрим равенства:

 \{begin\{align\}
 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\{align\}
 и выпишем показатели простых чисел в виде матрицы и решим систему(mod2):


 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=[111]
 Таким образом, произведение всех 3-х уравнений есть квадрат (mod N).

2978222678=226782
 и

124212721952=30708602
 алгоритм находит

22678230708602(mod15347)
 Теперь вычисляем GCD(3070860 - 22678, 15347) = 103, нетривиальныйделитель 15347, другим является 149.

Рекордыфакторизации


 До открытия общего метода решета числового поля (NFS), QS был известенкак самый быстрый алгоритм факторизации общего назначения. Сейчас, уалгоритма факторизации с помощью эллиптических кривых такое же времявыполнения как и в QS (в случае, когда n есть произведение толькодвух простых чисел), но на практике QS быстрее, т.к. он используетоперации одинарной точности вместо операций длинной арифметики, которыеиспользуются в методе эллиптических кривых.
 2 апреля 1994 года, была произведена факторизация RSA-129 методом QS.Это было число длины 129, результат произведения двух простых чисел,одного длиной 64 и другого длиной 65. При этом факторная база состоялаиз 524339 простых чисел. Этап сбора данных произвел 5000 MIPS. Собраннаяинформация занимала 2GB. Этап обработки матрицы занял 45 часов на-овском (сейчас ) суперкомпьютере MasPar. Это было самое большое число,которое в то время могли факторизовать алгоритмом общего назначения.Только 10 апреля 1996 года смогли факторизовать число длины 130 RSAметодом NFS.