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

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

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

Доведення. Нехай n = n1 * n2 – добуток взаємно простих чисел. Оберемо таке y, що НСД(y, n) = 1. Далі розв’яжемо систему рівнянь:



Розв’язком системи будуть такі x та y за модулем n = НСК(n1, n2), що x2 \xF0BA y2 (mod n). Якщо при цьому припустити, що x \xF0BA – y (mod n), то з другого рівняння системи маємо: y \xF0BA – 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 \xF0BA 60 (mod 143).

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

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

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

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

\xF0BA zi ,

таку що значення zi є повіністю факторизованими у множині F :

,

та добуток деякої підмножини значень zi є повним квадратом:

= y2, y \xF0CE\xF020Z, fi \xF0CE\xF020{0, 1}

і перевіривши виконання нерівності x \xF0B9 \xF0B1 y (mod n), отри маємо x2 \xF0BA y2 (mod n). Число d = НСД(x2 – y2, n) є нетривіальним дільником n.

Приклад. Знайти дільник числа n = 143.

Обираємо випадково число x \xF0CE [2, 142], обчислюємо x2 (mod 143) та розкладаємо результат на множники:

1. z1 = 192 (mod 143) = 75 = 3 * 52.

2. z2 = 772 (mod 143) = 66 = 2 * 3 * 11.

3. z3 = 292 (mod 143) = 126 = 2 * 32 * 7.

4. z4 = 542 (mod 143) = 56 = 23 * 7.

Можна помітити, що добуток z3 та z4 є повним квадратом:

z = z3 * z4 = 24 * 32 * 72 = (22 * 3 * 7)2 = 842

Маємо рівність:

z3 * z4 = 292 * 542 \xF0BA 842 (mod 143)

або враховуючи що 29 * 54 (mod 143) \xF0BA 136, маємо:

1362 = 842 (mod 143), при чому 136 \xF0B9 \xF0B184 (mod 143)

Дільником числа n = 143 буде d = НСД(136 – 84, 143) = НСД(52, 143) = 13.