Свойства операции по модулю

Question

У меня есть вычисление суммы S = (a * x + b * y + c)% N. Да, это выглядит как квадратное уравнение, но это не потому, что x и y имеют некоторые свойства и должны быть рассчитаны с использованиемнекоторые рецидивирующие отношения.Поскольку сумма превышает даже пределы беззнаковых длинных длинных, я хочу знать, как можно вычислить эту сумму, используя свойства операции по модулю, свойства, которые позволяют записать сумму примерно так (я что-то говорю, потому что точно не помнюкак эти свойства): (a * x)% N + (b * y)% N + c% N, таким образом, избегая превышения пределов беззнаковых длинных длинных.

Заранее благодарим за беспокойство!:)

Answer 1

a % N = x означает, что для некоторых целых чисел 0 <= x < N и m: m * N + x = a.

Вы можете просто сделать вывод, что если a % N = x и b % N = y, то

(a + b) % N =
= (m * N + x + l * N + y) % N =
= ((m + l) * N + x + y) % N =
= (x + y) % N =
= (a % N + b % N) % N.

Мы знаем, что 0 < x + y < 2N, поэтому вам нужно вести подсчет остатка. Это показывает, что можно разделить суммирование и вычислить остатки отдельно, а затем добавить их, но не забудьте получить остаток от суммы.

Для умножения:

(a * b) % N =
= ((m * N + x) * (l * N + y)) % N =
= ((m * l + x * l + m * y) * N + x * y) % N =
= (x * y) % N =
= ((a % N) * (b % N)) % N.

Таким образом, вы можете сделать то же самое с продуктами.

Эти свойства могут быть просто получены в более общем виде с использованием некоторой абстрактной алгебры (остатки образуют кольцо факторов Z/nZ).

Answer 2

Вы можете пойти дальше, если нужно:

S = ( (a%N)*(x%N)+(b%N)*(y%N)+c%N )%N

Answer 3

Вы можете применить модуль к каждому члену суммы, как вы предложили; но даже после их суммирования вы должны снова применить модуль, чтобы получить окончательный результат.

Answer 4

Как насчет этого:

   int x = (7 + 7 + 7) % 10;

   int y = (7 % 10 + 7 % 10 + 7 % 10) % 10;

Answer 5

Мало того, что вы можете уменьшить все переменные mod n перед началом вычисления, вы можете написать свой собственный mod-mul для вычисления * x mod n с помощью метода shift-and-add и уменьшать результат mod n на каждом шаге , Таким образом, ваши промежуточные вычисления потребуют только один бит больше, чем n. После вычисления этих продуктов вы можете добавлять их попарно и уменьшать mod n после каждого добавления, что также не потребует более 1 бита вне диапазона n.

В моем ответе на этот вопрос есть реализация Python модульного умножения. Преобразование в C должно быть тривиальным.

Answer 6

Вы помните правильно. Уравнение, которое вы дали, где вы% N каждое из слагаемых является правильным. И это было бы именно то, что я использую. Вы также должны снова% N для каждой частичной суммы (и суммы), так как результаты сложения могут быть все еще больше, чем N. Но будьте осторожны, это работает только в том случае, если ваш предел размера по крайней мере вдвое больше, чем ваш N. Если это не тот случай, это может стать очень неприятным.

Между прочим, для следующих% N операций с частичными суммами вам не нужно выполнять полное деление, проверку> N и, если больше, достаточно только вычитание N.