WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Розклад числа на прості множники - Реферат

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


Реферат на тему:
Розклад числа на прості множники
Задача. Розклад числа на прості множники (факторизація числа). Дано натуральне число n. Представити його у вигляді n = , де pi - взаємно прості числа, ki 1 .
Задача перевірки числа на простоту є простішою за задачу факторизації. Тому перед розкладанням числа на прості множники слід перевірити число на простоту.
Задача. Розбиття числа. Дано натуральне число n. Представити його у вигляді n = a * b, де a, b - натуральні числа, більші за 1 (не обов'язково прості).
Алгоритм Полард - ро факторизації числа
Нехай n - натуральне число, яке треба розкласти на множники. Алгоритм Полард - ро дає можливість знайти нетривіальний дільник числа n.
Побудуємо послідовність елементів xi наступним чином:
x0 = 2, xi+1 = f(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 наступним чином:
x0 = 1, xi+1 = , i 0 (1)
Ця послідовність у свою чергу утворить дві послідовності ci та di , що задовольняють умові
xi =
та визначаються наступним чином:
с0 = 0, сi+1 = , i 0 (2)
та
d0 = 0, di+1 = , i 0 (3)
Алгоритм буде працювати циклічно шукаючи таке знчення i, для якого xi = x2i. Для таких значень будуть мати місце рівність = або = . Логарифмуючи останню рівність за основою 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;
Якщо алгоритм завершується невдачею (повертає FALSE), то можна запустити його вибравши інші початкові значення c0, d0 з інтервалу [1; n - 1] та поклавши x0 = .
Loading...

 
 

Цікаве