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

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

Метод


 Предположим, что мы пытаемся разложить на множители составное числоn. Мы определяем границу B и базу множителей(которую будем обозначать через P), множество всех простых чисел,меньших либо равных B. Затем мы ищем положительное целоеz, такое, что как z, так и z+n являютсяB-гладкими, то есть все их простые делители содержатся вP. Мы можем поэтому записать для подходящих степеней ak
z=piPpiai,
 а также для подходящих bk мы имеем
z+n=piPpibi.
 Но z и z+n сравнимы по модулю n, так что любое такое целое числоz, которое мы находим, даёт связь по модулю по умножению (modn) среди всех элементов P, то есть
piPpiaipiPpibi(modn)

 (где ai и bi —неотрицательные целые числа.)
 Когда мы сгенерируем достаточно таких соотношений (как правило,достаточно, чтобы число таких отношений было чуть больше размераP), мы можем использовать методы линейной алгебры для умноженияэтих различных отношений таким образом, чтобы степени всех простыхмножителей оказались чётными. Это даст нам видаa\textsuperscript2≡b\textsuperscript2 (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\textsuperscript13\textsuperscript05\textsuperscript07\textsuperscript0 = 2 ≡ 189 = 2\textsuperscript03\textsuperscript35\textsuperscript07\textsuperscript1.............(1)
  • 2\textsuperscript03\textsuperscript05\textsuperscript17\textsuperscript0 = 5 ≡ 192 = 2\textsuperscript63\textsuperscript15\textsuperscript07\textsuperscript0.............(2)
  • 2\textsuperscript03\textsuperscript25\textsuperscript07\textsuperscript0 = 9 ≡ 196 = 2\textsuperscript23\textsuperscript05\textsuperscript07\textsuperscript2.............(3)
  • 2\textsuperscript33\textsuperscript05\textsuperscript07\textsuperscript1 = 56 ≡ 243 = 2\textsuperscript03\textsuperscript55\textsuperscript07\textsuperscript0.............(4)

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

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

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

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

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


 Рациональное решето, как и общее решето числового поля, не можетполучить разложение чисел вида p\textsuperscriptm, где p— простое число, а m — целое. Проблема не является слишкомбольшой — статистически такие числа редки и, кроме того, существуетпростой и быстрый процесс проверки, что заданное число имеет такой вид.Видимо, наиболее элегантным методом является проверка, не выполняется лиn1/bb=n для 1 \textless b \textless log(n), спомощью целочисленной версии метода Ньютона для вычисления корня
 Наибольшей проблемой является нахождение чисел z, таких, что какz, так и z+n являются B-гладкими. Для любогозаданного B пропорция B-гладких чисел уменьшается быстро сразмером числа. Так что, если n велико (скажем, сотня цифр),будет трудно или почти невозможно найти достаточное количество чиселz, чтобы заставить алгоритм заработать. Преимущество общегоалгоритма решета числового поля заключается в том, что нужно найтигладкие числа порядка n\textsuperscript1/d длянекоторого положительного целого d (обычно 3 или 5), вместопорядка n, как требуется в данном алгоритме.