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

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

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

, де 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, ... 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 ? r -1 (ci - c2i) mod n; return (x); end; end; .

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *