Регистрация Войти
Рейтинг:3
avatar Crypto

Квадратное сито: просеивание с простыми степенями

флаг et
user93353

Я пытаюсь понять алгоритм квадратного сита.

В настоящее время я застрял в части просеивания.

Допустим, нужно разложить на множители число 9788111. Я решаю поискать 50-гладкие множители. Моя исходная факторная база (FB) = $p_i$ = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47}.

Я просматриваю каждый номер в FB и их полномочия.

Для каждого числа в FB я сначала проверяю, является ли N квадратичным остатком по модулю числа (т. е. является ли N QR $\pmod{p_i}$. Если да, то я нахожу корни.

Для 2 тривиально проверить, является ли N QR $\pмод 2$. Вы также можете расширить это для степеней 2. Для других простых чисел вы можете использовать критерии Эйлера для квадратичных остатков, чтобы проверить, является ли N QR $\pmod{p_i}$. Если это QR, вы можете использовать Tonelli-Shanks, чтобы найти корни, а затем просеять с этим простым числом.

Что я делаю для основных полномочий? Для экв. $5^2$, как мне проверить, если $t^2 \экв N \pmod {5^2}$ есть решение? Есть ли какой-нибудь тест или правило, чтобы проверить это, прежде чем я попытаюсь найти корень?

Для небольших простых степеней, таких как $5^2$, может быть возможно найти проверку вручную, если N является QR $\pmod {{p_i}^n}$, но как это сделать для больших простых степеней?

102
1 + 0
Рейтинг:3
fgrieu avatar Crypto
флаг ng
fgrieu

Напомним, что (базовое) квадратное решето требует нахождения некоторых $х$ с $х^2-N$ гладкий. К этому он добавляет (масштабированный, приблизительный) логарифм $p_i$ на малые делители ${p_i}^м$ из $х^2-N$ в индексе $х>0$ массива. Это относительно быстро, потому что только два из ${p_i}^м$ записи в массиве нужно трогать для каждого ${p_i}^м$.

Что делать для простых степеней (т.е. ${p_i}^м$ за $м>1$)?

Ленивый и неоптимальный вариант — игнорировать их на этапе просеивания, компенсируя это более низким сглаженным порогом и/или большим количеством простых чисел в базе.

Лучший вариант - решить $x^2\экв N\pmod{{p_i}^m}$, а затем просеять ${p_i}^м$ как мы сделали для $p_i$. Для нечетного простого числа $p_i$, мы уже решили $x\экв N\pmod{p_i}$, скажем, имеет (два) решения $x_j\in[0,p_i)$. (два) решения $x^2\экв N\pmod{{p_i}^m}$ в $[0,{p_i}^m)$ находятся $${x_j}^{({p_i}^{m-1})}\cdot N^{({p_i}^m - 2{p_i}^{m-1} + 1)/2}\bmod { р_я}^м$$

Диксон атрибуты это Тонелли. я использовал этот ответ в качестве освежителя. Формула также в Википедии, с примерами.

0 + 4
флаг et
user93353
Спасибо. Для нечетно-простого $p$, если $x^2 \equiv N\pmod p$ имеет решение, то гарантируется, что $x^2 \equiv N\pmod {p^m}$ также имеет решение. Я знаю, что это неверно для степеней двойки. Но то же самое для нечетных простых чисел или это гарантировано?
0
Ответить
fgrieu avatar
флаг ng
fgrieu
@user93353: Да, для нечетного простого числа $p$, если $x^2\equiv N\pmod p$ имеет решение, то гарантируется ли, что $x^2\equiv N\pmod {p^m}$ также имеет решение. Их не более двух по модулю $p^m$.
0
Ответить
флаг et
user93353
Большой! Наверное, я предполагал, что это не так (точно так же, как это не для степеней двойки).Весь мой вопрос становится бессмысленным, если он гарантирован. Есть ли какое-нибудь доказательство или теорема, показывающая это? Ссылка в какой-то книге?
0
Ответить
fgrieu avatar
флаг ng
fgrieu
@ user93353: Источник Диксона (сам цитирующий Тонелли) в конце моего ответа — лучшее, что я нашел до сих пор. [Примечание HAC 3.41] (https://cacr.uwaterloo.ca/hac/about/chap3.pdf#page=16) утверждает, что легко найти квадратные корни в поле порядка степени простого числа, таким образом, включая модуль простого числа мощность, но, к сожалению, обоснование с использованием факта 3.42 и метода, по-видимому, охватывает только простое число 2. Возможно прямое доказательство формулы Тонелли (в моем ответе) путем возведения в квадрат и упрощения.
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.