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

677123911

19672152171

11473152171

1239115217157

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

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

abd

221

526НСД(21, 143) = 1

2615НСД(11, 143) = 11

Знайдено розклад 143 = 11 * 13.

Ймовірносний квадратичний алгоритм факторизації числа

Твердження. Нехай x та y – цілі числа, x2  y2 (mod n) та x y (mod n). Тоді x2 – y2 ділиться на n, при чому жоден із виразів x + y та x – y не ділиться на n. Число d = НСД(x2 – y2, n) є нетривіальним дільником n.

Теорема. Якщо n – непарне складене число, яке не є степенем простого числа, то завжди існують такі x та y, що x2  y2 (mod n), при чому x y (mod n).

Доведення. Нехай n = n1 * n2 – добуток взаємно простих чисел. Оберемо таке y, що НСД(y, n) = 1. Далі розв’яжемо систему рівнянь:Розв’язком системи будуть такі x та y за модулем n = НСК(n1, n2), що x2 y2 (mod n). Якщо при цьому припустити, що x – y (mod n), то з другого рівняння системи маємо: y  – y (mod n2), або 2 * y = 0 (mod n2). Оскільки було обрано НСД(y, n2) = 1, то з останньої рівності випливає що n2 ділиться на 2, тобто є парним. Це суперечить умові теореми про непарність n.

Приклад. Виберемо n1 = 11, n2 = 13 – взаємно прості числа. Тоді n = 11 * 13 = 143. Покладемо y = 5, НСД(5, 143) = 1. Складемо систему порівнянь:

або

Розв’язком системи буде x 60 (mod 143).

Має місце рівність 602 52 (mod 143) , при чому 60 5 (mod 143).

Тоді дільником числа n буде d = НСД(60 – 5, 143) = 11.

Формально ймовірносний квадратичний алгоритм факторизації будується на наступній ідеї:

Нехай F = {p0, p1, p2, …, pt} – множникова основа, pi – різні прості числа, при чому дозволяється обрати p0 = -1. Побудуємо множину порівнянь

zi ,