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

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

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

ИсторияПравить

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

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

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

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

$f(x,y)=ax^{2}+bxy+cy^{2}={\begin{pmatrix}x&y\end{pmatrix}}{\begin{pmatrix}a&b\\0&c\end{pmatrix}}{\begin{pmatrix}x\\y\end{pmatrix}}.$ 

В методе Шенкса используются только неопределенные формы. Под $\mathrm{\Delta <!--\; \Delta \; -->}$$\Delta$  будем понимать дискриминант квадратичной формы. Будем говорить, что квадратичная форма $f$$f$  представляет целое число $m\in <!--\; \in \; -->\mathbb{Z}$$m\in \mathbb {Z}$ , если существуют такие целые числа $x_0,y_0$$x_{0},y_{0}$ , что выполнено равенство: $f(x_0,y_0)=a{x}_0^2+b{x}_0{y}_0+c{y}_0^2$$f(x_{0},y_{0})=ax_{0}^{2}+bx_{0}y_{0}+cy_{0}^{2}$ . В случае если выполнено равенство $gcd(x_0,y_0)=1$$\gcd(x_{0},y_{0})=1$ , то представление называется примитивным.

Для любой неопределенной квадратичной формы $f={\begin{pmatrix}a,&b,&c\end{pmatrix}}$  можно определить оператор редукции как:

$\rho {\begin{pmatrix}a,&b,&c\end{pmatrix}}={\begin{pmatrix}c,&r(-b,c),&{\frac {r(-b,c)^{2}-\Delta }{4c}}\end{pmatrix}}$ ,где $r(-<!--\; -\; -->b,c)$$r(-b,c)$  — определено, как целое число $r$$r$ , однозначно определяемое условиями:

1. $r+b\equiv <!--\; \equiv \; -->0\mathrm{mod}(2c)$$r+b\equiv 0\mod (2c)$ 
2. $-|c|<r<|c|,\quad if\quad {\sqrt {\Delta }}<|c|$ 
3. ${\sqrt {\Delta }}-2|c|<r<{\sqrt {\Delta }},\quad if\quad |c|<{\sqrt {\Delta }}$ 

Результат применения оператора $\mathrm{\rho <!--\; \rho \; -->}$$\rho$  к форме $f$$f$  $n$$n$ раз записывается в виде ${\mathrm{\rho <!--\; \rho \; -->}}^n(f)$$\rho ^{n}(f)$ . Также определен оператор ${\mathrm{\rho <!--\; \rho \; -->}}^{-<!--\; -\; -->1}$$\rho ^{-1}$  как:

$\rho ^{-1}{\begin{pmatrix}a,&b,&c\end{pmatrix}}={\begin{pmatrix}{\frac {r(-b,c)^{2}-\Delta }{4c}},&r(-b,c),&c\end{pmatrix}}$ , где $r(-<!--\; -\; -->b,c)$$r(-b,c)$  определен так же как и в прошлом случае. Заметим, что в результате применения операторов ${\mathrm{\rho <!--\; \rho \; -->}}^{-<!--\; -\; -->1}$$\rho ^{-1}$  и $\mathrm{\rho <!--\; \rho \; -->}$$\rho$  к квадратичной форме $f={\begin{pmatrix}a,&b,&c\end{pmatrix}}$  с дискриминантом $\mathrm{\Delta <!--\; \Delta \; -->}$$\Delta$ , полученные квадратичные формы так же будут иметь дискриминант $\mathrm{\Delta <!--\; \Delta \; -->}$$\Delta$ .

Метод получения редуцированной формы, эквивалентной данной, был найден еще Карлом Гауссом и состоит в последовательном применении оператора редукции $g=\mathrm{\rho <!--\; \rho \; -->}(f)$$g=\rho (f)$ , пока $f$$f$  не станет редуцированной.

Теорема.

Каждая форма $f$$f$  эквивалентна некоторой редуцированной форме, и любая редуцированная форма для $f$$f$  равна ${\mathrm{\rho <!--\; \rho \; -->}}^k(f)$$\rho ^{k}(f)$  для некоторого положительного $k$$k$ . Если $f$$f$  - редуцирована, то $\mathrm{\rho <!--\; \rho \; -->}(f)$$\rho (f)$  также редуцирована.

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

ВариантыПравить

