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

Метод

Предположим, что мы пытаемся разложить на множители составное число 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 ² ≡b ² (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 ¹ 3 ⁰ 5 ⁰ 7 ⁰ = 2 ≡ 189 = 2 ⁰ 3 ³ 5 ⁰ 7 ¹ .............(1)
• 2 ⁰ 3 ⁰ 5 ¹ 7 ⁰ = 5 ≡ 192 = 2 ⁶ 3 ¹ 5 ⁰ 7 ⁰ .............(2)
• 2 ⁰ 3 ² 5 ⁰ 7 ⁰ = 9 ≡ 196 = 2 ² 3 ⁰ 5 ⁰ 7 ² .............(3)
• 2 ³ 3 ⁰ 5 ⁰ 7 ¹ = 56 ≡ 243 = 2 ⁰ 3 ⁵ 5 ⁰ 7 ⁰ .............(4)

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

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

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

• (3): Оно гласит 3 ² ≡ 14 ² (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), с помощью целочисленной версии метода Ньютона для вычисления корня

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

Примечания

Литература

• 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).