Переполнение: a * a mod n

Мне нужно рассчитатьa*a модификацияn ноa довольно большой, что приводит к переполнению, когда я его возводю в квадрат. дела((a%n)*(a%n))%n не работает, потому что (n-1)2 может переполниться. Это на C ++, и я использую int 64.

edit: пример значения = 821037907258 и n = 800000000000, которое переполняется, если вы возводите его в квадрат.

Я использую DevCPP, и я уже пытался заставить работать большие целочисленные библиотеки безрезультатно.

редактировать 2: Нет, у этих номеров нет шаблона.

 std''OrgnlDave09 апр. 2012 г., 18:09
@ Упрощение мат? Хм, нет. Но умножение можно обрабатывать с помощью сдвигов и сложений, что не слишком сложно для реализации.
 juergen d09 апр. 2012 г., 18:09
Что такое N? Имеет ли это образец?
 juergen d09 апр. 2012 г., 18:05
Пример значений, пожалуйста.
 dasblinkenlight09 апр. 2012 г., 18:13
Если вы используетеg++, вы могли бы использовать__uint128_t а также__int128_t расширения.
 std''OrgnlDave09 апр. 2012 г., 18:13
@juergend Double - это 64-битная версия, а что, 13-битная для мантиссы? Это оставляет 2 бита для знаков (один для целой части, один для мантиссы), и вы получите примерно 51 бит с целочисленной точностью. Это больше не поможет переполнению, фактически, оно переполнится раньше - при условии, что OP хочет точности

Ответы на вопрос(5)

что ((a% n) * (a% n))% n должно работать для натуральных чисел. Как вы думаете, почему это не работает? У вас есть контрпример? Если n может быть отрицательным, то оператор% не определен.

 09 апр. 2012 г., 18:37
@WhatsInAName: если(n-1) квадрат может переполниться, вы должны были сказать это в вопросе, потому что вопрос не говорит этого. Ваш вопрос просто говорит, чтоa квадратные переливы. Этот ответ зависит отn квадрат не переполняется.
 WhatsInAName09 апр. 2012 г., 18:27
а меньше п. ^ 2 больше чем n. Однако ^ 2 переполняется.
 09 апр. 2012 г., 18:49
@ MooingDuck: я не думаю, что это необходимо. Тот факт, что ФП вообще задает вопрос, подразумевает, чтоn-1 квадрат может переполниться. Этот ответ основан на необоснованном предположении.
 WhatsInAName09 апр. 2012 г., 18:40
Я не знал, что это имеет значение, потому что я не возводил в квадрат n. Но да, квадрат n-1 тоже будет переполнен.
 09 апр. 2012 г., 18:43
Еслиn очень большой, тоa%n может быть очень большим.

и у вас нет нативнойuint128_t (или аналогичный), вам нужно будет сделать это вручную.

Одним из вариантов является выразитьa как сумма двух 32-битных величин, т.е.a = 232b + c, гдеb содержит 32 msbs, иc содержит 32 фунта Квадрат - это набор из четырех кросс-умножений; каждый результат гарантированно вписывается в 64-битный тип. Затем вы выполняете операцию по модулю, когда вы комбинируете отдельные термины (тщательно принимая во внимание сдвиги, необходимые для перестройки всего).

 09 апр. 2012 г., 18:10
Для downvoter, перечитайте ответ.
 09 апр. 2012 г., 18:25
@WhatsInAName: я не думаю, что Mysticial пытается быть сумасшедшим ...
 09 апр. 2012 г., 18:21
@WhatsInAName По сути, Оли говорит вам, чтобы вы делали длинное умножение и длинное деление так же, как вы делали это в начальной школе.
 WhatsInAName09 апр. 2012 г., 18:24
@ Мистик Я уверен, что они не преподают битрейфтинг и модульную арифметику в начальной школе. Пожалуйста, держите snarkiness до минимума. Это явно не то, о чем я спрашиваю.
 09 апр. 2012 г., 18:27
@WhatsInAName Я не пытаюсь быть хитрым - извиняюсь, если вы так поступили. В арифметике начальной школы вы «сдвигаетесь» цифры. В компьютерах вы «сдвигаете» биты. Это все то же самое, за исключением другой базы.

