Розклад числа на прості множники, Детальна інформація

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

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

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

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

Означення. Розбиттям числа називається задача представлення натурального числа 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 можна відобразити у вигляді кола з хвостом: коло відповідає періодичній частині, а хвіст – доперіодичній. Картинка нагадує грецьку літеру \xF072, тому метод який застосовується в алгоритмі називається \xF072 – евристикою. Послідовність із попереднього прикладу можна зобразити так:

Ідея алгоритму полягає в обчисленні для кожного i > 0 значення d = НСД(x2i – xi, n). Якщо на деякому кроці d > 1, то це і є нетривіальний дільник числа n.

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

+ 1) mod n, i > 0

Алгоритм