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

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

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

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

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

Означення. Розбиттям числа називається задача представлення натурального
числа 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 можна відобразити у вигляді кола з хвостом: коло відповідає періодичній частині, а хвіст – доперіодичній. Картинка нагадує грецьку літеру ?, тому метод який застосовується в алгоритмі називається ? – евристикою. Послідовність із попереднього прикладу можна зобразити так: Ідея алгоритму полягає в обчисленні для кожного i > 0 значення d =
НСД(x2i – xi, n). Якщо на деякому кроці d > 1, то це і є нетривіальний
дільник числа n.

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

+ 1) mod n, i > 0

Алгоритм

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

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

1. a =?2, b =?2;

2. for i ??1 to t do

2.1. Обчислити a ???a2 + 1) mod n; b ???b2 + 1) mod n; b ???b2 + 1) mod
n;

2.2. Обчислити d ??НСД(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 ? 0, -2. Приклад. Нехай n = 19939. Послідовність xi: 2, 5, 26, 677, 19672, 11473, 12391, 6582, 15217, 5483, 15217, 5483, 15217, ... . a b d 2 2 1 5 26 1 26 19672 1 677 12391 1 19672 15217 1 11473 15217 1 12391 15217 157 Знайдено розклад 19939 = 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 ? y2 (mod n) та x ? ?y (mod n). Тоді x2 – y2 ділиться на n, при чому жоден із виразів x + y та x – y не ділиться на n. Число d = НСД(x2 – y2, n) є нетривіальним дільником n. Теорема. Якщо n – непарне складене число, яке не є степенем простого числа, то завжди існують такі x та y, що x2 ? y2 (mod n), при чому x ? ? y (mod n). Доведення. Нехай n = n1 * n2 – добуток взаємно простих чисел. Оберемо таке y, що НСД(y, n) = 1. Далі розв’яжемо систему рівнянь: Розв’язком системи будуть такі x та y за модулем n = НСК(n1, n2), що x2 ? y2 (mod n). Якщо при цьому припустити, що x ? – y (mod n), то з другого рівняння системи маємо: y ? – 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 ? 60 (mod 143). Має місце рівність 602 ? 52 (mod 143) , при чому 60 ? ?5 (mod 143). Тоді дільником числа n буде d = НСД(60 – 5, 143) = 11. Формально ймовірносний квадратичний алгоритм факторизації будується на наступній ідеї: Нехай F = {p0, p1, p2, …, pt} – множникова основа, pi – різні прості числа, при чому дозволяється обрати p0 = -1. Побудуємо множину порівнянь ? zi , таку що значення zi є повіністю факторизованими у множині F : , та добуток деякої підмножини значень zi є повним квадратом: = y2, y ??Z, fi ??{0, 1} і перевіривши виконання нерівності x ? ? y (mod n), отри маємо x2 ? y2 (mod n). Число d = НСД(x2 – y2, n) є нетривіальним дільником n. Приклад. Знайти дільник числа n = 143. Обираємо випадково число x ? [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 ? 842 (mod 143) або враховуючи що 29 * 54 (mod 143) ? 136, маємо: 1362 = 842 (mod 143), при чому 136 ? ?84 (mod 143) Дільником числа n = 143 буде d = НСД(136 – 84, 143) = НСД(52, 143) = 13. Квадратичний алгоритм факторизації . . Розглянемо многочлен 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. ]. 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 та повторити цей крок. . Покласти ai = x + m, bi = b, vi = (vi1, vi2, …, vit), де vij = eij mod 2, 1 ??j ??t. 3.3. i ? 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) 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. Література 1. Pomerance C. Analysis and comparison of some integer factorization algorithms. In Computational Methods in Number Theory, vol.154, H.Lenstra and R.Tijdeman, Eds. Amsterdam Mathematics Center 1982, pp. 89 – 139. 7 10 19 4 1

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *