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

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

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

Задача. Розклад числа на прості множники (факторизація числа). Дано натуральне число n. Представити його у вигляді n = $$p_1^{k_1}{p}_2^{k_2}\text{.}\text{.}\text{.}{p}_s^{k_s}$$, де pi — взаємно прості числа, ki 1 .

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

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

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

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

x0 = 2, xi+1 = f (xi) = ($$x_i^2$$ + 1) mod n, i > 0.

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

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

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

a 2, b 2;

for i 1, 2, … do.

begin.

a + 1) mod nb + 1) mod nb + 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 наступним чином:

x0 = 1, xi+1 = $$\begin{array}{c}b{x}_i,x_i{S}_1\\ x_i^2,x_i{S}_2\\ a{x}_i,x_i{S}_3\\ \\ \begin{array}{c}\{\{\end{array}\hfill \\ \end{array}$$, i 0 (1).

Ця послідовність у свою чергу утворить дві послідовності ci та di, що задовольняють умові.

xi = $$a^{c_i}{b}^{d_i}$$.

та визначаються наступним чином:

с0 = 0, сi+1 = $$\begin{array}{c}{c}_i,x_i{S}_1\\ (2c_i)\text{mod}n,x_i{S}_2\\ (c_i+1)\text{mod}n,x_i{S}_3\\ \\ \begin{array}{c}\{\{\end{array}\hfill \\ \end{array}$$, i 0 (2).

та.

d0 = 0, di+1 = $$\begin{array}{c}(d_i+1)\text{mod}n,x_i{S}_1\\ (2d_i)\text{mod}n,x_i{S}_2\\ d_i,x_i{S}_3\\ \\ \begin{array}{c}\{\{\end{array}\hfill \\ \end{array}$$, i 0 (3).

Алгоритм буде працювати циклічно шукаючи таке знчення i, для якого xi = x2i. Для таких значень будуть мати місце рівність $$a^{c_i}{b}^{d_i}$$ = $$a^{c_{2i}}{b}^{d_{2i}}$$ або $$b^{d_i-d_{2i}}$$ = $$a^{c_{2i}-c_i}$$. Логарифмуючи останню рівність за основою a, матимемо:

(di — d2i) * logab (c2i — ci) mod n.

Якщо di i (mod n), то це рівняння може бути ефективно розв’язано для обчислення logab.

Алгоритм обчислення дискретного логарифму Вхід: генератор циклічної групи G з порядком n (n — просте) та елемент b G.

Вихід: дискретний логарифм x = logab.

x0 1, c0 0, d0 0.

for i 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 -1 (ci — c2i) mod n;

return (x);

end;

end;

Якщо алгоритм завершується невдачею (повертає FALSE), то можна запустити його вибравши інші початкові значення c0, d0 з інтервалу [1- n — 1] та поклавши x0 = $$a^{c_0}{b}^{d_0}$$ .