Остаток от деления в системе остаточных классов (СОК)

[ubik77]

Возможна ли в системе исчисления СОК (остаточных классов)
операция получения остатка от деления, и насколько
сложно/просто она реализуется алгоритмически?
Я не нашёл информации об этом.

[iifat]

Если делитель взаимно прост с модулем остаточных классов, то любое число делится на него "без остатка".
Иначе может не делиться. О делении с остатком не слыхал, подозреваю, по причине полной бесполезности такового.

[ubik77]

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

Если делитель взаимно прост с модулем остаточных классов, то любое число делится на него "без остатка".

Скорее всего вы что-то путаете, так не может быть. Если делитель меньше делимого, то остаток всё равно будет, даже если делитель взаимно прост с модулем остаточных классов.

Я хочу попробовать использовать СОК для операции с длинными числами в модульной арифметике. Там постоянно "умножение по модулю", "возведение в квадрат по модулю" и т.д. Но модуль должен быть производный, а не обязательно удовлетворяющий условиям модуля СОК.

[ИСН]

ubik77, Вы сочетаете несочетаемое и удивляетесь, что так не может быть. Почему грузовик не едет, если двигатель в порядке и заправлен бензином? Так ведь не может быть? Может: Вы свой грузовик поставили брюхом на лодку, так что колёса свешиваются по бокам.
Операция такая есть, но она сломана, не нужна, и её нет.

[iifat]

ubik77 в сообщении #818587 писал(а):

Скорее всего вы что-то путаете

Отдюнь. Если $2\times2=1\pmod3$, то и $1/2=2\pmod3$

[ubik77]

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

ubik77 в сообщении #818587 писал(а):

Скорее всего вы что-то путаете

Отдюнь. Если $2\times2=1\pmod3$, то и $1/2=2\pmod3$

И что? Тройка - это здесь модуль СОК или что?
Мне нужно получить остаток от деления на большое число (модуль),
которое само разложено по компонентам модуля СОК. Пока что я нашёл
алгоритм только целочисленного деления без остатка. С остатком не нашёл.

[ИСН]

ubik77, ууу, ну как ещё сказать. Нет его, этого алгоритма. Нет, как нет пива в киоске, когда висит табличка "Пива нет". Вчера был, а сегодня распродали весь.
Ну или так: поделим 7 на 3 по модулю 10 в Вашем смысле ("с остатком"). Какое число Вы хотели бы получить?

[Sonic86]

ubik77 в сообщении #818424 писал(а):

Возможна ли в системе исчисления СОК (остаточных классов) операция получения остатка от деления,

Нет.
Потому что мультипликативная структура $\mathbb{Z}_m^{\times}$ кольца вычетов является группой, в результате если $a,b \in \mathbb{Z}_m^{\times}$, то $a$ делит $b$, т.е. искомый остаток для требуемой всегда равен нулю.
Короче говоря,

ИСН в сообщении #818614 писал(а):

"Пива нет"

Откуда у Вас вывалился этот вопрос? Сформулируйте лучше исходный вопрос. Вы хотите что-то оптимизировать?

[ubik77]

Sonic86 в сообщении #818626 писал(а):

Откуда у Вас вывалился этот вопрос? Сформулируйте лучше исходный вопрос. Вы хотите что-то оптимизировать?

Я хочу ускорить операции с длинными числами, используя СОК. Умножение есть - факториал считается намного быстрее, чем в позиционной системе, я проверил. Сложение есть. А вот деление какое-то кривое, причём деления с остатком не нашёл вообще.

[Sonic86]

ubik77 в сообщении #818629 писал(а):

А вот деление какое-то кривое

Надеюсь, что Вы знаете о том, что деление целых друг на друга иногда дает нецелые числа.

ubik77 в сообщении #818629 писал(а):

причём деления с остатком не нашёл вообще.