Идея метода Шенкса состоит в сопоставлении числу $n$$n$ , которое надо разложить, квадратичной бинарной формы $f$$f$  с дискриминантом $D=4n$$D=4n$ , с которой потом выполняется серия эквивалентных преобразований и переход от формы $f$$f$  к неоднозначной форме $(a^{\prime },b^{\prime },c^{\prime })$$(a',b',c')$ . Тогда, $gcd(a^{\prime },b^{\prime })$$\gcd(a',b')$  будет являться делителем $n$$n$ .

Первый вариант работает с положительно определёнными бинарными квадратичными формами заданного отрицательного дискриминанта и в группе классов форм он находит амбигову форму, которая даёт разложение дискриминанта на множители. Сложность первого варианта составляет $O(n^{1/5+\mathrm{\epsilon <!--\; \epsilon \; -->}})$$O(n^{1/5+\varepsilon })$  при условии истинности расширенной гипотезы Римана.

Второй вариант это SQUFOF, он использует группу классов бинарных квадратичных форм с положительным дискриминантом. В нём также происходит нахождение амбиговой формы и разложение дискриминанта на множители. Сложность SQUFOF составляет $O(n^{1/4+\mathrm{\epsilon <!--\; \epsilon \; -->}})$$O(n^{1/4+\varepsilon })$  арифметических операций; при этом алгоритм работает с целыми числами, не превосходящими $2\sqrt{n}$$2{\sqrt {n}}$ . Среди алгоритмов факторизации с экспоненциальной сложностью SQUFOF считается одним из самых эффективных.

Оценка сходимостиПравить

Согласно расчетам, выполненным самим Шенксом, число итераций первого и второго циклов алгоритма определяется числом $w$$w$  сомножителей числа $n$$n$  и равна примерно:

$\frac{C}{2^w-<!--\; -\; -->2}\cdot <!--\; \cdot \; -->n^{1/4},$${\frac {C}{2^{w}-2}}\cdot n^{1/4},$ 

где $C$$C$  — константа, равная примерно 2,4 для первого цикла итераций.

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

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

Вход: Нечетное составное число $n$$n$ , которое требуется факторизовать. Если $n\mathrm{mod}4=1,$$n\!\!\!\mod 4=1,$  заменим $n$$n$  на $2n.$$2n.$  Теперь $n\mathrm{mod}4=2;3.$$n\!\!\!\mod 4=2;3.$  Последнее свойство нужно, чтобы определитель квадратичной формы был фундаментальным, что обеспечивает сходимость метода.

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

1. Определим исходную квадратичную форму $f=(1,2b,b^2-<!--\; -\; -->D)$$f=(1,2b,b^{2}-D)$ , с дискриминантом $D=4n$$D=4n$ , где $b=\mathcal{b}\sqrt{n}\mathcal{c}$$b={\mathcal {b}}{\sqrt {n}}{\mathcal {c}}$ .

2. Выполним цикл редуцирований $f=\mathrm{\rho <!--\; \rho \; -->}(f)$$f=\rho (f)$ , пока форма $f$$f$  не станет квадратной.

3. Вычислим квадратный корень из $f:g=(a^{\mathrm{\prime <!--\; \prime \; -->}},b^{\mathrm{\prime <!--\; \prime \; -->}},c^{\mathrm{\prime <!--\; \prime \; -->}})=f^{1/2}$$f:~g=(a^{\prime },b^{\prime },c^{\prime })=f^{1/2}$ 

4. Выполним цикл редуцирований $p=\mathrm{\rho <!--\; \rho \; -->}(g)$$p=\rho (g)$ , пока значение второго коэффициента не стабилизируется $b_{i+1}^{\prime }=b_i^{\prime }$$b_{i+1}'=b_{i}'$ . Число итераций $m$$m$  этого цикла должно быть примерно равно половине от числа итераций первого цикла. Последнее значение $a^{\mathrm{\prime <!--\; \prime \; -->}}$$a^{\prime }$  даст делитель числа $n$$n$  (возможно тривиальный).

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

Теперь опишем алгоритм для реализации на компьютере. Отметим, что хотя теоретическая часть алгоритма связана с эквивалентными преобразованиями квадратичных форм, практическая часть алгоритма выполняется на основе вычисления коэффициентов $P,Q,r$$P,Q,r$  метода непрерывных дробей без обращения к формам. Каждая итерация цикла соответствует одной операции применения оператора редукции к соответствующей форме. При необходимости можно восстановить соответствующие формы $f_k=(a_k,b_k,c_k)$$f_{k}=(a_{k},b_{k},c_{k})$  по формулам: $(a_k,b_k,c_k)=((-<!--\; -\; -->1{)}^{k-<!--\; -\; -->1}{Q}_{k-<!--\; -\; -->1},2P_k,(-<!--\; -\; -->1{)}^k{Q}_k)$$(a_{k},b_{k},c_{k})=((-1)^{k-1}Q_{k-1},2P_{k},(-1)^{k}Q_{k})$ 

Вход: Составное число $n$$n$ 

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

• Инициализация алгоритма.
  • Проверим, является ли $n$$n$  полным квадратом. Если да, то вычислим $d=\sqrt{n},$$d={\sqrt {n}},$  и завершим вычисление. Иначе, перейдем к следующему пункту.
  • Если $n\equiv <!--\; \equiv \; -->1(mod4),$$n\equiv 1(mod4),$  тогда заменим $n$$n$  на $2n.$$2n.$  Определим $D=4n,q_0=\mathcal{b}\sqrt{D}\mathcal{c}.$$D=4n,~q_{0}={\mathcal {b}}{\sqrt {D}}{\mathcal {c}}.$ 
  • Определим исходные значения параметров $P,Q,r:$$P,Q,r:$ 

$P_0=0,Q_0=1,r_0=P_1=\mathcal{b}\sqrt{n}\mathcal{c},Q_1=n-<!--\; -\; -->r_0^2,r_1=\mathcal{b}2r_0/Q_1\mathcal{c}.$$P_{0}=0,~Q_{0}=1,~r_{0}=P_{1}={\mathcal {b}}{\sqrt {n}}{\mathcal {c}},~Q_{1}=n-r_{0}^{2},r_{1}={\mathcal {b}}2r_{0}/Q_{1}{\mathcal {c}}.$ 

• Первый цикл
  • $P_k=r_{k-<!--\; -\; -->1}\cdot <!--\; \cdot \; -->Q_{k-<!--\; -\; -->1}-<!--\; -\; -->P_{k-<!--\; -\; -->1},Q_k=Q_{k-<!--\; -\; -->2}+(P_{k-<!--\; -\; -->1}-<!--\; -\; -->P_k)\cdot <!--\; \cdot \; -->r_{k-<!--\; -\; -->1},r_k=\mathcal{b}\frac{P_k+\mathcal{b}\sqrt{n}\mathcal{c}}{Q_k}\mathcal{c},k\ge <!--\; \ge \; -->2.$$P_{k}=r_{k-1}\cdot Q_{k-1}-P_{k-1},~Q_{k}=Q_{k-2}+(P_{k-1}-P_{k})\cdot r_{k-1},r_{k}={\mathcal {b}}{\frac {P_{k}+{\mathcal {b}}{\sqrt {n}}{\mathcal {c}}}{Q_{k}}}{\mathcal {c}},~k\geq 2.$ 
  • Продолжаем вычисления коэффициентов $P_k,Q_k{r}_k$$P_{k},~Q_{k}~r_{k}$  до тех пор, пока не найдем Q_k, являющееся полным квадратом. Это должно произойти при некотором $k.$$k.$  Пусть $Q_k=d^2$$Q_{k}=d^{2}$  для целого $d>0.$$d>0.$  Перейдем к следующему циклу.

• Второй цикл.
  • начнем цикл вычислений новых параметров $P_j^{\mathrm{\prime <!--\; \prime \; -->}},Q_j^{\mathrm{\prime <!--\; \prime \; -->}},r_j^{\mathrm{\prime <!--\; \prime \; -->}}.$$P_{j}^{\prime },~Q_{j}^{\prime },~r_{j}^{\prime }.$  Формулы для реализации второго цикла останутся такими же, как раньше. Изменятся только начальные значения параметров $P^{\mathrm{\prime <!--\; \prime \; -->}},Q^{\mathrm{\prime <!--\; \prime \; -->}},r^{\mathrm{\prime <!--\; \prime \; -->}}:$$P^{\prime },~Q^{\prime },~r^{\prime }:$ 
  • $P_0^{\mathrm{\prime <!--\; \prime \; -->}}=-<!--\; -\; -->P_k,Q_0^{\mathrm{\prime <!--\; \prime \; -->}}=d,r_0^{\mathrm{\prime <!--\; \prime \; -->}}=\mathcal{b}\frac{P_0^{\mathrm{\prime <!--\; \prime \; -->}}+\mathcal{b}\sqrt{n}\mathcal{c}}{Q_0^{\mathrm{\prime <!--\; \prime \; -->}}}\mathcal{c},P_1^{\mathrm{\prime <!--\; \prime \; -->}}=r_0^{\mathrm{\prime <!--\; \prime \; -->}}\cdot <!--\; \cdot \; -->Q_0^{\mathrm{\prime <!--\; \prime \; -->}}-<!--\; -\; -->P_0^{\mathrm{\prime <!--\; \prime \; -->}},Q_1^{\mathrm{\prime <!--\; \prime \; -->}}=(N-<!--\; -\; -->P_1^{\mathrm{\prime <!--\; \prime \; -->}2})/Q_0^{\mathrm{\prime <!--\; \prime \; -->}}.$$P_{0}^{\prime }=-P_{k},~Q_{0}^{\prime }=d,~r_{0}^{\prime }={\mathcal {b}}{\frac {P_{0}^{\prime }+{\mathcal {b}}{\sqrt {n}}{\mathcal {c}}}{Q_{0}^{\prime }}}{\mathcal {c}},~P_{1}^{\prime }=r_{0}^{\prime }\cdot Q_{0}^{\prime }-P_{0}^{\prime },~Q_{1}^{\prime }=(N-P_{1}^{\prime 2})/Q_{0}^{\prime }.$ 
  • Вычисление следует продолжать, пока два подряд идущих значения $P_j^{\mathrm{\prime <!--\; \prime \; -->}},P_{j+1}^{\mathrm{\prime <!--\; \prime \; -->}}$$P_{j}^{\prime },~P_{j+1}^{\prime }$  не окажутся равными. Тогда, значение $Q_j$$Q_{j}$  даст искомый делитель числа $n.$$n.$  Описание алгоритма Шенкса закончено.

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

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

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

Цикл №1 $F_i$$F_{i}$  $i$$i$  $(-<!--\; -\; -->1{)}^{i-<!--\; -\; -->1}{Q}_{i-<!--\; -\; -->1}$$(-1)^{i-1}Q_{i-1}$  $2\cdot <!--\; \cdot \; -->P_i$$2\cdot P_{i}$  $(-<!--\; -\; -->1{)}^i{Q}_i$$(-1)^{i}Q_{i}$  $0$$0$  $-<!--\; -\; -->8215$$-8215$  $2\cdot <!--\; \cdot \; -->4702$$2\cdot 4702$  $1$$1$  $1$$1$  $1$$1$  $2\cdot <!--\; \cdot \; -->4702$$2\cdot 4702$  $-<!--\; -\; -->8215$$-8215$  $2$$2$  $-<!--\; -\; -->8215$$-8215$  $2\cdot <!--\; \cdot \; -->3513$$2\cdot 3513$  $1190$$1190$  $3$$3$  $1190$$1190$  $2\cdot <!--\; \cdot \; -->3627$$2\cdot 3627$  $-<!--\; -\; -->7531$$-7531$  $4$$4$  $-<!--\; -\; -->7531$$-7531$  $2\cdot <!--\; \cdot \; -->3904$$2\cdot 3904$  $913$$913$  $5$$5$  $913$$913$  $2\cdot <!--\; \cdot \; -->4313$$2\cdot 4313$  $-<!--\; -\; -->3850$$-3850$  $6$$6$  $-<!--\; -\; -->3850$$-3850$  $2\cdot <!--\; \cdot \; -->3387$$2\cdot 3387$  $2765$$2765$  $7$$7$  $2765$$2765$  $2\cdot <!--\; \cdot \; -->2143$$2\cdot 2143$  $-<!--\; -\; -->6338$$-6338$  $8$$8$  $-<!--\; -\; -->6338$$-6338$  $2\cdot <!--\; \cdot \; -->4195$$2\cdot 4195$  $713$$713$  $9$$9$  $713$$713$  $2\cdot <!--\; \cdot \; -->4361$$2\cdot 4361$  $-<!--\; -\; -->4346$$-4346$  $10$$10$  $-<!--\; -\; -->4346$$-4346$  $2\cdot <!--\; \cdot \; -->4331$$2\cdot 4331$  $773$$773$  $11$$11$  $773$$773$  $2\cdot <!--\; \cdot \; -->4172$$2\cdot 4172$  $-<!--\; -\; -->6095$$-6095$  $12$$12$  $-<!--\; -\; -->6095$$-6095$  $2\cdot <!--\; \cdot \; -->1923$$2\cdot 1923$  $3022$$3022$  $13$$13$  $3022$$3022$  $2\cdot <!--\; \cdot \; -->4121$$2\cdot 4121$  $-<!--\; -\; -->1699$$-1699$  $14$$14$  $-<!--\; -\; -->1699$$-1699$  $2\cdot <!--\; \cdot \; -->4374$$2\cdot 4374$  $1757$$1757$  $15$$15$  $1757$$1757$  $2\cdot <!--\; \cdot \; -->4411$$2\cdot 4411$  $-<!--\; -\; -->1514$$-1514$  $16$$16$  $-<!--\; -\; -->1514$$-1514$  $2\cdot <!--\; \cdot \; -->4673$$2\cdot 4673$  $185$$185$  $17$$17$  $185$$185$  $2\cdot <!--\; \cdot \; -->4577$$2\cdot 4577$  $-<!--\; -\; -->6314$$-6314$  $18$$18$  $-<!--\; -\; -->6314$$-6314$  $2\cdot <!--\; \cdot \; -->1737$$2\cdot 1737$  $3025$$3025$

Цикл №2 $G_i$$G_{i}$  $i$$i$  $(-<!--\; -\; -->1{)}^{i-<!--\; -\; -->1}{Q}_{i-<!--\; -\; -->1}^{\mathrm{\prime <!--\; \prime \; -->}}$$(-1)^{i-1}Q_{i-1}^{\prime }$  $2\cdot <!--\; \cdot \; -->P_i^{\mathrm{\prime <!--\; \prime \; -->}}$$2\cdot P_{i}^{\prime }$  $(-<!--\; -\; -->1{)}^i{Q}_i^{\mathrm{\prime <!--\; \prime \; -->}}$$(-1)^{i}Q_{i}^{\prime }$  $0$$0$  $-<!--\; -\; -->55$$-55$  $2\cdot <!--\; \cdot \; -->4652$$2\cdot 4652$  $8653$$8653$  $1$$1$  $8653$$8653$  $2\cdot <!--\; \cdot \; -->4001$$2\cdot 4001$  $-<!--\; -\; -->706$$-706$  $2$$2$  $-<!--\; -\; -->706$$-706$  $2\cdot <!--\; \cdot \; -->4471$$2\cdot 4471$  $3013$$3013$  $3$$3$  $3013$$3013$  $2\cdot <!--\; \cdot \; -->4568$$2\cdot 4568$  $-<!--\; -\; -->415$$-415$  $4$$4$  $-<!--\; -\; -->415$$-415$  $2\cdot <!--\; \cdot \; -->4562$$2\cdot 4562$  $3145$$3145$  $5$$5$  $3145$$3145$  $2\cdot <!--\; \cdot \; -->1728$$2\cdot 1728$  $-<!--\; -\; -->6083$$-6083$  $6$$6$  $-<!--\; -\; -->6083$$-6083$  $2\cdot <!--\; \cdot \; -->4355$$2\cdot 4355$  $518$$518$  $7$$7$  $518$$518$  $2\cdot <!--\; \cdot \; -->4451$$2\cdot 4451$  $-<!--\; -\; -->4451$$-4451$  $8$$8$  $-<!--\; -\; -->4451$$-4451$  $2\cdot <!--\; \cdot \; -->4451$$2\cdot 4451$  $518$$518$

Теперь можно увидеть во втором цикле, что $P_7^{\mathrm{\prime <!--\; \prime \; -->}}=P_8^{\mathrm{\prime <!--\; \prime \; -->}}.$$P_{7}^{\prime }=P_{8}^{\prime }.$  Следовательно число $N=22117019=4451\cdot <!--\; \cdot \; -->4969.$$N=22117019=4451\cdot 4969.$ 

ПримененияПравить

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

ЛитератураПравить

• Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — Москва: МЦНМО, 2003. — С. 75 — 76. — 328 с. — ISBN 5-94057-103-4. Архивная копия от 27 января 2007 на Wayback Machine
• Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: Учебное пособие. — Казань: Казанский Университет, 2011. — С. 74 — 82. — 190 с.
• D. A. Buell. Binary Quadratic Forms (неопр.). — New York: Springer-Verlag, 1989. — С. 197 — 199. — 247 с. — ISBN 0-387-97037-1.
• Hans Riesel. Prime Numbers and Computer Methods for Factorization. Birkhauser, second edition. — Sweden: Birkhauser, 1994. — С. стр 186 — 192. — ISBN 978-0-8176-8297-2.
• Henri Cohen. A Course in Computational Algebraic Number Theory (англ.). — Springer-Verlag, 1996. — P. 433 — 437. — 534 p. — ISBN 3-540-55640-0.
• Jason E. Gower and Samuel S. Wagstaff, JR. SQUARE FORM FACTORIZATION. — Москва: МЦНМО, 2003. — С. 1—16, 35—36. — 38 с. — ISBN 5-94057-103-4.
• Samuel S. Wagstaff Jr. Cryptanalysis of Number Theoretic Ciphers (англ.). — CRC Press, 2003. — 318 p. — ISBN 978-1584881537.
• Yike Guo,R.L. Grossman. High Performance Data Mining: Scaling Algorithms, Applications and Systems (англ.). — Kluwer Academic Publishers, 1999. — P. 111. — ISBN 0-7923-7745-1.

См. такжеПравить

• Факторизация целых чисел