Рациональное решето

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

Метод

Предположим, что мы пытаемся разложить на множители составное число n. Мы определяем границу B и базу множителей (которую будем обозначать через P), множество всех простых чисел, меньших либо равных B. Затем мы ищем положительное целое z, такое, что как z, так и z+n являются B-гладкими, то есть все их простые делители содержатся в P. Мы можем поэтому записать для подходящих степеней ${\displaystyle a_{k}}$

${\displaystyle z=\prod _{p_{i}\in P}p_{i}^{a_{i}}}$,

а также для подходящих ${\displaystyle b_{k}}$ мы имеем

${\displaystyle z+n=\prod _{p_{i}\in P}p_{i}^{b_{i}}}$.

Но ${\displaystyle z}$ и ${\displaystyle z+n}$ сравнимы по модулю ${\displaystyle n}$, так что любое такое целое число z, которое мы находим, даёт связь по модулю по умножению (mod n) среди всех элементов P, то есть

${\displaystyle \prod _{p_{i}\in P}p_{i}^{a_{i}}\equiv \prod _{p_{i}\in P}p_{i}^{b_{i}}\;\operatorname {(mod} \;n\operatorname {)} }$

(где a_i и b_i — неотрицательные целые числа.)

Когда мы сгенерируем достаточно таких соотношений (как правило, достаточно, чтобы число таких отношений было чуть больше размера P), мы можем использовать методы линейной алгебры для умножения этих различных отношений таким образом, чтобы степени всех простых множителей оказались чётными. Это даст нам сравнимость квадратов по модулю^[англ.] вида a^2≡b^2 (mod n), что можно преобразовать в разложение числа n, n = НОД(a-b,n)×НОД(a+b,n). Такое разложение может оказаться тривиальным (то есть n=n×1) и в этом случае нужно попытаться попробовать снова с другой комбинацией отношений. Если посчастливится, мы получим нетривиальную пару делителей числа n, и алгоритм завершится.

Пример

Разложим на множители число n = 187 с помощью рационального решета. Попробуем число B=7, для которого базой множителей служит множество P = {2,3,5,7}. Первый шаг — проверка на делимость числа n на числа из множества P. Ясно, что в случае, когда n делится на одно из таких простых, мы нашли решение. Однако 187 не делится на 2, 3, 5 или 7. На следующем шаге мы ищем подходящие значения z, в качестве таких чисел подходят 2, 5, 9 и 56. Четыре значения z дают соотношения по модулю 187:

• 2^13^05^07^0 = 2 ≡ 189 = 2^03^35^07^1.............(1)
• 2^03^05^17^0 = 5 ≡ 192 = 2^63^15^07^0.............(2)
• 2^03^25^07^0 = 9 ≡ 196 = 2^23^05^07^2.............(3)
• 2^33^05^07^1 = 56 ≡ 243 = 2^03^55^07^0.............(4)

Теперь мы комбинируем разными путями эти соотношения и завершаем чётными степенями. Например,

• (1)×(4): После умножения этих соотношения и сокращения общего множителя 7 (что мы можем делать, поскольку 7, будучи членом P, взаимно просто с n[1]). Сравнение упрощается до 2^4 ≡ 3^8 (mod n), или 4^2 ≡ 81^2 (mod n). Получаем разложение 187 = НОД(81-4,187) × НОД(81+4,187) = 11×17.

Альтернативно, уравнение (3) уже имеет нужный вид:

• (3): Оно гласит 3^2 ≡ 14^2 (mod n), что даёт разложение 187 = НОД(14-3,187) × НОД(14+3,187) = 11×17.

Ограничения алгоритма

Рациональное решето, как и общее решето числового поля, не может получить разложение чисел вида p^m, где p — простое число, а m — целое. Проблема не является слишком большой — статистически такие числа редки и, кроме того, существует простой и быстрый процесс проверки, что заданное число имеет такой вид. Видимо, наиболее элегантным методом является проверка, не выполняется ли ${\displaystyle \lfloor n^{1/b}\rfloor ^{b}=n}$ для 1 < b < log(n), с помощью целочисленной версии метода Ньютона для вычисления корня[2]

Наибольшей проблемой является нахождение чисел z, таких, что как z, так и z+n являются B-гладкими. Для любого заданного B пропорция B-гладких чисел уменьшается быстро с размером числа. Так что, если n велико (скажем, сотня цифр), будет трудно или почти невозможно найти достаточное количество чисел z, чтобы заставить алгоритм заработать. Преимущество общего алгоритма решета числового поля заключается в том, что нужно найти гладкие числа порядка n^1/d для некоторого положительного целого d (обычно 3 или 5), вместо порядка n, как требуется в данном алгоритме.

Примечания

1. Заметим, что общие множители в общем случае не могут быть сокращены в сравнении, но в этом случае сократить можно, поскольку все простые из базы множителей взаимно просты с n. См. Обратное по умножению в модульной арифметике^[англ.].
2. R. Crandall, J. Papadopoulos, On the implementation of AKS-class primality tests Архивная копия от 5 октября 2012 на Wayback Machine

Литература

• A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, J. M. Pollard. The Factorization of the Ninth Fermat Number // Math. Comp. — 1993. — Вып. 61. — С. 319-349.. Предварительная версия статьи доступна по адресу
• The Development of the Number Field Sieve / A. K. Lenstra, H. W. Lenstra. — New York: Springer-Verlag, 1993. — Т. 1554. — (Lecture Notes in Mathematics).