Processing math: 100%

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

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

История


 Другое название алгоритма — SQUFOF (акроним от английского — SQUareFOrm Factorization), что означает факторизация методом квадратичныхформ. Данный подход был достаточно успешным на протяжении многих лет и,как следствие, довольно много различных модификаций и реализаций можнонайти на эту тему в литературе. Большинство методов являются сложными изапутанными, особенно в том случае, когда необходима реализация методана компьютере. В результате чего, многие варианты алгоритмов не пригодныдля реализации. Однако в 1975 году Даниель Шенкс предложил создатьалгоритм, который можно реализовать и использовать не только накомпьютере, но и на простом мобильном телефоне.
 Хотя Шенкс описал другие алгоритмы для факторизации целых чисел, поSQUFOF он ничего не опубликовал. Он предоставил лекции по данной теме иобъяснил основную суть своего метода довольно небольшому кругу людей.Некоторые работы других ученых обсуждали алгоритм, но ни одна несодержит подробный анализ. Также интересно то, что в своем методе Шенксделает довольно большое количество предположений, которые, к сожалению,остались без доказательства. В работе представлены результаты некоторыхэкспериментов, которые свидетельствуют, что многие предположения имеютместо быть. В итоге, основываясь на этих упрощающих предположениях,Шенксу удалось создать SQUFOF.

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


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

f(x,y)=ax2+bxy+cy2=(xy)(ab0c)(xy).\\
 В методе Шенкса используются только неопределенные формы. Под Δбудем понимать дискриминант квадратичной формы. Будем говорить, чтоквадратичная форма f представляет целое число m\Z, еслисуществуют такие целые числа x0,y0, что выполнено равенство:f(x0,y0)=ax20+bx0y0+cy20. В случае если выполнено равенствоgcd(x0,y0)=1, то представление называется примитивным.
 Для любой неопределенной квадратичной формыf=(a,b,c) можно определитьоператор редукции как:

ρ(a,b,c)=(c,r(b,c),r(b,c)2Δ4c),гдеr(b,c) — определено, как целое число r, однозначно определяемоеусловиями:
 :\# r+b0mod(2c)
 :\# |c|<r<|c|,ifΔ<|c|
 :\#Δ2|c|<r<Δ,if|c|<Δ
 Результат применения оператора ρ к форме f nраз записывается ввиде ρn(f). Также определен оператор ρ1 как:

ρ1(a,b,c)=(r(b,c)2Δ4c,r(b,c),c),где r(b,c) определен так же как и в прошлом случае. Заметим, что врезультате применения операторов ρ1 и ρ к квадратичнойформе f=(a,b,c) с дискриминантомΔ, полученные квадратичные формы так же будут иметь дискриминантΔ.
 Метод получения редуцированной формы, эквивалентной данной, был найденеще Карлом Гауссом и состоит в последовательном применении оператораредукции g=ρ(f), пока f не станет редуцированной.
Теорема.
 Так же для ясности понимания всех операций с квадратичными формами нампонадобится понятия квадратных, смежных и неоднозначных квадратичныхформ

Варианты


 Идея метода Шенкса состоит в сопоставлении числу n, которое надоразложить, квадратичной бинарной формы f с дискриминантом D=4n, скоторой потом выполняется серия эквивалентных преобразований и переходот формы f к неоднозначной форме (a,b,c). Тогда, gcd(a,b)будет являться делителем n.
 Первый вариант работает с положительно определёнными бинарнымиквадратичными формами заданного отрицательного дискриминанта и в группеклассов форм он находит амбигову форму, которая даёт разложениедискриминанта на множители. Сложность первого варианта составляетO(n1/5+ε) при условии истинности расширенной гипотезыРимана.
 Второй вариант это SQUFOF, он использует группу классов бинарныхквадратичных форм с положительным дискриминантом. В нём также происходитнахождение амбиговой формы и разложение дискриминанта на множители.Сложность SQUFOF составляет O(n1/4+ε) арифметическихопераций; при этом алгоритм работает с целыми числами, не превосходящими2n. Среди алгоритмов факторизации с экспоненциальной сложностьюSQUFOF считается одним из самых эффективных.

