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

Как выбрать подходящую границу гладкости при использовании метода расчета индекса

флаг et
user93353

При реализации квадратичного решета учебники дают приблизительную формулу того, какую границу гладкости вы должны использовать в своей факторной базе.

Чтобы разложить число N с помощью квадратного решета, мы можем использовать следующее:

$ L знак равно е ^ {\ sqrt {\ пер (N) пер (пер (N))}} $, $ B = L ^ {\ гидроразрыва {1} {\ sqrt 2}} $

Для метода индексного исчисления для решения задачи дискретного журнала в $\mathbb F_p$, есть аналогичная формула? Во многих текстах, которые я проверил, просто говорится, что нужно выбрать подходящую границу гладкости B. Но не дается никаких указаний на то, как выбрать подходящую B.

117
1 + 0
Рейтинг:1
avatar Crypto
флаг pe
Samuel Neves

Копперсмит, Одлызко и Шреппель изначально установлен $В = L[1/2, 1/2]$ как для линейного, так и для гауссова решет. Померанс установлен $B = L[1/2, 1/\sqrt{2}]$ для варианта строгого индексного исчисления с использованием метода эллиптических кривых в качестве метода проверки гладкости.

Эти оценки только асимптотические; граница в реализации обычно корректируется с учетом реальной неасимптотической производительности задействованных подпрограмм.

0 + 7
флаг et
user93353
Я попробовал эту формулу с некоторыми решенными примерами в некоторых книгах, и результат кажется совершенно отличным от того, что использовалось в примерах. Например,в книге Сильвермана по математической криптографии он решает $37^x \equiv 211\pmod 18443$. Если я использую формулу $B = L^{\frac {1}{\sqrt 2}}$, я получаю 28,5. Однако для решения задачи Сильверман использует B=5, что довольно далеко от рассчитанного B. У Сильвермана также есть задача на упражнение $17^x \equiv 19 \pmod 19079$, где расчетное B будет равно 28,5, но я могу чтобы решить это снова, используя B=5.
0
Ответить
флаг et
user93353
Что вы подразумеваете под `с ранними прерываниями, как тестер гладкости`?
0
Ответить
флаг et
user93353
Почему 2 формулы, т.е. почему $B = L[1/2, 1/\sqrt{2}]$ - что такое $L^{1/2}$
0
Ответить
флаг pe
Samuel Neves
Если вы читаете книгу Сильвермана, конец раздела 3.8 на странице 169 дал бы ответ на ваш вопрос. Не обращайте особого внимания на параметры в примерах, они оптимизированы для ясности, а не для производительности (т. е. рабочий пример будет выглядеть хуже, если будет слишком много простых чисел, потребуется гораздо больше отношений и т. д.).
0
Ответить
флаг pe
Samuel Neves
$L[1/2, 1/\sqrt{2}]$ — это более общая [L-нотация] (https://en.wikipedia.org/wiki/L-нотация). Это означает то же самое, что и ваш $L^{1/\sqrt{2}}$.
0
Ответить
флаг et
user93353
Спасибо - не могли бы вы также сообщить мне, что вы подразумеваете под «с ранними прерываниями, как тестер плавности».
0
Ответить
флаг pe
Samuel Neves
Неважно, я перепутал это с другой статьей Pomerance. Здесь только ЭЦМ. Но это не имеет большого значения; пробное деление также будет работать, но с несколько худшим временем выполнения.
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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