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

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

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

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

Задача. Розбиття числа. Дано натуральне число n. Представити його у
вигляді n = a * b, де a, b – натуральні числа, більші за 1 (не
обов’язково прості).

Алгоритм Полард — ро факторизації числа

Нехай n – натуральне число, яке треба розкласти на множники. Алгоритм
Полард — ро дає можливість знайти нетривіальний дільник числа n.

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

+ 1) mod n, i > 0

Алгоритм факторизації

Вхід: натуральне число n.

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

a ??2, b ??2;

for i ??1, 2, … do

begin

a ???a2 + 1) mod n; b ???b2 + 1) mod n; b ???b2 + 1) mod n;

d ??НСД(a — b, n);

if 1 < d < n return (d); else return (FALSE); // розв’язку не знайдено end; Алгоритм Полард - ро обчислення дискретних логарифмів Нехай G – циклічна група з порядком n (n – просте). Розіб’ємо елементи групи G на три підмножини S1, S2 та S3, які мають приблизно однакову потужність. При цьому необхідне виконання умови: 1 ??S2. Визначимо послідовність елементів xi наступним чином: , i ??0 (1) Ця послідовність у свою чергу утворить дві послідовності ci та di , що задовольняють умові та визначаються наступним чином: , i ??0 (2) та , i ??0 (3) . Логарифмуючи останню рівність за основою a, матимемо: (di - d2i) * logab ??(c2i - ci) mod n Якщо di ? d2i (mod n), то це рівняння може бути ефективно розв’язано для обчислення logab. Алгоритм обчислення дискретного логарифму Вхід: генератор циклічної групи G з порядком n (n – просте) та елемент b ??G. Вихід: дискретний логарифм x = logab. x0 ??1, c0 ??0, d0 ??0. for i ? 1, 2, ... do begin За значеннями xi-1, ci-1, di-1 та x2i-2, c2i-2, d2i-2 обчислити значення xi, ci, di та x2i, c2i, d2i використовуючи формули (1), (2), (3). if (xi = x2i) then begin r ??(di - d2i) mod n; if (r = 0) then return (FALSE); // розв’язку не знайдено x ? r -1 (ci - c2i) mod n; return (x); end; end; .

Похожие записи

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

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

, де 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. 7 10 19 4 1

Похожие записи