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

Реферат на тему:

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

де pi — взаємно прості числа, ki xF0B3xF0201 .

Задача перевірки числа на простоту є простішою за задачу факторизації. Тому перед розкладанням числа на прості множники слід перевірити число на простоту.

Означення. Розбиттям числа називається задача представлення натурального числа n у вигляді n = a * b, де a, b — натуральні числа, більші за 1 (не обов’язково прості).

Метод Ферма Нехай n — складене число, яке не є степенем простого числа. Метод Ферма намагається знати такі натуральні x та y, що n = x2 — y2. Після чого дільниками числа n будуть a = x — y та b = x + y: n = a * b = (x — y)(x + y).

Якщо припустити що n = a * b, то в якості x та y (таких що n = x2 — y2) можна обрати.

Приклад. Виберемо n = 143 = 11 * 13.

Тоді x = (13 + 11) / 2 = 12, y = (13 — 11) / 2 = 1.

Перевірка: x2 — y2 = 122 — 11 = 143 = n.

< x < (n + 1) / 2.

< x.

.

(n + 1) / 2], перевіряючи при цьому чи є вираз x2 — n повним квадратом.

= 19.

202 — 391 = 9 = 32. Маємо рівність: 391 = 202 — 32.

Звідси 391 = (20 — 3)(20 + 3) = 17 * 23.

Алгоритм Полард — ро факторизації числа У 1974 році Джон Полард запропонував алгоритм знаходження нетривіального дільника натурального числа n. Пр цьому алгоритм використовує лише операції додавання, множення та віднімання модулярної арифметики.

тобто починаючи з індекса i = n1 послідовність {xi mod n} буде періодичною.

+ 3 mod 21.

Тоді послідовність xi має вигляд: 1, 4, 19, 7, 10, 19, 7, 10, … .

Таким чином x3 = x6, період послідовності дорівнює 3.

Послідовність xi можна відобразити у вигляді кола з хвостом: коло відповідає періодичній частині, а хвіст — доперіодичній. Картинка нагадує грецьку літеру xF072, тому метод який застосовується в алгоритмі називається xF072 — евристикою. Послідовність із попереднього прикладу можна зобразити так:

Ідея алгоритму полягає в обчисленні для кожного i > 0 значення d = НСД (x2i — xi, n). Якщо на деякому кроці d > 1, то це і є нетривіальний дільник числа n.

Побудуємо послідовність елементів xi наступним чином:

+ 1) mod n, i > 0.

Алгоритм Вхід: натуральне число n, параметр t xF0B3 1.

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

1. a =xF0202, b =xF0202;

2. for i xF0ACxF0201 to t do.

2.1. Обчислити a xF0ACxF020xF028a2 + 1) mod n; b xF0ACxF020xF028b2 + 1) mod n; b xF0ACxF020xF028b2 + 1) mod n;

2.2. Обчислити d xF0ACxF020НСД (a — b, n);

2.3. if 1 < d < n return (d); // знайдено нетривіальний дільник.

3. return (False); // дільника не знайдено.

) операцій модулярного множення.

Якщо алгоритм Поларда — ро не знаходить дільника за t ітерацій, то замість функції f (x) = (x2 + 1) mod n можна використовувати f (x) = (x2 + c) mod n, для деякого цілого c, c xF0B9 0, -2.

Приклад. Нехай n = 19 939.

Послідовність xi: 2, 5, 26, 677, 19 672, 11 473, 12 391, 6582, 15 217, 5483, 15 217, 5483, 15 217, … .

a b d.

2 2 1.

5 26 1.

26 19 672 1.

677 12 391 1.

19 672 15 217 1.

11 473 15 217 1.

12 391 15 217 157.

Знайдено розклад 19 939 = 157 * 127.

Нехай n = 143. Послідовність xi: 2, 5, 26, 105, 15, … .

a b d.

2 2 1.

5 26 НСД (21, 143) = 1.

26 15 НСД (11, 143) = 11.

Знайдено розклад 143 = 11 * 13.

