q(x) = (x + m)2 - n
Квадратичний алгоритм обирає ai = x + m (x = 0, ±1, ±2, …), обчислює значення bi = (x + m)2 – n та перевіряє, чи факторизується bi у множниковій основі F = {p0, p1, p2, …, pt}.
Помітимо, що = (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. Побудуємо наступну таблицю:
| 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) |
| 3 | -1 | -625 | -54 | 156 | (1, 0, 0, 0, 0, 0) |
| 4 | 2 | 320 | 26 * 5 | 159 | (0, 0, 0, 1, 0, 0) |
| 5 | -2 | -936 | -23 * 32 * 13 | 155 | (1, 1, 0, 0, 1, 0) |
| 6 | 4 | 960 | 26 * 3 * 5 | 161 | (0, 0, 1 ,1, 0, 0) |
| 7 | -6 | -2160 | -24 * 33 * 5 | 151 | (1, 0, 1, 1, 0, 0) |
4. Виберемо T = {1, 2, 5}, оскільки v1 + v2 + v5 = 0.
5. Обчислимо x = (a1a2a5) (mod n) = 936 = 26 * 34 * 132.
6. l1 = 1, l2 = 3, l3 = 2, l4 = 0, l5 = 1, l6 = 0.
7. y = -23 * 32 * 13 (mod n) = 24025.
8. Оскільки 936 º –24025 (mod n), необхідно шукати іншу множину T.
9. Виберемо T = {3, 6, 7}, оскільки v3 + v6 + v7 = 0.
10. Обчислимо x = (a3a6a7) mod n = 23405 = 210 * 34 * 56.
11. l1 = 1, l2 = 5, l3 = 2, l4 = 3, l5 = 0, l6 = 0.
12. y = -25 * 32 * 53 (mod n) = 13922.
13. 23405 ¹ ±13922 (mod n).
d = НСД(x – y, n) = НСД(9483, 24961) = 109 – дільник.
Відповідь: 109 – дільник 24961.