Оценкасходимости


 Согласно расчетам, выполненным самим Шенксом, число итераций первого ивторого циклов алгоритма определяется числом w сомножителей числа nи равна примерно:
C2w2n1/4,
 где C константа, равная примерно 2,4 для первого цикла итераций.

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


 Более подробно алгоритм может быть записан в следующем виде:
Вход: Нечетное составное число n, которое требуетсяфакторизовать. Если nmod4=1, заменим n на 2n. Теперьnmod4=2;3. Последнее свойство нужно, чтобы определительквадратичной формы был фундаментальным, что обеспечивает сходимостьметода.
Выход: Нетривиальный делитель n.

 1. Определим исходную квадратичную форму f=(1,2b,b2D), сдискриминантом D=4n, где b=bnc.


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


 3. Вычислим квадратный корень изf:g=(a,b,c)=f1/2


 4. Выполним цикл редуцирований p=ρ(g), пока значение второгокоэффициента не стабилизируется bi+1=bi. Число итераций mэтого цикла должно быть примерно равно половине от числа итерацийпервого цикла. Последнее значение a даст делитель числа n(возможно тривиальный).

Реализацияалгоритма


 Теперь опишем алгоритм для реализации на компьютере. Отметим, что хотятеоретическая часть алгоритма связана с эквивалентными преобразованиямиквадратичных форм, практическая часть алгоритма выполняется на основевычисления коэффициентов P,Q,r метода непрерывных дробей без обращенияк формам. Каждая итерация цикла соответствует одной операции примененияоператора редукции к соответствующей форме. При необходимости можновосстановить соответствующие формы fk=(ak,bk,ck) по формулам:(ak,bk,ck)=((1)k1Qk1,2Pk,(1)kQk)
Вход: Составное число n
Выход: Нетривиальный делитель n

  • Инициализация алгоритма.
    • Проверим, является ли n полным квадратом. Если да, то вычислим d=n, и завершим вычисление. Иначе, перейдем к следующему пункту.
    • Если n1(mod4), тогда заменим n на 2n. Определим D=4n,q0=bDc.
    • Определим исходные значения параметров P,Q,r:

P0=0,Q0=1,r0=P1=bnc,Q1=nr20,r1=b2r0/Q1c.

  • Первый цикл
    • Pk=rk1Qk1Pk1,Qk=Qk2+(Pk1Pk)rk1,rk=bPk+bncQkc,k2.
    • Продолжаем вычисления коэффициентов Pk,Qkrk до тех пор, пока не найдем Q\_k, являющееся полным квадратом. Это должно произойти при некотором k. Пусть Qk=d2 для целого d>0. Перейдем к следующему циклу.


  • Второй цикл.
    • начнем цикл вычислений новых параметров Pj,Qj,rj. Формулы для реализации второго цикла останутся такими же, как раньше. Изменятся только начальные значения параметров P,Q,r:
    • P0=Pk,Q0=d,r0=bP0+bncQ0c,P1=r0Q0P0,Q1=(NP21)/Q0.
    • Вычисление следует продолжать, пока два подряд идущих значения Pj,Pj+1 не окажутся равными. Тогда, значение Qj даст искомый делитель числа n. Описание алгоритма Шенкса закончено.

 Как уже было упомянуто, это не единственная реализация этого алгоритма.Так же реализации алгоритма можно найти здесь

Пример факторизациичисла


 Применим данный метод для факторизации числа N=22117019
Цикл №2
Gi
i
0
1
2
3
4
5
6
7
8

 Теперь можно увидеть во втором цикле, что P7=P8.Следовательно число N=22117019=44514969.

Применения


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