Факторизация форм квадрата Шанкса

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

Успех метода Ферма зависит от нахождения целых чисел $x$ и $y$ такой, что $x^{2}-y^{2}=N$, где $N$ целое число, которое нужно факторизовать. Улучшение (замеченное Kraitchik ) — поиск целых чисел $x$ и $y$ такой, что $x^{2}\equiv y^{2}{\pmod {N}}$. Находим подходящую пару $(x,y)$ не гарантирует факторизацию $N$, но это подразумевает, что $N$ является фактором $x^{2}-y^{2}=(x-y)(x+y)$, и есть большая вероятность, что простые делители $N$ распределены между этими двумя факторами, так что вычисление наибольшего общего делителя $N$ и $x-y$ даст нетривиальный коэффициент $N$.

Практический алгоритм поиска пар $(x,y)$ которые удовлетворяют $x^{2}\equiv y^{2}{\pmod {N}}$ был разработан Шанксом, который назвал его факторизацией квадратных форм или SQUFOF. Алгоритм может быть выражен через цепные дроби или через квадратичные формы. Хотя сейчас доступны гораздо более эффективные методы факторизации, SQUFOF имеет то преимущество, что он достаточно мал, чтобы его можно было реализовать на программируемом калькуляторе. Шанкс запрограммировал его на HP-65 , выпущенном в 1974 году, который имеет память только для девятизначных чисел и позволяет программировать только 100 шагов/нажатий клавиш. Существуют версии алгоритма, использующие мало памяти, и версии, хранящие список значений, которые выполняются быстрее.

В 1858 году чешский математик Вацлав Шимерка использовал метод, аналогичный SQUFOF, для факторинга. $(10^{17}-1)/9$ $=$ $11111111111111111$ $=$ $2071723\cdot 5363222357$.

Алгоритм

Примечание. Эта версия алгоритма работает в некоторых примерах, но часто зацикливается.

В этой версии список не используется.

Вход : $N$, целое число, подлежащее факторизации, которое не должно быть ни простым числом , ни полным квадратом , а также небольшим положительным целым числом, $k$.

Выход : нетривиальный фактор $N$.

Алгоритм:

Инициализировать $i=0,P_{0}=\lfloor {\sqrt {kN}}\rfloor ,Q_{-1}=1,Q_{0}=kN-P_{0}^{2}.$

Повторить

$i=i+1,b_{i}=\left\lfloor {\frac {P_{0}+P_{i-1}}{Q_{i-1}}}\right\rfloor ,P_{i}=b_{i}Q_{i-1}-P_{i-1},Q_{i}=Q_{i-2}+b_{i}(P_{i-1}-P_{i})$

до $Q_{i}$ является идеальным квадратом при некотором нечетном значении $i$.

Начните вторую фазу (обратный цикл).

Инициализировать $b_{0}=\left\lfloor {\frac {P_{0}-P_{i}}{\sqrt {Q_{i}}}}\right\rfloor$, $Q_{-1}={\sqrt {Q_{i}}}$, и $P_{0}=b_{0}{\sqrt {Q_{i}}}+P_{i}$, где $P_{0},P_{i}$, и $Q_{i}$ относятся к предыдущему этапу. $b_{0}$ используется при расчете $P_{0}$ это недавно вычисленное значение $b_{0}$.

Набор $i=0$ и $Q_{0}={\frac {kN-P_{0}^{2}}{Q_{-1}}}$, где $P_{0}$ это недавно вычисленное значение $P_{0}$.

Повторить

$i=i+1,b_{i}=\left\lfloor {\frac {P_{0}+P_{i-1}}{Q_{i-1}}}\right\rfloor ,P_{i}=b_{i}Q_{i-1}-P_{i-1},Q_{i}=Q_{i-2}+b_{i}(P_{i-1}-P_{i})$

до $P_{i}=P_{i-1}.$

Тогда, если $f=\gcd(N,P_{i})$ не равен $1$ и не равен $N$, затем $f$ является нетривиальным фактором $N$. В противном случае попробуйте другое значение $k$.

Метод Шанкса имеет временную сложность $O({\sqrt[{4}]{N}})$.

Стивен С. Макмат написал более подробное обсуждение математики метода Шанкса, вместе с доказательством его правильности.

Пример

Позволять $N=11111$

$Q_{-1}=1$

