.

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

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

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

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

, де 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, ... dobeginЗа значеннями xi-1, ci-1, di-1 та x2i-2, c2i-2, d2i-2 обчислити значення xi, ci, di та x2i, c2i, d2i використовуючи формули (1), (2), (3).if (xi = x2i) thenbeginr ??(di - d2i) mod n;if (r = 0) then return (FALSE); // розв’язку не знайденоx ? r -1 (ci - c2i) mod n;return (x);end;end;.

Нашли опечатку? Выделите и нажмите CTRL+Enter

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

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

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