10 ответов:
хорошо, так что вы хотите вычислить
a^b mod m. Сначала мы примем наивный подход, а затем посмотрим, как мы можем его усовершенствовать.во-первых, уменьшить
a mod m. Это значит, найти числоa1, так что0 <= a1 < mиa = a1 mod m. Затем многократно в цикле умножьте наa1и снова уменьшитьmod m. Таким образом, в псевдокоде:a1 = a reduced mod m p = 1 for(int i = 1; i <= b; i++) { p *= a1 p = p reduced mod m }делая это, мы избегаем чисел больше, чем
m^2. Это и есть ключ. Причина, по которой мы избегаем чисел больше, чемm^2- это потому, что на каждом шаг0 <= p < mи0 <= a1 < m.в качестве примера, вычислим
5^55 mod 221. Во-первых,5уже снижена5^55 = 112 mod 221.теперь мы можем улучшить это с помощью возведение в степень путем возведения в квадрат; это известный трюк, в котором мы сводим возведение в степень к требованию только
log bумножений вместоb. Обратите внимание, что с алгоритмом, который я описал выше, возведение в степень путем возведения в квадрат улучшения, вы в конечном итоге с двоичный метод справа налево.a1 = a reduced mod m p = 1 while (b > 0) { if (b is odd) { p *= a1 p = p reduced mod m } b /= 2 a1 = (a1 * a1) reduced mod m }таким образом, с 55 = 110111 в двоичный
1 * (5^1 mod 221) = 5 mod 2215 * (5^2 mod 221) = 125 mod 221125 * (5^4 mod 221) = 112 mod 221112 * (5^16 mod 221) = 112 mod 221112 * (5^32 mod 221) = 112 mod 221поэтому ответ
5^55 = 112 mod 221. Причина это работает, потому что55 = 1 + 2 + 4 + 16 + 32, так что
5^55 = 5^(1 + 2 + 4 + 16 + 32) mod 221 = 5^1 * 5^2 * 5^4 * 5^16 * 5^32 mod 221 = 5 * 25 * 183 * 1 * 1 mod 221 = 22875 mod 221 = 112 mod 221в шаге, где мы вычисляем
5^1 mod 221,5^2 mod 221и т. д. отметим, что5^(2^k)=5^(2^(k-1)) * 5^(2^(k-1)), потому что2^k = 2^(k-1) + 2^(k-1)так что мы можем сначала вычислить5^1и уменьшитьmod 221, тогда квадрат это и уменьшитьmod 221получить5^2 mod 221и т. д.выше алгоритм формализует эту идею.
чтобы добавить к ответу Джейсона:
вы можете ускорить процесс (Что может быть полезно для очень больших показателей), используя двоичное расширение показателя. Сначала вычислить 5, 5^2, 5^4, 5^8 мод 221 - вы можете сделать это путем повторного возведения в квадрат:
5^1 = 5(mod 221) 5^2 = 5^2 (mod 221) = 25(mod 221) 5^4 = (5^2)^2 = 25^2(mod 221) = 625 (mod 221) = 183(mod221) 5^8 = (5^4)^2 = 183^2(mod 221) = 33489 (mod 221) = 118(mod 221) 5^16 = (5^8)^2 = 118^2(mod 221) = 13924 (mod 221) = 1(mod 221) 5^32 = (5^16)^2 = 1^2(mod 221) = 1(mod 221)теперь мы можем написать
55 = 1 + 2 + 4 + 16 + 32 so 5^55 = 5^1 * 5^2 * 5^4 * 5^16 * 5^32 = 5 * 25 * 625 * 1 * 1 (mod 221) = 125 * 625 (mod 221) = 125 * 183 (mod 183) - because 625 = 183 (mod 221) = 22875 ( mod 221) = 112 (mod 221)вы можете видеть, как для очень больших показателей это будет намного быстрее (я считаю, что это лог, а не линейный в b, но не уверен.)
/* The algorithm is from the book "Discrete Mathematics and Its Applications 5th Edition" by Kenneth H. Rosen. (base^exp)%mod */ int modular(int base, unsigned int exp, unsigned int mod) { int x = 1; int power = base % mod; for (int i = 0; i < sizeof(int) * 8; i++) { int least_sig_bit = 0x00000001 & (exp >> i); if (least_sig_bit) x = (x * power) % mod; power = (power * power) % mod; } return x; }
5^55 mod221 = ( 5^10 * 5^10 * 5^10 * 5^10 * 5^10 * 5^5) mod221 = ( ( 5^10) mod221 * 5^10 * 5^10 * 5^10 * 5^10 * 5^5) mod221 = ( 77 * 5^10 * 5^10 * 5^10 * 5^10 * 5^5) mod221 = ( ( 77 * 5^10) mod221 * 5^10 * 5^10 * 5^10 * 5^5) mod221 = ( 183 * 5^10 * 5^10 * 5^10 * 5^5) mod221 = ( ( 183 * 5^10) mod221 * 5^10 * 5^10 * 5^5) mod221 = ( 168 * 5^10 * 5^10 * 5^5) mod221 = ( ( 168 * 5^10) mod 221 * 5^10 * 5^5) mod221 = ( 118 * 5^10 * 5^5) mod221 = ( ( 118 * 5^10) mod 221 * 5^5) mod221 = ( 25 * 5^5) mod221 = 112
то, что вы ищете, - это модульное возведение в степень, в частности модульное двоичное возведение в степень. Это ссылка на Википедию есть псевдокод.
Китайская Теорема Остатка приходит на ум как начальная точка, как 221 = 13 * 17. Итак, разбейте это на 2 части, которые объединяются в конце концов, один для мод 13 и один для мод 17. Во-вторых, я считаю, что есть некоторое доказательство a^(p-1) = 1 mod p для всех ненулевых a, что также помогает уменьшить вашу проблему, поскольку 5^55 становится 5^3 для случая mod 13 Как 13*4=52. Если вы посмотрите в разделе "конечные поля", вы можете найти некоторые хорошие результаты о том, как это решить.
изменить: Причина, по которой я упоминаю факторы, заключается в том, что это создает способ разложения нуля на ненулевые элементы, как если бы вы попробовали что-то вроде 13^2 * 17^4 mod 221, ответ равен нулю, так как 13*17=221. Многие большие числа не будут простыми, хотя есть способы найти большие простые числа, поскольку они часто используются в криптографии и других областях математики.
Это часть кода, который я сделал для проверки IBAN. Не стесняйтесь использовать.
static void Main(string[] args) { int modulo = 97; string input = Reverse("100020778788920323232343433"); int result = 0; int lastRowValue = 1; for (int i = 0; i < input.Length; i++) { // Calculating the modulus of a large number Wikipedia http://en.wikipedia.org/wiki/International_Bank_Account_Number if (i > 0) { lastRowValue = ModuloByDigits(lastRowValue, modulo); } result += lastRowValue * int.Parse(input[i].ToString()); } result = result % modulo; Console.WriteLine(string.Format("Result: {0}", result)); } public static int ModuloByDigits(int previousValue, int modulo) { // Calculating the modulus of a large number Wikipedia http://en.wikipedia.org/wiki/International_Bank_Account_Number return ((previousValue * 10) % modulo); } public static string Reverse(string input) { char[] arr = input.ToCharArray(); Array.Reverse(arr); return new string(arr); }
ответ Джейсона на Java (Примечание
i < exp).private static void testModulus() { int bse = 5, exp = 55, mod = 221; int a1 = bse % mod; int p = 1; System.out.println("1. " + (p % mod) + " * " + bse + " = " + (p % mod) * bse + " mod " + mod); for (int i = 1; i < exp; i++) { p *= a1; System.out.println((i + 1) + ". " + (p % mod) + " * " + bse + " = " + ((p % mod) * bse) % mod + " mod " + mod); p = (p % mod); } }
это называется модульным возведением в степень(https://en.wikipedia.org/wiki/Modular_exponentiation).
предположим, у вас есть следующее выражение:
19 ^ 3 mod 7вместо питания 19 непосредственно вы можете сделать следующее:
(((19 mod 7) * 19) mod 7) * 19) mod 7но это может занять также много времени из-за большого количества последовательных умножений, и поэтому вы можете умножать на квадратные значения:
x mod N -> x ^ 2 mod N -> x ^ 4 mod -> ... x ^ 2 |log y| mod Nмодульный алгоритм возведения в степень делает предположения что:
x ^ y == (x ^ |y/2|) ^ 2 if y is even x ^ y == x * ((x ^ |y/2|) ^ 2) if y is oddи поэтому рекурсивный модульный алгоритм возведения в степень будет выглядеть так в java:
/** * Modular exponentiation algorithm * @param x Assumption: x >= 0 * @param y Assumption: y >= 0 * @param N Assumption: N > 0 * @return x ^ y mod N */ public static long modExp(long x, long y, long N) { if(y == 0) return 1 % N; long z = modExp(x, Math.abs(y/2), N); if(y % 2 == 0) return (long) ((Math.pow(z, 2)) % N); return (long) ((x * Math.pow(z, 2)) % N); }отдельное спасибо @chux для найденной ошибки с неверным возвращаемым значением в случае сравнения y и 0.
просто предоставьте еще одну реализацию ответа Джейсона C.
после обсуждения с моими одноклассниками, основываясь на объяснении Джейсона, мне больше нравится рекурсивная версия, если вы не очень заботитесь о производительности:
например:
#include<stdio.h> int mypow( int base, int pow, int mod ){ if( pow == 0 ) return 1; if( pow % 2 == 0 ){ int tmp = mypow( base, pow >> 1, mod ); return tmp * tmp % mod; } else{ return base * mypow( base, pow - 1, mod ) % mod; } } int main(){ printf("%d", mypow(5,55,221)); return 0; }
Comments