Квадратичне решето: відмінності між версіями
| [перевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
Olvin (обговорення | внесок) Немає опису редагування |
Tolsai (обговорення | внесок) Функція пропозицій посилань: додано 2 посилання. |
||
Рядок 47:
## Якщо <math>b</math> є <math>p_t</math>-гладким, скажімо <math>b = \prod_{j=1}^t p_i^{e_{ij}},</math> тоді покласти <math>a_i\gets (x + m), b_i\gets b, v_i = (v_{i1}, v_{i2}, \dots, v_{it})</math>, де <math>v_{ij} = e_{ij} \mod 2</math> для <math>1 \le j \le t.</math>
## <math>i\gets i + 1.</math>
# Використати [[Лінійна алгебра|лінійну алгебру]] над <math>\Zeta_2</math> для знаходження непустої підмножини <math>T \subseteq {1, 2, \dots, t + 1}</math> такої, що <math>\sum_{i \in T} v_i = 0.</math>
# Обчислити <math>x = \prod_{i\in T} {a_i \mod n}.</math>
# Для кожного <math>j, 1 \le j \le t,</math> обчислити <math>l_j = (\sum_{i\in T} e_{ij})/2</math>.
Рядок 141:
:<math>y(x+kp)=y(x)+2xkp+(kp)^2\equiv y(x)\pmod{p}</math>
Отже через розв'язання рівняння <math>q(x) \equiv 0 \pmod p</math> для <math>x</math> (для цього існує багато дієвих алгоритмів), отримуємо одну або дві (залежно від кількості розв’язків у [[Квадратне рівняння|квадратного рівняння]]) послідовностей інших значень <math>y</math> для яких <math>p</math> ділить <math>q(y).</math>
Також просіювання використовує властивість [[логарифм]]а <math> \log(\prod_1^n p_i) = \sum_1^n\log (p_i) . \,</math>
| |||