Простое деление

     Прежде, чем перейти к более сложным материям, рассмотрим самый простой, наивный метод простого деления. И в самом деле, практически при любом алгоритме факторизации оптимально использовать этот способ до некоторой границы B, чтобы убрать малые делители.

     Пусть мы хотим поделить N на все простые числа до корня из N. Для этого мы можем иметь или не иметь в своем распоряжении достаточно большую таблицу простых чисел. Если это не так, то, очевидно, мы можем делить N на числа d в заданных классах эквивалентности, например, 1 и 5 по модулю 6, или 1,7,11,13,17,19,23,29 по модулю 30. Тогда мы проделаем много бессмысленных делений (на составные числа), однако результат останется верным. Таким образом, можно составить следующий алгоритм:


А1.      Простое деление.

     Предположим, что у нас уже есть таблица простых чисел: p[1] = 2, p[2] = 3, ... , p[k], где k > 3, массив t := [6,4,2,4,2,4,6,2], и индекс j, такой что если p[k] mod 30 равно 1,7,11,13,17,19,23 или 29, то j := 0,1,2,3,4,5,6 или 7 соответственно.
     Выберем некоторую верхнюю грань B, такую что B >= p[k], чтобы не тратить на этот алгоритм слишком много времени.

     Получив на входе положительное целое число N, этот алгоритм пытается разложить его на множители, и, если это не получается, то N - число без простых делителей, меньших либо равных B.
  1. [Инициализация]
         Если N <= 5, вывести разложение 1 = 1, 2 = 2, 3 = 3, 4 = 22, 5 = 5 в зависимости от N и выйти. Иначе, i := -1, m := 0, L := [ SQRT(N) ]

  2. [Cледующее простое]
         Пусть m := m + 1. Если m > k, то i : = j - 1 и идти к шагу 5, иначе d : = p[m].

  3. [Простое деление]
         Пусть r : = N mod d. Если r = 0, то вывести d как нетривиальный делитель N и выйти ( или N := N / d, L : = [ SQRT(N) ] и повторить шаг 3, если мы хотим продолжить нахождение делителей N).

  4. [Простое?]
         Если d >= L, то в случае N > 1 вывести сообщение, что оставшаяся часть N - простое и выйти. Иначе, если i < 0 идти на шаг 2.

  5. [Следующий делитель]
         Пусть i := i + 1 mod 8, d := d + t[i]. Если d > B, то вывести сообщение о том, что оставшиеся простые делители N больше B, иначе идти на шаг 3.
     Заметим, что i = -1 пока мы используем нашу таблицу простых и i >= 0 если нет. Этот тест не следует использовать для полной факторизации, кроме тех случаев, когда N - очень маленькое ( например, N < 108), так как для этого есть лучшие методы. Однако, с другой стороны, он весьма полезен для удаления малых множителей.


Заметки к практической реализации.

     Предположим, что мы используем таблицу простых до 500'000 ( 41'538 простых чисел ). Простое деление при таком ограничении никогда не занимает больше нескольких секунд на современных компьютерах. Причем хранить можно только разности между простыми (или их половины), а не сами числа, так как p[k] - p[k-1] можно поместить в 1 байт вместо четырех, если p[k] <= 1'872'851'947 ( а половину этой разности - если p[k] <= 1'999'066'711'391).

     Кроме того, не нужно делать больше делений после того, как кончится таблица простых, так как есть лучшие методы для удаления малых делителей.

     И, наконец, заметим, что нет необходимости в вычислении L := [ SQRT(N) ] во время инициализации, так как проверка d >= L в шаге 4 может быть заменена на q <= L, где q - евклидово частное при делении N на d : N = q * d + r, обычно вычисляемое одновременно с остатком в шаге 3.