Path: Математика » Теория чисел » Факторизация »
Простое деление

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

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

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

Предположим, что
у нас уже есть таблица простых чисел: 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.

[Инициализация]
Если N <=
5, вывести разложение 1 = 1, 2 = 2, 3 = 3, 4 = 22, 5 =
5 в зависимости от N и выйти. Иначе, i := -1, m := 0, L := [
N1/2 ]

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

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

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

[Следующий делитель]
Пусть 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 := [ N1/2 ] во время
инициализации, так как проверка d >= L в шаге 4 может быть
заменена на q <= L, где q - евклидово частное при делении N на d
: N = q * d + r, обычно вычисляемое одновременно с остатком в шаге
3.

Обсудить на форуме
»

[AD]