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

Представьте себе, что вы раскладываете на множители — и делите число M=1987645202877 на 197. Не делится. Переходите к 199. Опять не делится. Переходите дальше, и тут кто-то, пришедший понаблюдать за этим процессом, выдаёт — "а зачем вы делите на числа, на которые M не делится? Делить M надо на те числа, на которые делится!"
Скорее всего, вы захотите такому советчику много что сказать. Так вот, удивительная вещь состоит в том, что ровно так и работает квадратичное решето — за счёт того, что мы знаем, какие числа Q(x)=x^2-N на какие простые из базы будут делится!

А именно — вот у нас есть простое число p из базы. По модулю p наше N является квадратичным вычетом (иначе бы мы p из базы выкинули) — и мы можем (просто перебором, это всё равно не самая трудозатратная часть) найти корни a и (-a) из N. Но мы знаем, что Q(x) и Q(y) сравнимы, если x и y сравнимы по модулю p. Значит, на p будут делиться Q(x) при x вида a+n*p и (-a)+n*p, и только при таких!
То есть, к примеру, для простых порядка сотни тысяч или миллиона мы знаем, какие Q(x) нужно на них делить, и это должно дать ускорение в эту самую сотню тысяч-миллион раз.

Так что глобальный алгоритм просеивания (действительно напоминающий решето Эратосфена) устроен следующим образом. Вот мы будем смотреть на числа вида
(m+k)^2-N,
где m это целая часть корня из N, а k пробегает какой-то интервал, и хотим из них отобрать гладкие.

Давайте считать произведение всех степеней простых из базы, на которые такие числа делятся. А именно — заведём массив W для логарифма такого произведения ("видишь длинное произведение — прологарифмируй!"); изначально заполним его нулями.

После чего для каждого p в цикле пробежим по k, для которых m+k имеют один из двух нужных остатков по модулю p, и добавим ln p к W[k]. И, конечно, это будет не цикл по k, а движение с шагом в p.
После чего обработаем делящиеся на p^2 числа (движение с шагом p^2, добавим ещё раз ln p), на p^3, и так далее.

В результате такого цикла мы для каждого k найдём, на какое максимальное гладкое число Q(m+k)=(m+k)^2-N делится. И, сравнив его с логарифмом Q(m+k), выясним, гладкое это число или нет.

И поскольку мы, вместо того, чтобы каждое число пытаться делить — добавляли ln p только туда, куда надо, алгоритм действительно очень сильно ускорился.

Давайте я процитирую три абзаца из уже упомянутой "A Tale of Two Sieves" Карла Померанса:

Кстати, зашифрованное в 1977 году создателями RSA сообщение "The Magic Words are Squeamish Ossifrage" (https://en.wikipedia.org/wiki/The_Magic_Words_are_Squeamish_Ossifrage ) было расшифровано как раз с использованием (чуть более продвинутой и приспособленной к распараллеливанию) версии квадратичного решета — позволившей разложить на множители соответствующее 129-значное число RSA-129 (см. https://en.wikipedia.org/wiki/RSA_numbers#RSA-129 )

Ну и на этом, наверное, я этот рассказ [на время?] завершу. Тут ещё осталось много чего нерасказанного (включая, например, распараллеливание вычислений), но вообще-то я собирался сделать всего лишь короткий перерыв между двумя рассказами о результатах Фюрстенберга и Маргулиса. :)

Давайте я начну рассказывать об одном из результатов Маргулиса — о доказательстве гипотезы Оппенгейма (https://en.wikipedia.org/wiki/Oppenheim_conjecture ). И для начала посмотрим на саму эту гипотезу, посвящённую значениям квадратичной формы от нескольких переменных в целых точках.

Вообще, значения квадратичной формы нескольких переменных в целых точках даже для квадратичной формы с целыми коэффициентами это большая, красивая и нетривиальная наука. Сразу можно вспомнить теорему Лагранжа, утверждающую, что любое натуральное число представляется как сумма четырёх квадратов. Иными словами, значения на Z^4 квадратичной формы B(x,y,z,t)=x^2+y^2+z^2+t^2
это все неотрицательные целые числа.

Можно вспомнить критерий того, когда натуральное число n представляется как сумма двух квадратов: простые вида 4k+3 должны входить в разложение n на простые множители только в чётных степенях.

Чуть менее известное, но тоже красивое утверждение — это в каких натуральных точках (x,y) квадратичная форма
B(x,y)=y^2 -xy - x^2
принимает значения плюс или минус 1. Оказывается, (x,y) должны быть тогда парой последовательных числами Фибоначчи — и это критерий. (Если мы разрешаем x и y быть отрицательными, то последовательность Фибоначчи тоже нужно будет продолжить на отрицательные индексы, и ещё разрешить одновременную смену их знака). Что, кстати, хорошее упражнение.
И отсюда идёт дорога к работам Матиясевича и решению 10-й проблемы Гильберта — но по этой дороге я сейчас не пойду. :)

