UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75855
останнє поновлення: 2016-12-09
за 7 днів додано 17

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваРозклад числа на прості множники (реферат)
Авторdimich
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось1050
Скачало376
Опис
ЗАКАЧКА
Замовити оригінальну роботу

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

 

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

 

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

 

.

 

0

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