Ускорение вычисления китайской теоремы об остатках

[Dmitriy40]

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

Пример.
Пусть даны три множества: $a_{2357}=\{191\} \pmod{210}$, $a_{11}=\{2;3;4;8;9\} \pmod{11}$, $a_{13}=\{2;4;5;6;8;11;12\} \pmod{13}$. По китайской теореме об остатках они задают 35 различных чисел ${} \pmod{30030}$, от $1031$ до $29801$. Причём первые два множества задают 5 чисел $2081;2291;191;1031;1241 \pmod{2310}$.

Можно ли без полного перебора и вычисления всех 35 чисел, имея лишь сами три множества (и их модули разумеется), получить или число $1031$ (для него выполняется $a_{11}=8 \pmod{11}, \; a_{13}=4 \pmod {13}$, т.е. вовсе не наименьшие допустимые) или скажем 12 наименьших чисел из 35 или скажем все числа менее $10000$ (их как раз 12)?

Сколько ни думаю, кроме полного перебора всех 35 вариантов ничего в голову не приходит.
Глянул в "Дынкин, Успенский. Математические беседы.", рекомендованную Munin год назад, но там похоже ответа нет.
Пробовал вычислять числа через сумму произведений, надеялся минимизировать сумму взяв минимумы каждого слагаемого, но не работает: слагаемые большие, сумма большая, но по модулю мала. А в алгоритме Гарднера не получается считать (и минимизировать) произведения независимо.
Да, все числа натуральные и конечные, а модули вообще или простые или праймориалы, никаких идеалов и прочей зауми.

Возможно ли желаемое и если да, то в какую сторону смотреть?

[iifat]

Имхо, ввиду банального отсутствия операций меньше/больше в арифметике остатков — полнаяя безнадёга.

[arseniiv]

iifat
Циклический порядок там зато остаётся. Так что про него должны быть возможны какие-то утверждения, и если мы зафиксируем один из элементов, например 0 «самым левым», мы получим на оставшихся линейный порядок, так что если мы в вычислениях будем где-то иметь в виду этот зафиксированный 0, то есть надежда улучшить вычисления каким-то образом.

Но советов конкретно по теме у меня нет.

[vpb]

Dmitriy40 в сообщении #1507630 писал(а):

Можно ли без полного перебора и вычисления всех 35 чисел,

Можно. Немножко, по крайней мере.

iifat в сообщении #1507636 писал(а):

полнаяя безнадёга.

Ну что вы так пессимистичны ?

Пусть у нас есть два взаимно простых модуля $m_1$ и $m_2$. Сначала найдем вычет $x_1$ по модулю $m=m_1m_2$ такой, что $x_1\equiv1\pmod{m_1}$ и $x_1\equiv0\pmod{m_2}$, и аналогично $x_2$ такой, что $x_2\equiv0\pmod{m_1}$ и $x_2\equiv1\pmod{m_2}$. Дальше, пусть есть два множества вычетов $A_1\subseteq\{0,1,\ldots, m_1-1\}$, и аналогичное $A_2$. Тогда нам надо найти наименьшее по модулю $m$ среди чисел вида $a_1x_1+a_2x_2$, где $a_i\in A_i$, не так ли ?

Вычисляем все числа вида $a_1x_1$ по модулю $m$, и упорядочиваем их. Затем то же самое делаем с числами вида $-a_2x_2$ (заметим минус !). Объединяем их в один список, упорядоченный, и потом по этому списку проходим, и смотрим, где там наименьшая разность между последовательными элементами. (При этом два элемента должны быть подходящих типов, т.е. тот, что больше, вида $a_1x_1$, а второй --- вида $-a_2x_2$.)

Хотя я написал весьма примерно, но надеюсь понятно.

-- 03.03.2021, 16:54 --

Но всё равно тут большого сокращения не получается, разве что в квадратный корень, по сравнению с полным перебором. Если бы можно было обобщить на произведение $\geq3$ модулей, тогда бы получилось. Но, это я думаю, непросто, если вообще возможно.

[svv]

Dmitriy40 в сообщении #1507630 писал(а):

Можно ли без полного перебора

Из первого сравнения вытекает, что достаточно для чисел вида $p_n=191+210n$, где $n=0...(11\cdot 13-1)$, проверить, что остатки $p_n\operatorname{mod} 11$ и $p_n\operatorname{mod} 13$ будут подходящими.
«Коэффициент полезного действия» при этом будет $\frac{5\cdot 7}{11\cdot 13}\approx 0.245$, то есть примерно каждое четвёртое проверяемое число окажется подходящим.
Чтобы добраться до числа $1031$, нужно проверить всего пять чисел такого вида.

-- Ср мар 03, 2021 17:26:53 --

Более того, пусть $m_n=p_n \operatorname{mod} 11$. Найдя
$191\operatorname{mod} 11=4$,
$210\operatorname{mod} 11=1$,
можно эффективно вычислять $m_n$:
$m_0=4$
$m_n=m_{n-1}+1$ (и ещё минус $11$, если результат $\geqslant 11$).