a * b % mбез переполнений, независимо от размера a, b и m.

(Обратите внимание, чтоres -= m а такжеtemp_b -= m для получения ожидаемых результатов в строках используется 64-разрядное целое число без знака. Это должно быть хорошо, поскольку переполнение целых чисел без знака хорошо определено в C и C ++. По этой причине этоважно использоватьunsigned integer types.)

uint64_t mulmod(uint64_t a, uint64_t b, uint64_t m) {
    uint64_t res = 0;
    uint64_t temp_b;

    /* Only needed if b may be >= m */
    if (b >= m) {
        if (m > UINT64_MAX / 2u)
          ,  b -= m;
        else
            b %= m;
    }

    while (a != 0) {
        if (a & 1) {
            /* Add b to res, modulo m, without overflow */
            if (b >= m - res) /* Equiv to if (res + b >= m), without overflow */
                res -= m;
            res += b;
        }
        a >>= 1;

        /* Double b, modulo m */
        temp_b = b;
        if (b >= m - b)       /* Equiv to if (2 * b >= m), without overflow */
            temp_b -= m;
        b += temp_b;
    }
    return res;
}

Этомоя модификация издругой ответ на другой похожий вопрос.

что вам это больше не нужно, и есть альтернативное решение, но я хочу добавить альтернативный метод для его реализации. Он предоставляет два разных метода:удвоить и добавить алгоритми метод обработкиmod(a + b, n) с обнаружением переполнения.

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

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

unsigned addmod(unsigned x, unsigned y, unsigned n)
{
    // Precondition: x<n, y<n
    // If it will overflow, use alternative calculation
    if (x + y <= x) x = x - (n - y);
    else x = (x + y) % n;
    return x;
}

unsigned sqrmod(unsigned a, unsigned n)
{
    unsigned b;
    unsigned sum = 0;

    // Make sure original number is less than n
    a = a % n;

    // Use double and add algorithm to calculate a*a mod n
    for (b = a; b != 0; b >>= 1) {
        if (b & 1) {
            sum = addmod(sum, a, n);
        }
        a = addmod(a, a, n);
    }
    return sum;
}
 09 апр. 2012 г., 22:17
@OliCharlesworth рассчитывает(x+y)%n без переполнения. Не переполнение легко доказать. и х и у меньшеn (и, следовательно, максимальный размер слова), и мы только вычитаем числа, поэтому они идут только вниз, что означает, что они никогда не переполнятся. Чтобы доказатьx - (n - y) правильно немного сложнее. Во-первых, поскольку он переполнен,x+y явно больше, чемn, Кроме того, так как обаx а такжеy меньше чемn, x+y меньше чем2*n, поэтому модуль равен(x+y)-n, Если ты пишешьx+y какx-(-y) и переставив термины, вы получите формулу, которую я использовал.
 09 апр. 2012 г., 21:05
x = x - (n - y) - Вы уверены, что делаете что-нибудь полезное?
 29 окт. 2013 г., 06:52
addmod() нужен комментарий о том, что предварительным условием является то, чтоx < n а такжеy < n.
 09 апр. 2012 г., 22:23
@OliCharlesworth Я думаю, вы можете использовать альтернативную формулу(x+y)+2^W-n вместоx-(n-y), но я не пробовал. Это позволило бы нам рассчитатьx+y только один раз вaddmul.
 30 окт. 2013 г., 18:51
@CraigMcQueen Да. Это не очевидно. Я редактирую ответ, чтобы добавить его.

n каждый прогон и изменение результата сразу.

 WhatsInAName09 апр. 2012 г., 18:08
Мне потребуется слишком много времени, чтобы перебрать a-значение, чтобы сделать это
 09 апр. 2012 г., 18:09
@OrgnlDave: этого было бы достаточно, чтобы переполнить 32-битное int. Для 64-битного int вам нужно что-то примерно в 4 миллиарда раз больше. (Или вы имеете в виду, что два входа превышают 4 миллиарда, поэтому их умножение переполняет 64-битное целое число?)
 09 апр. 2012 г., 18:07
Вы понимаете, что он говорит о цифрах свыше 4 миллиардов, верно? Вот что нужно, чтобы переполнить 64-битное int ...

Ваш ответ на вопрос