Потому что его нет. Вам надо формулировать вопрос правильно (сейчас неправильно). Например, начать с такой формулировки: "Даны 2 числа $a,b <m$, написать алгоритм вычисления $a\bmod b$". М.б. в такой формулировке задача окажется осмысленной. Я пока сам фоново подумаю...

[ИСН]

ИСН в сообщении #818614 писал(а):

поделим 7 на 3 по модулю 10 в Вашем смысле ("с остатком"). Какое число Вы хотели бы получить?

[Sonic86]

А, я буду типа переводчик.

Пусть заданы $a,b\geqslant 0$. Выберем любое $m$ такое, что $a,b < m$.
Нам надо найти $q,r: a=qb+r$. Ясно, что $0\leqslant q,r<m$
При всех этих ограничениях на $a,b,q,r$ будет верно ни фига не будет верно, что $a=bq+r\Leftrightarrow a\equiv bq+r \pmod{m}$.
$\Rightarrow$: ясно, что из $a=bq+r\Rightarrow a\equiv bq+r\pmod m$
$\Leftarrow$: пусть $a\equiv bq_1+r_1\pmod{m}, a\equiv bq_2+r_2\pmod{m}$. Тогда $b(q_2-q_1)\equiv -(r_2-r_1)\pmod{m}$. И все. Уже здесь Fail;_
Полагая $m=p_1...p_s$ получаем, что $a\equiv bq+r \pmod{m} \Leftirghtarrow (\forall j) a\equiv bq+r \pmod{p_j}$. Теперь нам надо попытаться решить эти сравнения относительно всех $p_j$.
Ясно, что это невозможно: для каждого $j$ сравнение одно, а переменных - две.
Fail;


Действительно, даже так не получается.

А вот деление сделать можно. Только при этом трудно проверить, будет ли частное целым числом или нет

-- Пт янв 24, 2014 11:53:30 --

Sonic86 в сообщении #818648 писал(а):

А вот деление сделать можно. Только при этом трудно проверить, будет ли частное целым числом или нет

А, ну я идиот: чтобы проверить, является ли частное целым числом, достаточно вычислить НОД чисел (за логарифмическое время) и сравнить его с делителем. Ну а дальше - вперед на танке СОКе.

[ubik77]

Sonic86 в сообщении #818632 писал(а):

ubik77 в сообщении #818629 писал(а):

А вот деление какое-то кривое

Надеюсь, что Вы знаете о том, что деление целых друг на друга иногда дает нецелые числа.

Вот в интернете написано, что если делится нацело, то можно вычислить в СОК, а если не делится, то нигде нет алгоритма, как поделить с остатком.

Да, если уж хотите формулы, то будет так:
М - модуль СОК, является произведением всех простых чисел скажем от 10009 до 65381;
a<M, b<M, а и b представлены как вектора в системе СОК с модулем M
(каждое число это массив из примерно 5300 двухбайтовых слов, очень удобно и быстро умножать и складывать их) причём a всегда больше b.

Найти a mod b

P.S. Чтобы было понятно, зачем это мне - я всё ещё мучаю метод квадратов (topic73607-45.html) для теста Ферма на простоту. Есть идея перегнать число в СОК и считать в ней. Умножение, сложение есть, причём умножение реально намного быстрее работает чем в позиционной, но нужно ещё получать остаток от деления.

[ИСН]

ИСН в сообщении #818614 писал(а):

поделим 7 на 3 по модулю 10 в Вашем смысле ("с остатком"). Какое число Вы хотели бы получить?

[ubik77]

ИСН в сообщении #818670 писал(а):

ИСН в сообщении #818614 писал(а):

поделим 7 на 3 по модулю 10 в Вашем смысле ("с остатком"). Какое число Вы хотели бы получить?

Я бы хотел получить остаток от деления 7 на 3, т.е. 1
10 - это у вас что? Если модуль СОК, то из каких компонент он состоит?
7 и 3 слишком маленькие числа, мне нужны числа побольше, разложенные остатками по вектору СОК (даже чтобы рассмотреть в качестве примера).