Цикл вперед
$i$	$b_{i}$	$P_{i}$	$Q_{i}$
$0$	${\displaystyle }$	$105$	$86$
$1$	$2$	$67$	$77$
$2$	$2$	$87$	$46$
$3$	$4$	$97$	$37$
$4$	$5$	$88$	$91$
$5$	$2$	$94$	$25$

Здесь $Q_{5}=25$ — идеальный квадрат, поэтому первая фаза заканчивается.

Для второго этапа установите $Q_{-1}={\sqrt {25}}=5$. Затем:

Обратный цикл
$i$	$b_{i}$	$P_{i}$	$Q_{i}$
$0$	$2$	$104$	$59$
$1$	$3$	$73$	$98$
$2$	$1$	$25$	$107$
$3$	$1$	$82$	$41$
$4$	$4$	$82$	${\displaystyle }$

Здесь $P_{3}=P_{4}=82$, так что вторая фаза заканчивается. Теперь посчитаем $gcd(11111,82)=41$, что является фактором $11111$.

Таким образом, $N=11111=41\cdot 271$.

Пример реализации

Ниже приведен пример функции C для выполнения факторизации SQUFOF целого числа без знака длиной не более 64 бит без переполнения переходных операций.

#include <inttypes.h>
#define nelems(x) (sizeof(x) / sizeof((x)[0]))

const int multiplier[] = {1, 3, 5, 7, 11, 3*5, 3*7, 3*11, 5*7, 5*11, 7*11, 3*5*7, 3*5*11, 3*7*11, 5*7*11, 3*5*7*11};

uint64_t SQUFOF( uint64_t N )
{
    uint64_t D, Po, P, Pprev, Q, Qprev, q, b, r, s;
    uint32_t L, B, i;
    s = (uint64_t)(sqrtl(N)+0.5);
    if (s*s == N) return s;
    for (int k = 0; k < nelems(multiplier) && N <= UINT64_MAX/multiplier[k]; k++) {
        D = multiplier[k]*N;
        Po = Pprev = P = sqrtl(D);
        Qprev = 1;
        Q = D - Po*Po;
        L = 2 * sqrtl( 2*s );
        B = 3 * L;
        for (i = 2 ; i < B ; i++) {
            b = (uint64_t)((Po + P)/Q);
            P = b*Q - P;
            q = Q;
            Q = Qprev + b*(Pprev - P);
            r = (uint64_t)(sqrtl(Q)+0.5);
            if (!(i & 1) && r*r == Q) break;
            Qprev = q;
            Pprev = P;
        };
        if (i >= B) continue;
        b = (uint64_t)((Po - P)/r);
        Pprev = P = b*r + P;
        Qprev = r;
        Q = (D - Pprev*Pprev)/Qprev;
        i = 0;
        do {
            b = (uint64_t)((Po + P)/Q);
            Pprev = P;
            P = b*Q - P;
            q = Q;
            Q = Qprev + b*(Pprev - P);
            Qprev = q;
            i++;
        } while (P != Pprev);
        r = gcd(N, Qprev);
        if (r != 1 && r != N) return r;
    }
    return 0;
}

Ссылки

• Д.А. Бьюэлл (1989). Бинарные квадратичные формы . Спрингер-Верлаг. ISBN  0-387-97037-1 .
• Д. М. Брессу (1989). Факторизация и тестирование на простоту . Спрингер-Верлаг. ISBN  0-387-97040-1 .
• Ризель, Ганс (1994). Простые числа и компьютерные методы факторизации (2-е изд.). Биркгаузер. ISBN  0-8176-3743-5 .
• Сэмюэл С. Вагстафф-младший (2013). Радость факторинга . Провиденс, Род-Айленд: Американское математическое общество. стр. 163–168. ISBN  978-1-4704-1048-3 .

Внешние ссылки

• Дэниел Шэнкс: Анализ и улучшение метода факторизации цепной дроби (расшифровка С. МакМата, 2004 г.)
• Дэниел Шэнкс: Заметки SQUFOF (расшифровка С. МакМата, 2004 г.)
• Стивен С. МакМат: Параллельная факторизация целых чисел с использованием квадратичных форм , 2005 г.
• С. МакМэт, Ф. Крэбб, Д. Джойнер: Цепные дроби и параллельные SQUFOF , 2005 г.
• Джейсон Гауэр, Сэмюэл Вагстафф: Факторизация квадратной формы (опубликовано)
• Алгоритм факторинга SQUFOF Шанкса
• Java-математическая библиотека