Розклад числа на прості множники, Детальна інформація

Квадратичний алгоритм факторизації

.

. Розглянемо многочлен

q(x) = (x + m)2 - n

Квадратичний алгоритм обирає ai = x + m (x = 0, \xF0B11, \xF0B12, …), обчислює значення bi = (x + m)2 – n та перевіряє, чи факторизується bi у множниковій основі F = {p0, p1, p2, …, pt}.

= (x + m)2 – n \xF0BA (x + m)2 (mod n) \xF0BA bi (mod n).

Алгоритм

Вхід: натуральне число n, яке не є степенм простого числа.

Вихід: нетривіальний дільник d числа n.

1. Обрати множникову основу F = {p0, p1, p2, …, pt}, де p0 = -1, pi – i - те просте число p, для якого n є квадратичним лишком за модулем p.

].

3. Знаходження t + 1 пари (ai, bi).

Значення x перебираються у послідовності 0, \xF0B11, \xF0B12, … .

Покласти i \xF0AC 1. Поки i \xF0A3 t + 1 робити:

3.1. Обчислити b = q(x) = (x + m)2 – n та перевірити, чи розкладається b у множниковій основі F. Якщо ні, обрати наступне x та повторити цей крок.

. Покласти ai = x + m, bi = b, vi = (vi1, vi2, …, vit), де vij = eij mod 2, 1 \xF0A3\xF020j \xF0A3\xF020t.

3.3. i \xF0AC i + 1.

= 0.

mod n.

) / 2.

mod n.

= 0 та перейти до кроку 5.

9. Обчислити дільник d = НСД(x – y, n).

Приклад. Розкласти на множники n = 24961.

1. Побудуємо множникову основу: F = {-1, 2, 3, 5, 13, 23}

] = 157.

3. Побудуємо наступну таблицю:

i x q(x) факторизація q(x) ai vi

1 0 -312 -23 * 3 * 13 157 (1, 1, 1, 0, 1, 0)

2 1 3 3 158 (0, 0, 1, 0, 0, 0)