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

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

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

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

 

ПОШУК:   

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

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

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

 

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

 

, де pi – взаємно прості числа, ki ??1 .

 

Задача перевірки числа на простоту є простішою за задачу факторизації.

Тому перед розкладанням числа на прості множники слід перевірити число

на простоту.

 

Означення. Розбиттям числа називається задача представлення натурального

числа n у вигляді n = a * b, де a, b – натуральні числа, більші за 1 (не

обов’язково прості).

 

Метод Ферма

 

Нехай n – складене число, яке не є степенем простого числа. Метод Ферма

намагається знати такі натуральні x та y, що n = x2 – y2. Після чого

дільниками числа n будуть a = x – y та b = x + y: n = a * b = (x – y)(x

+ y).

 

Якщо припустити що n = a * b, то в якості x та y (таких що n = x2 – y2)

можна обрати

 

 

Приклад. Виберемо n = 143 = 11 * 13.

 

Тоді x = (13 + 11) / 2 = 12, y = (13 – 11) / 2 = 1.

 

Перевірка: x2 – y2 = 122 – 11 = 143 = n.

 

< x < (n + 1) / 2.

 

< x.

 

.

 

, (n + 1) / 2], перевіряючи при цьому чи є вираз x2 - n повним

квадратом.

 

= 19.

 

202 – 391 = 9 = 32. Маємо рівність: 391 = 202 – 32.

 

Звідси 391 = (20 – 3)(20 + 3) = 17 * 23.

 

Алгоритм Полард - ро факторизації числа

 

У 1974 році Джон Полард запропонував алгоритм знаходження нетривіального

дільника натурального числа n. Пр цьому алгоритм використовує лише

операції додавання, множення та віднімання модулярної арифметики.

 

, тобто починаючи з індекса i = n1 послідовність {xi mod n} буде

періодичною.

 

+ 3 mod 21.

 

Тоді послідовність xi має вигляд: 1, 4, 19, 7, 10, 19, 7, 10, ... .

 

Таким чином x3 = x6, період послідовності дорівнює 3.

 

Послідовність xi можна відобразити у вигляді кола з хвостом: коло

відповідає періодичній частині, а хвіст – доперіодичній. Картинка

нагадує грецьку літеру ?, тому метод який застосовується в алгоритмі

називається ? – евристикою. Послідовність із попереднього прикладу можна

зобразити так:

 

Ідея алгоритму полягає в обчисленні для кожного i > 0 значення d =

НСД(x2i – xi, n). Якщо на деякому кроці d > 1, то це і є нетривіальний

дільник числа n.

 

Побудуємо послідовність елементів xi наступним чином:

 

+ 1) mod n, i > 0

 

Алгоритм

 

Вхід: натуральне число n, параметр t ? 1.

 

Вихід: нетривіальний дільник d числа n.

 

1. a =?2, b =?2;

 

2. for i ??1 to t do

 

2.1. Обчислити a ???a2 + 1) mod n; b ???b2 + 1) mod n; b ???b2 + 1) mod

n;

 

2.2. Обчислити d ??НСД(a - b, n);

 

2.3. if 1 < d < n return (d); // знайдено нетривіальний дільник

 

3. return (False); // дільника не знайдено

 

) операцій модулярного множення.

 

Якщо алгоритм Поларда – ро не знаходить дільника за t ітерацій, то

замість функції f(x) = (x2 + 1) mod n можна використовувати f(x) = (x2 +

c) mod n, для деякого цілого c, c ? 0, -2.

 

Приклад. Нехай n = 19939.

 

Послідовність xi: 2, 5, 26, 677, 19672, 11473, 12391, 6582, 15217, 5483,

15217, 5483, 15217, ... .

 

a b d

 

2 2 1

 

5 26 1

 

26 19672 1

 

677 12391 1

 

19672 15217 1

 

11473 15217 1

 

12391 15217 157

 

 

 

Знайдено розклад 19939 = 157 * 127.

 

Нехай n = 143. Послідовність xi: 2, 5, 26, 105, 15, ... .

 

a b d

 

2 2 1

 

5 26 НСД(21, 143) = 1

-----> Page:

0 [1] [2]

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