Аналогично для $p_n \operatorname{mod} 13$

[Dmitriy40]

vpb
Обобщить вроде бы можно: ищем такие $x_i$, чтобы они были $\forall i: x_i \equiv 1 \pmod{m_i}$ и $\forall j \ne i: x_i \equiv 0 \pmod{m_j}$, т.е. единичные ровно по одному модулю, по остальным нулевые. Остальное как у Вас. Или там засада в знаке минус?
Только я не понял откуда возьмётся ускорение если перебор всё равно будет при подборе $a_i$, который предлагаете выполнять проходом по списку (ещё плохо понятно как объединять списки). Или Вы имели в виду что сложность слияния с сортировкой и линейного прохода даже в сумме меньше сложности перебора? Надо обдумать и попробовать на других примерах. Пока заметного преимущества не замечаю.

svv
Да, похоже в ограниченном примере это работает неплохо, 25% вероятность хороша. Но вот при расширении примера до реальной задачи, а надо хотя бы два десятка простых модуля и искомые числа порядка $10^{30}$, КПД упадёт, причём я даже знаю насколько.
На самом деле я видимо уже использую нечто подобное.

Для реальных задач и объёмов памяти — "КПД" упадёт в миллионы раз, например в одной из задач из интервала в $13\cdot10^{15}$ чисел у меня уходят дальше на проверку лишь $3.83\cdot10^6$ чисел, или одна трёхмиллиардная часть, вместо 1.1% ($35/30030$) как в примере, и этот показатель хочется улучшить ещё на несколько порядков путём более прямого построения подходящих чисел вместо поиска их перебором, потому что реальные решения очень часто буквально в первых подходящих числах, при том что большинство остальных на порядки больше, но вот как найти эти подходящие среди всех ...

[vpb]

Dmitriy40 в сообщении #1507685 писал(а):

Только я не понял откуда возьмётся ускорение

Допустим, есть два множества чисел $X$ и $Y$, и нам надо найти пару $(x,y)\in X\times Y$ такую, что $x-y$ --- минимальное возможное (и положительное). Ясно, что можно перебирать все пары $(x,y)$, вычислять для них разность. На это нужно время порядка $|X|\cdot|Y|$. Но можно и не перебирать все пары, а сначала сортировать одно из множеств, скажем $X$, а потом для каждого элемента из $Y$ находить ближайший к нему элемент из $X$. Так нужно перебрать только элементы из $Y$. И время $O(|Y| \log |X|)$. Так понятнее ?

-- 03.03.2021, 20:17 --

Собственно, про $O(|Y|\log |X|)$ я зря написал. Если сортировать заранее оба $X$ и $Y$, то только $O(|X|+|Y|)$, да еще $O(|X|\log |X|+|Y|\log |Y|)$ на саму сортировку.

[Dmitriy40]

vpb
Ну да, я так и понял, что предварительной сортировкой уменьшаете потом время поиска минимума.
Сомнения были что две сортировки будут быстрее перебора всех пар. Множества то маленькие, с полсотни элементов, на них важнее не $O()$, а конкретное время. Хотя, если брать не по простому модулю, а сразу по произведению простых, множества будут большими ... Буду думать и пробовать.

Интересно можно ли это обобщить на большее количество множеств, моя мысль выше про единственность единичного вычета не работает.

[vpb]

Dmitriy40 в сообщении #1507878 писал(а):

Хотя, если брать не по простому модулю, а сразу по произведению простых, множества будут большими ...

Так вот то-то и оно. Я как раз имел в виду, разбить множество простых модулей на две группы, найти группы вычетов по модулям, являющимся произведениями простых в каждой из групп, и дальше применить указанный прием. А можно ли обобщить на несколько множеств (три и больше), это, боюсь, вопрос на миллион (NP-полная задача, то есть).

[Dmitriy40]

vpb
Ну в общем с двумя множествами способ очевидно работает (после некоторых мелких доработок).
Засада что я не могу разбить интересующий диапазон всего на два множества, они получаются длиной порядка $10^{20}$ элементов, столько ни вычислить, ни сохранить, ни отсортировать, ни перебрать. В принципе они все и не нужны, хватило бы и наименьших $10^{15}$, но как их получить без вычисления всех $10^{20}$ мне непонятно (вопрос в частности как раз об этом). Рекурсивно спуститься не получится, они не равны суммам, там произведения.

Если б побить исходные $10^{40}$ хотя бы на пять множеств по $10^{8}$ элементов, то вот их уже можно и отсортировать и потом перебрать, но количество вариантов сумм кардинально увеличивается: для двух множеств вариантов всего два (оба элемента в начале каждого множества и элементы в разных концах множеств), для трёх уже больше десятка (вроде бы, даже не выписал ещё все), и т.д. (UPD. Глупость написал, всё проще.) Наверное можно их все аккуратно выписать и закодировать, и если это делать автоматически, а не руками, то должно получиться.
Спасибо за идею, буду думать как автоматизировать процесс.


