Реферат на тему:
Розклад числа на прості множники
, де 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
Нашли опечатку? Выделите и нажмите CTRL+Enter