Так вот, возвращаясь к гипотезе — пусть у нас есть квадратичная форма (однородный многочлен степени два)
B(x_1,...,x_n)
в R^n. Рассмотрим множество X=B(Z^n) её значений во всевозможных целых точках. Вопрос, который нас будет интересовать — когда можно утверждать, что X всюду плотно?

Во-первых, нельзя, чтобы у формы B были бы целые коэффициенты. Или рациональные. Или одновременно пропорциональные рациональным. Так что будем рассматривать формы, которые не пропорциональны формам с целыми коэффициентами (и будем для краткости называть такие формы иррациональными ).

Во-вторых, нельзя, чтобы форма B была знакоопределённой — если она положительно определена, то мы по определению не получим отрицательных значений, если отрицательно, положительных. Так что пусть она будет не-знакоопределённой [индефинитной].

В-третьих, бессмысленно брать вырожденную форму — так что мы будем просить её невырожденности.
Достаточно ли попросить всего этого, чтобы X=B(Z^n) было всюду плотным? В размерности два — нет.

И тут есть два естественных примера; и тут, и там мы будем смотреть на малые значения — принимает ли B на Z^2 малые ненулевые значения (ибо если множество значений плотно, то должна).

Пример 1. Давайте рассмотрим квадратичную форму на плоскости
B(x,y)=x^2-w^2 y^2=(x-wy)(x+wy),
где w=(1+\sqrt{5})/2. Тогда ненулевые значения |B(p,q)| отделены от нуля.

Действительно, например, для натуральных p и q величина
|w-p/q|
не может быть меньше, чем 1/(5q^2) — что можно увидеть или через цепные дроби, или "вручную" — " квадратичную иррациональность нельзя приблизить лучше, чем const/q^2 ". Потому что при подстановке (p/q) в квадратный трёхчлен f(z)=z^2-z-1, корнем которого является w, мы получаем дробь со знаменателем q^2 и числителем не меньше 1 по модулю — а если значение |f(p/q)| "большое", то и |w-p/q| большое, ибо теорема Лагранжа.

Так вот — раз |w-p/q| не меньше, чем 1/(5q^2), то |p-wq| не меньше 1/5q, и значит, произведение
|B(p,q)|= |p-wq| |p+wq|
не меньше 1/5.

Цитируя Маргулиса из сборника лекций филдсовских медалистов (https://www.worldscientific.com/doi/abs/10.1142/9789812564856_0009 ) —

Пример 2 — из работы самого Оппенгейма, https://academic.oup.com/qjmath/article-abstract/4/1/54/1568503 . Он очень похож на предыдущий, но в этот раз форма будет принимать маленькие положительные значения и не будет — маленьких отрицательных.
А именно — достаточно взять
B(p,q)=pq-wq^2 = q (p-wq),
где разложение константы w в цепную дробь,
w=[a_0; a_1,a_2,a_3,...]
таково, что нечётные его элементы a_{2k-1} равномерно ограничены, а чётные a_{2k} стремятся к плюс бесконечности.
Тогда подходящие дроби (p_i,q_i), полученные обрубанием цепной дроби для w после a_i с нечётным i=2k-1, приближают w с избытком, меньшим
1/(q_i q_{i+1}) — и потому соответствующие положительные значения
B(p_i,q_i) =q_i (p_i-q_i w) < q_i/q_{i+1} < 1/a_{i+1}
стремятся к нулю. А из-за ограниченности нечётных элементов цепной дроби соответствующие отрицательные значения к нулю не подходят.