Арифметика в остаточных классах
Вопрос такой. Предположим некое довольно большое число N задано через китайскую теорему об остатках этими собственно остатками r_1, ...r_n по фиксированной системе взаимно простых модулей m_1,..., m_n.
И пусть нам теперь дан еще один модуль m (тоже взаимно простой с m_1,...,m_n).
Как(каким алгоритмом) наиболее оптимально(и какая сложность этого) можно посчитать остаток r от деления нашего числа N=N(r_1,...,r_n) выше на m?
Update: Предположительно, у нас не менее нескольких сотен или даже тысяч модулей, и соответственно остатков. И каждый модуль довольно велик от 30000 до 60000. То есть вычислять само число, гмм, не желательно, и вряд ли оптимально.
И пусть нам теперь дан еще один модуль m (тоже взаимно простой с m_1,...,m_n).
Как(каким алгоритмом) наиболее оптимально(и какая сложность этого) можно посчитать остаток r от деления нашего числа N=N(r_1,...,r_n) выше на m?
Update: Предположительно, у нас не менее нескольких сотен или даже тысяч модулей, и соответственно остатков. И каждый модуль довольно велик от 30000 до 60000. То есть вычислять само число, гмм, не желательно, и вряд ли оптимально.