Квадратичное сито: существует ли эмпирическое правило, позволяющее решить, сколько чисел просеивать?

В чистом квадратичном решете нам нужно найти немного больше отношений (что эквивалентно сглаживаний), чем простых чисел в факторной базе. При этом мы считаем маленькие простые числа $p_i$ это делает $N$ квадратичный вычет по модулю $p_i$, а не их полномочия. Это количество также является количеством столбцов в (разреженной) матрице отношений, где отношения являются строками, которые служат входными данными для фазы линейной алгебры. Как правило, на 5 строк больше, чем столбцов. Каждое дополнительное отношение уменьшает вероятность отказа в два раза.

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

• Критически важно, если мы просеиваем один (QS) или несколько полиномов (MPQS/SIQS). С QS слишком часто случается, что полином вырастает до чрезмерно высоких значений, поэтому сглаживания становятся редкостью; тогда увеличение сита или его повторное использование для дальнейшего просеивания одного и того же многочлена не сильно поможет.
• Стратегия w.r.t. полиномиальные значения, в которых мы не уверены (или очень уверены), суммируя логарифмы их факторов, найденных путем просеивания, что они достаточно гладкие для наших целей. Мы можем
  • Игнорируйте их, даже если они все еще могут быть $В$-гладкий.
  • Попробуйте маленькие простые множители до самого высокого просеянного простого числа. $В$, и их мощности, даже если они превышают $В$ (другими словами, мы ограничиваемся $В$-гладкие значения полинома, прошедшие шаг просеивания); это просто и типично для базовой (MP/SI)QS.
  • Попробуйте небольшие коэффициенты до некоторого более высокого предела $В'$ (другими словами, мы просеиваем простые и простые степени, чтобы $B<B'$, и ограничиться $В'$-гладки, прошедшие стадию просеивания).
  • Кроме того, допустите один большой простой множитель (PMPQS) до некоторого более высокого предела в надежде, что столкновение для этих больших простых чисел позволит двум иначе неприменимым отношениям дать новое пригодное для использования (то есть без большого простого числа, так что оно соответствует ограниченному количеству столбцов в матрица)
  • Дополнительно разрешите два больших простых множителя (PPMPQS).
• Порог просеивания (для суммы логов простых чисел, накопленных в записи сита), который является компромиссом между отбрасыванием $В$-сглаживает и тратит слишком много времени на попытки факторизовать кандидатов, которые не дадут пригодных отношений.

Рекомендации по запуску QS:

• Сначала сделайте что-нибудь скромное $N$ без ситового массива!
  • Используйте факторную базу $p_i$ изготовление $N$ квадратичный вычет до некоторого предела $В$. Безопаснее сначала ошибиться в большую сторону от оптимума. $В$.
  • Находить $В$-сглаживает среди значений многочлена $т^2-N$ с $t\gtrsim\left\lceil\sqrt N\,\right\rceil$ самым простым способом (например, пробным делением).Найдите немного больше сглаживаний, чем простых чисел.
  • Получите линейную алгебру, работающую на фактор $N$.
• Оптимизировать большинство (или все) пробных подразделений $т^2-N$ тестом, который $t\bmod(p_i^k)$ попадает в набор из двух предварительно вычисленных значений.
• На этом этапе узким местом должно быть нахождение сглаживаний путем полной факторизации многих $т^2-N$ с использованием (оптимизированного) пробного разделения, в результате чего большинство из них не $В$-гладкий. Ввести массив сита, цель которого состоит в том, чтобы (резко) уменьшить количество гладких кандидатов за счет ошибочного отклонения нескольких (отсеивание простых степеней помогает сделать ложное отклонение редким). Это позволяет увеличить $N$ (таким образом повышая оптимальную $В$).
• Вводите дальнейшие оптимизации одну за другой:
  • имея $-1$ в факторной базе, то есть просеивание $N-t^2$ за $t\lesssim\влево\lfloor\sqrt N\,\right\rfloor$
  • легкое улучшение «множителя», которое $м\,N$ для некоторого выбранного небольшого целого числа $м$, так что факторная база улучшается (имеет относительно много маленьких простых чисел)
  • с использованием нескольких полиномов, что позволяет отсеивать и факторизовать гораздо меньших кандидатов, что, таким образом, с большей вероятностью будет $В$-гладит
  • узким местом все еще может быть попытка факторизации смузи, прошедшего ситовый тест (в зависимости от порога просеивания и размера факторной базы); некоторая экономия возможна за счет использования (оптимизированного) пробного деления только на маленькие простые числа, а затем чего-то лучшего, возможно, ро Полларда с проверкой на простоту, когда она не дает быстрого результата; такой тест будет необходим для больших основных улучшений.
  • одно, затем два больших основных улучшения (PMPQS и PPMPQS).
• Оптимизируйте любые узкие места и настройте множество параметров. В конечном счете, узким местом должно быть просеивание. Оптимизированные реализации требуют больших усилий, с методами и кодом, специализированными в зависимости от размера просеянных простых чисел и взаимодействия с кешем ЦП.