Ймовірносний квадратичний алгоритм факторизації числа Твердження. Нехай x та y — цілі числа, x2 xF0BA y2 (mod n) та x xF0B9 xF0B1y (mod n). Тоді x2 — y2 ділиться на n, при чому жоден із виразів x + y та x — y не ділиться на n. Число d = НСД (x2 — y2, n) є нетривіальним дільником n.

Теорема. Якщо n — непарне складене число, яке не є степенем простого числа, то завжди існують такі x та y, що x2 xF0BA y2 (mod n), при чому x xF0B9 xF0B1 y (mod n).

Доведення. Нехай n = n1 * n2 — добуток взаємно простих чисел. Оберемо таке y, що НСД (y, n) = 1. Далі розв’яжемо систему рівнянь:

Розв’язком системи будуть такі x та y за модулем n = НСК (n1, n2), що x2 xF0BA y2 (mod n). Якщо при цьому припустити, що x xF0BA — y (mod n), то з другого рівняння системи маємо: y xF0BA — y (mod n2), або 2 * y = 0 (mod n2). Оскільки було обрано НСД (y, n2) = 1, то з останньої рівності випливає що n2 ділиться на 2, тобто є парним. Це суперечить умові теореми про непарність n.

Приклад. Виберемо n1 = 11, n2 = 13 — взаємно прості числа. Тоді n = 11 * 13 = 143. Покладемо y = 5, НСД (5, 143) = 1. Складемо систему порівнянь:

Розв’язком системи буде x xF0BA 60 (mod 143).

Має місце рівність 602 xF0BA 52 (mod 143), при чому 60 xF0B9 xF0B15 (mod 143).

Тоді дільником числа n буде d = НСД (60 — 5, 143) = 11.

Формально ймовірносний квадратичний алгоритм факторизації будується на наступній ідеї:

Нехай F = {p0, p1, p2, …, pt} - множникова основа, pi — різні прості числа, при чому дозволяється обрати p0 = -1. Побудуємо множину порівнянь.

xF0BA zi ,.

таку що значення zi є повіністю факторизованими у множині F :

.

та добуток деякої підмножини значень zi є повним квадратом:

= y2, y xF0CExF020Z, fi xF0CExF020{0, 1}.

і перевіривши виконання нерівності x xF0B9 xF0B1 y (mod n), отри маємо x2 xF0BA y2 (mod n). Число d = НСД (x2 — y2, n) є нетривіальним дільником n.

Приклад. Знайти дільник числа n = 143.

Обираємо випадково число x xF0CE [2, 142], обчислюємо x2 (mod 143) та розкладаємо результат на множники:

1. z1 = 192 (mod 143) = 75 = 3 * 52.

2. z2 = 772 (mod 143) = 66 = 2 * 3 * 11.

3. z3 = 292 (mod 143) = 126 = 2 * 32 * 7.

4. z4 = 542 (mod 143) = 56 = 23 * 7.

Можна помітити, що добуток z3 та z4 є повним квадратом:

z = z3 * z4 = 24 * 32 * 72 = (22 * 3 * 7)2 = 842.

Маємо рівність:

z3 * z4 = 292 * 542 xF0BA 842 (mod 143).

або враховуючи що 29 * 54 (mod 143) xF0BA 136, маємо:

1362 = 842 (mod 143), при чому 136 xF0B9 xF0B184 (mod 143).

Дільником числа n = 143 буде d = НСД (136 — 84, 143) = НСД (52, 143) = 13.

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

.

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

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 xF0A3xF020j xF0A3xF020t.

3.3. i xF0AC i + 1.

= 0.

mod n.

) / 2.

mod n.

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

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

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

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).

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) = 24 025.

8. Оскільки 936 xF0BAxF020−24 025 (mod n), необхідно шукати іншу множину T.

9. Виберемо T = {3, 6, 7}, оскільки v3 + v6 + v7 = 0.

10. Обчислимо x = (a3a6a7) mod n = 23 405 = 210 * 34 * 56.

11. l1 = 1, l2 = 5, l3 = 2, l4 = 3, l5 = 0, l6 = 0.

12. y = -25 * 32 * 53 (mod n) = 13 922.

13. 23 405 xF0B9 xF0B113922 (mod n).

d = НСД (x — y, n) = НСД (9483, 24 961) = 109 — дільник.

Відповідь: 109 — дільник 24 961.