Быстрый способ вручную изменить номер

Question

Мне нужно иметь возможность рассчитать (a ^ b)% c для очень больших значений a и b (которые по отдельности устанавливают предел и вызывают ошибки переполнения при попытке вычислить a ^ b). Для достаточно малых чисел использование идентификатора (a ^ b)% c = (a% c) ^ b% c работает, но если c слишком велико, это действительно не поможет. Я написал цикл для выполнения операции мод вручную, по одному:

private static long no_Overflow_Mod(ulong num_base, ulong num_exponent, ulong mod) 
    {
        long answer = 1;
        for (int x = 0; x < num_exponent; x++)
        {
            answer = (answer * num_base) % mod;
        }
        return answer;
    }

но это занимает очень много времени. Есть ли простой и быстрый способ выполнить эту операцию, не прибегая к степени b и не используя трудоемких циклов? Если ничего не помогает, я могу создать массив bool для представления огромного типа данных и выяснить, как сделать это с помощью побитовых операторов, но должен быть лучший способ.

Answer 1

Я думаю, вы ищете: http://en.wikipedia.org/wiki/Montgomery_reduction или более простой способ, основанный на модульном экспонировании (из википедии)

Bignum modpow(Bignum base, Bignum exponent, Bignum modulus) {

    Bignum result = 1;

    while (exponent > 0) {
        if ((exponent & 1) == 1) {
            // multiply in this bit's contribution while using modulus to keep result small
            result = (result * base) % modulus;
        }
        // move to the next bit of the exponent, square (and mod) the base accordingly
        exponent >>= 1;
        base = (base * base) % modulus;
    }

    return result;
}

Answer 2

Быстрое модульное экспонирование (думаю, так оно и называется) может работать.

Given a, b, c and a^b (mod c):

1. Write b as a sum of powers of 2. (If b=72, this is 2^6 + 2^3 )
2. Do:
    (1) a^2 (mod c) = a*
    (2) (a*)^2 (mod c) = a*
    (3) (a*)^2 (mod c) = a*
    ...
    (n) (a*)^2 (mod c) = a*

3. Using the a* from above, multiply the a* for the powers of 2 you identified. For example:
    b = 72, use a* at 3 and a* at 6.
    a*(3) x a*(6) (mod c)

4. Do the previous step one multiplication at a time and at the end, you'll have a^b % c.

Теперь, как вы собираетесь это делать с типами данных, я не знаю. Пока ваш тип данных может поддерживать c ^ ​​2, я думаю, вы будете в порядке.

Если используются строки, просто создайте строковые версии сложения, вычитания и умножения (не слишком сложно). Этот метод должен быть достаточно быстрым, делая это. (и вы можете начать шаг 1 с помощью мода c, чтобы a никогда не превышало c).

РЕДАКТИРОВАТЬ: О, смотри, вики-страницу на Модульное экспонирование .

Answer 3

Вот пример быстрого модульного экспонирования (предложено в одном из предыдущих ответов) в Java. Не должно быть слишком сложно преобразовать это в C #

http://www.math.umn.edu/~garrett/crypto/a01/FastPow.html

и источник ...

http://www.math.umn.edu/~garrett/crypto/a01/FastPow.java

Answer 4

В Python есть pow (a, b, c), который возвращает (a ** b)% c (только быстрее), поэтому должен быть какой-то умный способ сделать это. Может быть, они просто делают личность, которую вы упомянули.

Answer 5

Мне кажется, что есть какая-то связь между мощью и модом. Power - это просто повторное умножение, а мод связан с делением. Мы знаем, что умножение и деление являются обратными, поэтому я предположил бы, что благодаря этой связи существует корреляция между мощностью и модом.

Например, взять полномочия 5:

5 % 4 = 1
25 % 4 = 1
125 % 4 = 1
625 % 4 = 1
...

Шаблон ясен, что 5 ^ b% 4 = 1 для всех значений b.

В этой ситуации менее ясно:

5 % 3 = 2
25 % 3 = 1
125 % 3 = 2
625 % 3 = 1
3125 % 3 = 2
15625 % 3 = 1
78125 % 3 = 2
...

Но есть еще шаблон.

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

Answer 6

Вы можете попробовать разложить 'a' на достаточно малые числа.

Если множителями 'a' являются 'x', 'y' и 'z', то

a ^ b = (x ^ b) (y ^ b) (z ^ b).

Тогда вы можете использовать свою личность: (a ^ b)% c = (a% c) ^ b% c

Answer 7

Вы можете попробовать это:

C #: выполнение операции модуля (мода) для очень большого числа (> Int64.MaxValue)
http://www.del337ed.com/blog/index.php/2009/02/04/c-doing-a-modulus-mod-operation-on-a-very-large-number-int64maxvalue/

Answer 8

Я бы порекомендовал проверить документацию Decimal и посмотреть, соответствует ли она вашим требованиям, так как она встроенного типа и может использовать оператор мод Если нет, то вам понадобится библиотека произвольной точности, например, Bignum в java.

Answer 9

Если не считать написания собственного быстрого модульного возведения в степень , самая простая идея, которую я могу придумать, - это использовать тип F # BigInt: Microsoft.FSharp.Math.Types.BigInt, который поддерживает операции с произвольно большим масштабом, включая возведение в степень и модульное арифметика.

Это встроенный тип, который станет частью полной платформы .NET со следующим выпуском. Вам не нужно использовать F # для использования BitInt - вы можете использовать его непосредственно в C #.

Answer 10

Похоже на домашнее задание по криптографии.

Подсказка: посмотрите Маленькая теорема Ферма .