Но конечно желалось более прямого и простого пути. Ведь праймориал $127\# > 4\cdot10^{48}$, а значит зная все остатки/вычеты по простым до $127$ можно узнать и список допустимых чисел до $4\cdot10^{48}$ и в нём будет хотя бы относительно мало чисел меньше скажем $10^{25}$ и уже их можно более-менее быстро перебрать. Вопрос как их получить не вычисляя все допустимые $10^{36}$ (для одной из задач) во всём праймориале. А если учесть ещё и допустимые остатки по следующей сотне тысяч простых, то можно сразу более-менее вероятно гарантировать простоту допустимых чисел не проверяя их каждое на простоту.

[Dmitriy40]

Никак не получается для реальных задач применить, массивы слишком большие (десятки терабайт и более), а по частям их не получается обрабатывать. Дело не доходит даже до пробной реализации, каждая предварительная оценка даёт нереальные размеры массивов. Или не даёт уменьшения перебора допустимых чисел. Или слишком медленно генерируются и проверяются потом числа.

Пока проще всего и намного быстрее оказался старый рабочий способ (реализованный ещё 5 лет назад), почти как svv описал: сформировал список допустимых остатков по некоторому большому модулю и иду по числовому ряду с шагом модуля и проверяю лишь вот этот список допустимых чисел в каждом интервале. Каждое число проверяется на допустимость по остаткам на 15 следующих простых в среднем за 5 тактов процессора (на все 15 простых суммарно).
Для примера из первого сообщения это будет примерно так: иду с шагом $2310$ и проверяю числа $x=2310n+\{2081;2291;191;1031;1241\}$ (это допустимые остатки по модулю $2310$, полученные из $a_{2357}$ и $a_{11}$ китайской теоремой об остатках) на остаток от деления каждого на $13$, чтобы он попал в множество $a_{13}=\{2;4;5;6;8;11;12\}$. Подходит только $1031$, оно в данном случае и является искомым решением. В других случаях $n$ может быть очень велико.

Вот для одной из несложных задач надо проверить $6\cdot10^{15}$ чисел в диапазоне $10^{23}$ (если я прав и искомое число его не превышает), все они в память не лезут или слишком медленно проверяются по двум массивам и приходится поджать модуль лишь до $7.4\cdot10^{12}$ с $6.6\cdot10^6$ допустимыми числами, ну и вместо $6\cdot10^{15}$ проверить надо $10^{17}$ чисел и при итоговой скорости $3\cdot10^9$ проверяемых чисел в секунду (в 4 потока) время возрастает с примерно трёх недель до более года. А если я ошибся и искомое число ещё больше, то ...

[Dmitriy40]

Что же, тогда немного другой вопрос в продолжение той же темы.
Пусть для того же примера из первого сообщения дополнительно известны допустимые остатки ещё по модулю: $a_{17}=\{1,2,3,4,5,6,7,8,9,10,12,13,14,15,16\}\pmod{17}$.
Сделаем предположение что искомое число менее $2310$. Тогда вычислив его по модулю $2310$ получим что оно не просто должно давать допустимые остатки из $a_{13}$ и $a_{17}$, но и более того, оно не должно меняться при учёте китайской теоремой об остатках модулей $13$ и $17$. При этом условии при учёте модуля $13$ из 5-ти допустимых чисел по модулю $2310$ остаётся всего 2 допустимых числа по модулю $30030$ вместо всего возможных 35-ти. Фактически лишь два из них меньше $2310$. А при учёте и модуля $17$ количество допустимых чисел падает до нуля из 525 возможных (т.е. все они не меньше $2310$). Т.е. сделанное предположение оказалось неверным. И число, удовлетворяющее всем модулям никак не меньше $2310$.

Вопрос можно ли как-то вот эти условия на следующие модули интегрировать в список допустимых остатков по предыдущим модулям? Т.е. не перебирая все 5 чисел по модулю сразу как-то ограничить их до 2 (или хотя бы менее 35) учётом множества $a_{13}$? Вроде бы здесь должно наблюдаться не объединение множеств (как по китайской теореме об остатках), а пересечение. А значит можно как-то "перекинуть" условия сравнимости из одного модуля в другой (другие), но вот как ...
Или всё в итоге всё равно сведётся к перебору всех комбинаций чисел (например предложенным выше vpb способом с делением на два разных модуля и однократным проходом по двум массивам с проверкой лишь чисел менее желаемого порога)?

[Dmitriy40]

Чего-то не получается у меня математическими методами уменьшить размер перебора при одновременном не слишком сильном возрастании размеров массивов. Даже для простенького модельного примерчика выше.

А высказанная выше надежда об уменьшении списка допустимых остатков вообще не работает, во всяком случае как задумывалось: чтобы по известной величине $a_{2357} \bmod 13$ уменьшить список $a_{11}$ с пяти до двух элементов. Он конечно уменьшается, но почему-то (sic!) для разных чисел $a_{2357}=\{9,35,87,139,191\}\equiv 9 \pmod{13}$ одинаковых по модулю $13$ он разный. А это собственно убивает всю идею.