Хочу поинтересоваться у тех, кто занимался факторизацией чисел. Как в методе квадратичного решета оптимально выбрать размер факторной базы и интервал просева?

задан 27 Мар '18 17:20

Вроде бы здесь есть достаточно конкретная информация.

(27 Мар '18 21:32) falcao

Там написано очень расплывчато, что величины должны быть порядка exp(sqrt(log(n)*log(log(n)))). Для размера факторной базы это приблизительно подходит, но хотелось бы поточнее. А вот для глубины просева это совсем не верно. Она должна быть в несколько раз больше факторной базы, иначе просто не наберется нужного количества гладких чисел. Приведенное число, кстати, является приблизительной вычислительной сложностью этого метода.

(27 Мар '18 22:05) Андрей13neo

Может быть, тогда посмотреть уточнения в статьях типа этой, а также в ссылках на литературу внутри неё?

(27 Мар '18 22:27) falcao

Именно в этой статье не даются конкретные рекомендации выбора параметров, а только приводится пример, какие были параметры для факторизации числа RSA-129. Там очень маленькая факторная база (к=0,125) и очень большой интервал просева (М=В^3). Это обусловлено тем, что просев делался распределенно на сотнях компьютерах (более 400), а система уравнений решалась на одном (причем около двух недель). В других источниках указано, что к должно быть в пределах от 0,5 до 1, а М от В до В^2. Это ближе к истине. Подбирать приходится методом тыка (например, я пока остановился на к=0,6 М=18*В).

(28 Мар '18 18:22) Андрей13neo

@Андрей13neo: судя по всему, выбор везде делался эмпирически, то есть "точных" данных по этому поводу нет. Поэтому вполне разумно звучит идея воспользоваться, как говорят шутники, "методом великого польского учёного Тадеуша Тыка" :)

Факторизация -- вещь весьма интересная сама по себе, поэтому будет хорошо, если Вы потом расскажете, что получилось.

(28 Мар '18 22:45) falcao

Так я уже могу рассказать. Моя прога работает с числами длиной 2^128. Максимальное время работы на самом тяжелом числе 21 секунда. Хочу усовершенствовать скорость. Она сильно зависит от указанных параметров. Уменьшая один, надо увеличивать другой. От первого зависит скорость решения системы, от второго скорость просева. Но, при этом должно набираться необходимое количество гладких (больше факторной базы). Второй путь, по которому хочу пойти разобраться в методах Видеманна и Ланцшота и заменить одним из них метод Гауса, который я сейчас использую.

(29 Мар '18 2:05) Андрей13neo

@Андрей13neo: а какой вид имеют исследуемые числа? Вы берёте произведения типа pq, или что-то другое?

(29 Мар '18 2:12) falcao

Тут комменты имеют ограничение, поэтому пишу следующий. Пока с указанными параметрами сильно не экспериментирую, так как копаюсь с усовершенствованием решения системы. Пока использую либо к=1 М=4ВВ, либо к=0,6 М=18ВВ. Время работы примерно одинаково: в первом случае в два раза быстрее просев, но медленнее решение системы, во втором наоборот. Кому интересно, даю два числа для теста: 340282366909646319581956946666535343973 11111111111111111111111111111111109251 У меня они оба факторизуются около 15-20 сек. Буду благодарен за предоставление интересных чисел для тестов.

(29 Мар '18 2:20) Андрей13neo

Первое число просто очень близко к границе размера, которую использует моя прога, второе интересно тем, что требует интервал просева больший, чем другие, которые я использую для тестов. Кстати, в пакете GMP в папке demos есть готовая прога для факторизации factorize.c, которая работает с длинными числами (в отличии от моей). Но, там используется другой метод.

(29 Мар '18 2:32) Андрей13neo

@Андрей13neo: я сейчас оба числа поместил в Maple. Она справилась, хотя считала долго. Получилось (6981463658303)(6981463658233)(6981463658227) в первом случае и (6306338984375119)(1761895632099784153229) во втором. Сами множители, наверное, для тестов можно брать любыми, как обычно -- проверка на простоту проводится известными методами.

(29 Мар '18 13:03) falcao

Очень интересно, сколько приблизительно времени они считались? Я вчера немного модифицировал метод решения системы уравнений - не стал лезть в дебри Ланцшота или Вимеманна, оставил простой метод Гауса, но изменил размер элементов с байта на бит. Первое число теперь считается 6 секунд, второе 5. Теперь система решается почти моментально. А вот, что делать с просевом ума не приложу. Там так все просто, что нечего модифицировать. Разве только уменьшить радиус просева за счет увеличения базы простых. Но, они много места занимают в памяти, а генерить их каждый раз заново очень долго.

(29 Мар '18 15:54) Андрей13neo

@Андрей13neo: программа Maple сама по себе не очень быстрая, а у меня её старая версия, и компьютер почти 10-летней давности. Поэтому там подсчёты длились минуты три где-то.

(29 Мар '18 17:45) falcao
показано 5 из 12 показать еще 7
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×879

задан
27 Мар '18 17:20

показан
905 раз

обновлен
29 Мар '18 17:45

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru