Розклад числа на прості множники

Помітимо, що = (x + m)2 – n (x + m)2 (mod n)  bi (mod n).

Алгоритм

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

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

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

2. Обчислити m = [ ].

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

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

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

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

3.2. Нехай b = . Покласти ai = x + m, bi = b, vi = (vi1, vi2, …, vit), де vij = eij mod 2, 1 j t.

3.3. i i + 1.

4. Знайти підмножину T {1, 2, …, t + 1} таку що = 0.

5. Обчислити x = mod n.

6. Для кожного j, 1 j t, обчислити lj = ( ) / 2.

7. Обчислити y = mod n.

8. Якщо x y (mod n), знайти іншу підмножину T {1, 2, …, t + 1} таку що = 0 та перейти до кроку 5.

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

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

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

2. m = 157.

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

ixq(x)факторизація q(x)aivi

10-312-23 * 3 * 13157(1, 1, 1, 0, 1, 0)

2133158(0, 0, 1, 0, 0, 0)