Квадратичне решето

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Алгоритм квадратичного решета (англ. quadratic sieve, QS) — це алгоритм факторизації цілих чисел і, на практиці, другий за швидкістю з відомих (після загального решета цифрового поля). Він досі найшвидший для цілих до 100 десяткових чисел або близько того, і помітно простіший ніж решето цифрового поля. Це метод факторізації загального призначення, тобто час його виконання залежить лише від розміру цілого числа на вході, а не на особливостях його структури. Його винайшов Карл Померанц у 1981 як покращення до лінійного решета Шроппеля.[1]

Вступ[ред.ред. код]

Візьмемо, наприклад, число 2419. Це число складене і не ділиться на жодне з малих простих чисел. Але можна побачити, що це 2500 - 81, тобто 2419 = 50^2 - 9^2. Отже ми можемо розкласти 2419 як різницю квадратів. Це є (50-9)(50+9) або 41\times 59. Кожне непарне складене число можна розкласти як різницю квадратів:

n = pq = \left(\frac{p+q}{2}\right)^2 - \left(\frac{p-q}{2}\right)^2.

Спробуймо знов з числом 1649. Воно також складене і не має малих простих дільників, менших ніж його логарифм. З 2419 ми взяли перший квадрат більший від нього, а саме 50^2 і тоді зауважили, що 50^2 - 2419 = 81, що є квадратом. Можна подумати, що в пошуці квадратів можна пройти послідовність x^2-n з x = \lceil n^{1/2} \rceil, \lceil n^{1/2} \rceil + 1, \dots. Для n = 1649 маємо:

41^2 - n = 32,
42^2 - n = 115,

43^2 - n = 200,

 

 

 

 

(1)

\vdots

і не бачимо квадратів поміж перших результатів.

Незважаючи на цю невдачу, попередні три рівняння вже можна використати для розкладення n. Зауважте, що хоча ані 32, ані 200 не є квадратами, їхній добуток — квадрат, а саме 80^2. отже з того, що

41^2 \equiv 32 \pmod n,
43^2 \equiv 200 \pmod n,

маємо 41^2 \times 43^2\equiv 80^2\pmod n, що рівнозначно

(41\times 43)^2 \equiv 80^2 \pmod n.

 

 

 

 

(2)

Ми знайшли розв'язок для a^2\equiv b^2 \pmod n. Наскільки це цікаво? Звісно існує багато нецікавих двійок a^2\equiv b^2 \pmod n. А саме, якщо взяти будь-яке значення a і покласти b = \pm a. Але цей перелік не вичерпує всі розв'язки для цього рівняння, бо розкладення n як різницю квадратів дало б дійку a, b з b \not = \pm a. Далі, будь-яка двійка a, b з

a^2 \equiv b^2 \pmod n, b \not\equiv \pm a \pmod n

 

 

 

 

(3)

повинно вести до нетривіального розкладу n, через \gcd(a-b,n). Справді, з 3 випливає, що n ділить (a-b)(a+b), але не ділить жоден з множників, отже \gcd(a-b,n), \gcd(a+b,n) повинні бути нетривіальними дільниками n. НСД можна знайти через алгоритм Евкліда. Зрештою, якщо n має щонайменше два простих множники, тоді не менше половини розв'язків a^2 \equiv b^2 \pmod n з ab взаємно простим з n також задовольняють b\not\equiv \pm a \pmod n, що і є 3.

Доведення
Для степені непарного простого p^u, конгруентність y^2\equiv 1 \pmod {p^u} має рівно 2 розв'язки, отже з того, що n ділимо не менш як двома різними непарними простими, конгруенція y^2 \equiv 1 \pmod n має щонайменше 4 розв'язки. Позначимо ці значення як y_1, y_2, y_3, \dots, y_s, де y_1 = 1, y_2 = -1. Тоді повний перелік двійок квадратичних залишків a, b за модулем n взаємно простих з n і з a^2 \equiv b^2 \pmod n збігається з усіма двійками a, y_i a, де a пробігає всі залишки взаємно прості з n, a i = 1, \dots, s. Двійки з i = 1, 2 не задовольняють 3, тоді як інші так. З того, що s \ge 4, доведення завершене.

