Рациональное сито

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

Метод

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

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

и аналогично, для подходящего $b_{i}$, у нас есть

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

Но $z$ и $z+n$ конгруэнтны по модулю $n$, и поэтому каждое такое целое число z , которое мы находим, дает мультипликативное отношение (mod n ) между элементами P , т.е.

$\prod _{p_{i}\in P}p_{i}^{a_{i}}\equiv \prod _{p_{i}\in P}p_{i}^{b_{i}}{\pmod {n}}$

(где a _i и b _i — неотрицательные целые числа.)

Когда мы сгенерировали достаточное количество этих отношений (обычно достаточно, чтобы число отношений было на несколько раз больше размера P ), мы можем использовать методы линейной алгебры , чтобы перемножить эти различные отношения таким образом, чтобы показатели степени все простые числа четные. Это даст нам сравнение квадратов вида a ² ≡b ² (mod 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^{1}3^{0}5^{0}7^{0}=2\equiv 189=2^{0}3^{3}5^{0}7^{1}$ ( 1 )

$2^{0}3^{0}5^{1}7^{0}=5\equiv 192=2^{6}3^{1}5^{0}7^{0}$ ( 2 )

$2^{0}3^{2}5^{0}7^{0}=9\equiv 196=2^{2}3^{0}5^{0}7^{2}$ ( 3 )

$2^{3}3^{0}5^{0}7^{1}=56\equiv 243=2^{0}3^{5}5^{0}7^{0}$ ( 4 )

Сейчас существует несколько существенно разных способов объединить их и получить в итоге четные показатели. Например,

• ( 1 )×( 4 ): после их умножения и исключения общего множителя 7 (что мы можем сделать, поскольку 7, будучи членом P , уже определено как взаимно простое с n ), это уменьшается до 2 ⁴ ≡ 3 ⁸ (мод . n ), или 4 ² ≡ 81 ² (мод. н ). Результирующая факторизация равна 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 ^м , где p — простое число, а m — целое число. Однако это не такая уж большая проблема: такие числа статистически редки, и, более того, существует простой и быстрый процесс проверки того, имеет ли данное число такую ​​форму. Вероятно, самый элегантный метод — проверить, $\lfloor n^{1/b}\rfloor ^{b}=n$ справедливо для любого $1<b\leq \log _{2}(n)$ используя целочисленную версию метода Ньютона для извлечения корня.

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

Ссылки

• А. К. Ленстра, Х. В. Ленстра-младший, М. С. Манасс и Дж. М. Поллард, Факторизация девятого числа Ферма, Math. Комп. 61 (1993), 319-349. Доступно по адресу [2] .
• А.К. Ленстра, Х.В. Ленстра-младший (ред.) Развитие сита числового поля, Конспект лекций по математике, 1554 г., Springer-Verlag, Нью-Йорк, 1993.