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

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

Варианты

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

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

Второй вариант называется SQUFOF (акроним от английского SQUare FOrm Factorization) и использует группу классов бинарных квадратичных форм с положительным дискриминантом. В нём также происходит нахождение амбиговой формы и разложение дискриминанта на множители.

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

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

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

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

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

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

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

4. Выполним цикл редуцирований , пока значение второго коэффициента не стабилизируется . Число итераций m этого цикла должно быть примерно равно половине от числа итераций первого цикла. Последнее значение a даст делитель числа n (возможно тривиальный). Метод квадратичных форм Шенкса имеет асимптотическую сложность и является, как уже упоминалось раньше, наиболее быстрым методом в классе алгоритмов для разложения чисел длиной до 18 десятичных знаков.

Примечания

Литература

• Василенко О. Н. Теоретико-числовые алгоритмы в криптографии, МЦНМО, 2003

См. также

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