Ідея[ред.ред. код]

В основі методу лежить така ідея. Припустимо x і y є цілими такими, що x^2 \equiv y^2 \pmod n, але x \not\equiv \pm y \pmod n. Тоді n ділить x^2 - y^2 = (x - y)(x + y), але не ділить ані (x - y), ані (x + y). Звідси \gcd(x-y,n) повинен бути нетривіальним дільником n.

Припустимо, що ми маємо розкласти ціле n. Нехай m = \sqrt n, розглянемо многочлен q(x) = (x + m)^2 -n. Зауважимо, що

q(x) = x^2 + 2mx +m^2 - n \approx x^2 + 2mx

є малим порівняно з n, якщо абсолютне значення x мале. Алгоритм квадратичного решета обирає a_i = (x + m) і перевіряє чи є b_i = (x + m)^2\ \ p_t-гладким. Зауважимо, що a_i = (x + m)^2 \equiv b_i \pmod n, звідси n є квадратичним залишком за модулем p. Отже фактор-база повинна складатись з простих чисел p, для яких символ Лежандра \left(\frac{n}{p}\right)=1. Окрім цього, тому що b_i може бути від'ємним, -1 також включаємо до фактор-бази.

Алгоритм[ред.ред. код]

Вхід: ціле складене число n, яке не є степенем простого.

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

  1. Обираємо базу дільників S = \{p_1, p_2, . . . , p_t\}, де p_1=-1 і p_j (j \ge 2) є (j-1)-е просте p для якого n є квадратичним залишком за модулем p.
  2. Обчислити m = \lfloor \sqrt n \rfloor.
  3. (Зібрати t + 1 двійок (a_i, b_i). Значення x обираємо в порядку 0,\pm 1,\pm 2, \dots)
    Встановити i\gets 1. Поки i \le t + 1 робити наступне:
    1. Обчислити b = q(x) = (x+m)^2-n, і перевірити послідовним діленням на елементи з S чи є b\ p_t-гладким. Якщо ні, обираємо новий x і повторюємо.
    2. Якщо b є p_t-гладким, скажімо b = \prod_{j=1}^t p_i^{e_{ij}}, тоді покласти a_i\gets (x + m), b_i\gets b, v_i = (v_{i1}, v_{i2}, \dots, v_{it}), де v_{ij} = e_{ij} \mod 2 для 1 \le j \le t.
    3. i\gets i + 1.
  4. Використати лінійну алгебру над \Zeta_2 для знаходження непустої підмножини T \subseteq {1, 2, \dots, t + 1} такої, що \sum_{i \in T} v_i = 0.
  5. Обчислити x = \prod_{i\in T} {a_i \mod n}.
  6. Для кожного j, 1 \le j \le t, обчислити l_j = (\sum_{i\in T} e_{ij})/2.
  7. Обчислити y = \prod_{j=1}^t p_j^{l_j} \mod n.
  8. Якщо x \equiv \pm y \pmod n, тоді знайти іншу непорожню підмножину T \subseteq \{1, 2, \dots, t+1\} таких, що \sum_{i\in T} v_i = 0, і перейти до етапу 5. (У малоймовірному випадку, якщо підмножина T не існує, замінити декілька з двійок (a_i, b_i) новими парами (етап 3), і перейти на етап 4.
  9. Обчислити d = \gcd(x-y,n) і повернути d.

Приклад роботи[ред.ред. код]

Алгоритм квадратичного решета для находження нетривіального дільника для n = 24961.

  1. Обираємо фактор-базу S = \{-1, 2, 3, 5, 13, 23\} розміру t = 6. (7, 11, 17 і 19 опущені з S, бо для цих простих (\frac{n}{p}) = -1.)
  2. Обчислити m = \lfloor \sqrt 24961 \rfloor = 157.
  3. Далі йдуть дані зібрані для перших t + 1 значень x, для яких q(x) є 23-гладких.
i x q(x) факторизація q(x) a_i b_i
1 0 −312 -2^3 \times 3 \times 13 157 (1, 1, 1, 0, 1, 0)
2 1 3 3 158 (0, 0, 1, 0, 0, 0)
3 −1 −625 -5^4 156 (1, 0, 0, 0, 0, 0)
4 2 320 2^6 \times 5 159 (0, 0, 0, 1, 0, 0)
5 −2 −936 -2^3 \times 3^2 \times 13 155 (1, 1, 0, 0, 1, 0)
6 4 960 2^6 \times 3 \times 5 161 (0, 0, 1, 1, 0, 0)
7 −6 −2160 -2^4 \times 3^3 \times 5 151 (1, 0, 1, 1, 0, 0)
  1. Візьмемо T = \{1, 2, 5\}.[2] Маємо v_1 +v_2 +v_5 = 0.
  2. Обчислимо x = (a_1 a_2 a_5 \mod n) = 936.
  3. Обчислимо l_1 = 1, l_2 = 3, l_3 = 2, l_4 = 0, l_5 = 1, l_6 = 0.
  4. Обчислимо y = -23 \times 32 \times 13 \mod n = 24025.
  5. Через те, що 936 \equiv -24025 \pmod n, потрібно взяти наступну лінійну залежність.
  6. У випадку T = \{2, 4, 6\}, отримуємо такий самий вислід.
  7. Наступна T = \{3, 6, 7\}, v_3 + v_6 + v_7 = 0.
  8. Обчислимо x = (a_3 a_6 a_7 \mod n) = 23405.
  9. Обчислимо l_1 = 1, l_2 = 5, l_3 = 2, l_4 = 3, l_5 = 0, l_6 = 0.
  10. Обчислимо y = (-25 \times 32 \times 53 \mod n) = 13922.
  11. Тепер, 23405 \not\equiv \pm 13922 \pmod n, отже обчислимо \gcd(x-y, n) = \gcd(9483, 24961) =
109. Звідки, маємо два нетривіальних дільники для 24961109 і 229.

Перевірка гладкості просіюванням[ред.ред. код]

Замість перевірки на гладкість перебором дільників застосовної на етапі 3.1, використовується ефективніша техніка відома як просіювання (англ. sieving). Спочатку звернемо увагу на те, що якщо p є непарним простим у фактор-базі і p ділить q(x), тоді p також ділить q(x+l p) для кожного цілого l.

y(x)=x^2-n
y(x+kp)=(x+kp)^2-n
y(x+kp)=x^2+2xkp+(kp)^2-n
y(x+kp)=y(x)+2xkp+(kp)^2\equiv y(x)\pmod{p}

Отже через розв'язання рівняння q(x) \equiv 0 \pmod p для x (для цього існує багато дієвих алгоритмів), отримуємо одну або дві (залежно від кількості розв’язків у квадратного рівняння) послідовностей інших значень y для яких p ділить q(y).

Також просіювання використовує властивість логарифму  \log(\prod_1^n p_i) = \sum_1^n\log (p_i) . \,

Перебіг просіювання такий. Створюється масив Q[\ ] проіндексований по x, -M \le x \le M, і кожний запис ініціалізується \lg |q(x)|. Нехай x_1, x_2 будуть розв'язками для q(x) \equiv 0 \pmod p, де p є непарним простим числом з фактор-бази. Тоді значення \lg p віднімають від тих записів в Q[x] для яких x \equiv x_1 або x_2 \pmod p, і -M \le x \le M. Дія повторюється для кожного простого p у фактор-базі. (Випадки з p = 2 і степенями простих чисел можна обробити подібним чином.) Після просіювання, записи в масиві Q[x] зі значеннями близькими до 0 швидше за все є p_t-гладкі (треба брати до уваги помилки округлення), і це можна перевірити через факторизацію q(x) перебором дільників.

Примітки[ред.ред. код]

  1. Carl Pomerance, Analysis and Comparison of Some Integer Factoring Algorithms, in Computational Methods in Number Theory, Part I, H.W. Lenstra, Jr. and R. Tijdeman, eds., Math. Centre Tract 154, Amsterdam, 1982, pp 89-139.
  2. Повний перелік лінійно залежних підмножин векторів такий: 125, 264, 763, 1456, 2347, 13457, 1234567.