Розклад числа на прості множники, Детальна інформація

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

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

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

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

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

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

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

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

+ 1) mod n, i > 0

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

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

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

a \xF0AC\xF0202, b \xF0AC\xF0202;

for i \xF0AC\xF0201, 2, ... do

begin

a \xF0AC\xF020\xF028a2 + 1) mod n; b \xF0AC\xF020\xF028b2 + 1) mod n; b \xF0AC\xF020\xF028b2 + 1) mod n;

d \xF0AC\xF020НСД(a - b, n);

if 1 < d < n return (d);

else return (FALSE); // розв’язку не знайдено

end;

Алгоритм Полард - ро обчислення дискретних логарифмів

Нехай G – циклічна група з порядком n (n – просте). Розіб’ємо елементи групи G на три підмножини S1, S2 та S3, які мають приблизно однакову потужність. При цьому необхідне виконання умови: 1 \xF0CF\xF020S2. Визначимо послідовність елементів xi наступним чином:

, i \xF0B3\xF0200 (1)

-

\x00B2

-

,

.

J

z