Реферат на тему:
Розклад числа на прості множники
, де 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.
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
Нашли опечатку? Выделите и нажмите CTRL+Enter
