Факторизация квадратных форм Шанкса - Википедия - Shankss square forms factorization

Эта статья требует внимания специалиста по математике. Пожалуйста, добавьте причина или разговаривать в этот шаблон, чтобы объяснить проблему со статьей. ВикиПроект по математике может помочь нанять эксперта. (Ноябрь 2008 г.)

Эта статья включает Список ссылок, связанное чтение или внешняя ссылка, но его источники остаются неясными, потому что в нем отсутствует встроенные цитаты. Пожалуйста, помогите улучшать эта статья введение более точные цитаты. (Март 2015 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

Практический алгоритм поиска пар ${ Displaystyle (х, у)}$ которые удовлетворяют ${ Displaystyle х ^ {2} эквив у ^ {2} { pmod {N}}}$ был разработан Шанксом, который назвал его «Факторизация квадратной формы» или SQUFOF. Алгоритм может быть выражен в виде непрерывных дробей или квадратичных форм. Хотя сейчас доступны гораздо более эффективные методы факторизации, преимущество SQUFOF состоит в том, что он достаточно мал, чтобы быть реализованным на программируемом калькуляторе.

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

Алгоритм

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

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

Алгоритм:

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

Повторение

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

до того как ${ displaystyle Q_ {я + 1}}$ идеальный квадрат в некоторых даже ${ displaystyle i + 1}$.

Инициализировать ${ displaystyle b_ {0} = left lfloor { frac {P_ {0} -P_ {i-1}} { sqrt {Q_ {i}}}} right rfloor, P_ {0} = b_ {0} { sqrt {Q_ {i}}} + P_ {i-1}, Q_ {0} = { sqrt {Q_ {i}}}, Q_ {1} = { frac {kN-P_ { 0} ^ {2}} {Q_ {0}}}}$

Повторение

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

до того как ${ displaystyle P_ {i} = P_ {i-1}.}$

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

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

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

Пример

Позволять ${ Displaystyle N = 11111, k = 1}$

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

Здесь ${ displaystyle Q_ {6} = 25}$ идеальный квадрат.

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

Здесь ${ displaystyle P_ {3} = P_ {4} = 82}$.

${ displaystyle gcd (11111,82) = 41}$, что является фактором ${ displaystyle 11111}$.

Таким образом, ${ Displaystyle N = 11111 = 41 cdot 271}$

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

Ниже приведен пример функции C для выполнения SQUFOF факторизации целого числа без знака, не превышающего 64 бит, без переполнения переходных операций.^{[нужна цитата ]}

#включают <inttypes.h>#define nelems (x) (sizeof (x) / sizeof ((x) [0]))const int множитель[] = {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 СКФОФ( uint64_t N ){    uint64_t D, По, п, Pprev, Q, Qprev, q, б, р, s;    uint32_t L, B, я;    s = (uint64_t)(sqrtl(N)+0.5);    если (s*s == N) возвращаться s;    за (int k = 0; k < Nelems(множитель) && N <= UINT64_MAX/множитель[k]; k++) {        D = множитель[k]*N;        По = Pprev = п = sqrtl(D);        Qprev = 1;        Q = D - По*По;        L = 2 * sqrtl( 2*s );        B = 3 * L;        за (я = 2 ; я < B ; я++) {            б = (uint64_t)((По + п)/Q);            п = б*Q - п;            q = Q;            Q = Qprev + б*(Pprev - п);            р = (uint64_t)(sqrtl(Q)+0.5);            если (!(я & 1) && р*р == Q) перемена;            Qprev = q;            Pprev = п;        };        если (я >= B) Продолжить;        б = (uint64_t)((По - п)/р);        Pprev = п = б*р + п;        Qprev = р;        Q = (D - Pprev*Pprev)/Qprev;        я = 0;        делать {            б = (uint64_t)((По + п)/Q);            Pprev = п;            п = б*Q - п;            q = Q;            Q = Qprev + б*(Pprev - п);            Qprev = q;            я++;        } пока (п != Pprev);        р = gcd(N, Qprev);        если (р != 1 && р != N) возвращаться р;    }    возвращаться 0;}

Рекомендации

• Д. А. Буэлл (1989). Бинарные квадратичные формы. Springer-Verlag. ISBN  0-387-97037-1.
• Д. М. Брессуд (1989). Факторизация и тестирование на примитивность. Springer-Verlag. 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-математическая библиотека