Рациональное сито - Rational sieve

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

Методика

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

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

и аналогично для подходящего имеем ${\ displaystyle b_ {i}}$

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

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

${\ displaystyle \ 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 = gcd ( a - b , n ) × gcd ( 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 дают четыре мультипликативных отношения (mod 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 - целое число. Однако это не большая проблема - такие числа статистически редки, и, кроме того, существует простой и быстрый процесс проверки того, имеет ли данное число такую ​​форму. Вероятно, самый элегантный метод - проверить, выполняется ли какое-либо 1 <b <log (n), используя целочисленную версию метода Ньютона для извлечения корня. ${\ displaystyle \ lfloor n ^ {1 / b} \ rfloor ^ {b} = n}$

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

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

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

Сноски