.

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

Язык: украинский
Формат: реферат
Тип документа: Word Doc
0 1196
Скачать документ

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

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

, де 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

Похожие документы
Обсуждение

Оставить комментарий

avatar
  Подписаться  
Уведомление о
Заказать реферат!
UkrReferat.com. Всі права захищені. 2000-2020