Как рассчитать модуль 5 ^ 55 по модулю 221 без особого использования калькулятора?
Я предполагаю, что в теории чисел в криптографии есть несколько простых принципов для вычисления таких вещей.
Как рассчитать модуль 5 ^ 55 по модулю 221 без особого использования калькулятора?
Я предполагаю, что в теории чисел в криптографии есть несколько простых принципов для вычисления таких вещей.
Итак, вы хотите вычислить 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
уже уменьшено mod 221
.
1 * 5 = 5 mod 221
5 * 5 = 25 mod 221
25 * 5 = 125 mod 221
125 * 5 = 183 mod 221
183 * 5 = 31 mod 221
31 * 5 = 155 mod 221
155 * 5 = 112 mod 221
112 * 5 = 118 mod 221
118 * 5 = 148 mod 221
148 * 5 = 77 mod 221
77 * 5 = 164 mod 221
164 * 5 = 157 mod 221
157 * 5 = 122 mod 221
122 * 5 = 168 mod 221
168 * 5 = 177 mod 221
177 * 5 = 1 mod 221
1 * 5 = 5 mod 221
5 * 5 = 25 mod 221
25 * 5 = 125 mod 221
125 * 5 = 183 mod 221
183 * 5 = 31 mod 221
31 * 5 = 155 mod 221
155 * 5 = 112 mod 221
112 * 5 = 118 mod 221
118 * 5 = 148 mod 221
148 * 5 = 77 mod 221
77 * 5 = 164 mod 221
164 * 5 = 157 mod 221
157 * 5 = 122 mod 221
122 * 5 = 168 mod 221
168 * 5 = 177 mod 221
177 * 5 = 1 mod 221
1 * 5 = 5 mod 221
5 * 5 = 25 mod 221
25 * 5 = 125 mod 221
125 * 5 = 183 mod 221
183 * 5 = 31 mod 221
31 * 5 = 155 mod 221
155 * 5 = 112 mod 221
112 * 5 = 118 mod 221
118 * 5 = 148 mod 221
148 * 5 = 77 mod 221
77 * 5 = 164 mod 221
164 * 5 = 157 mod 221
157 * 5 = 122 mod 221
122 * 5 = 168 mod 221
168 * 5 = 177 mod 221
177 * 5 = 1 mod 221
1 * 5 = 5 mod 221
5 * 5 = 25 mod 221
25 * 5 = 125 mod 221
125 * 5 = 183 mod 221
183 * 5 = 31 mod 221
31 * 5 = 155 mod 221
155 * 5 = 112 mod 221
Таким образом, 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 221
5 * (5^2 mod 221) = 125 mod 221
125 * (5^4 mod 221) = 112 mod 221
112 * (5^16 mod 221) = 112 mod 221
112 * (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
, и т. д.
Приведенный выше алгоритм формализует эту идею.
%
является оператором модуля. Таким образом, int p = 625 % 221
назначит 183
p
. Вы можете добиться той же функциональности, разделив 625
на 221
как целочисленное деление и получив ответ 2
. Затем вы берете 625 - 2 * 221
, чтобы получить остаток. В данном случае 625 - 2 * 221 = 183
это ответ.
- person jason; 01.02.2010
5^16 == 1 (mod 221)
. Следовательно, 5^k == 5^(k%16) (mod 221)
.
- person Cascabel; 01.02.2010
Чтобы добавить к ответу Джейсона:
Вы можете ускорить процесс (что может быть полезно для очень больших показателей), используя двоичное расширение показателя степени. Сначала вычислите 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, но не уверен).
То, что вы ищете, - это модульное возведение в степень, особенно модульное двоичное возведение в степень. Эта ссылка на википедию содержит псевдокод.
китайская теорема об остатках приходит на ум в качестве начальной точки, поскольку 221 = 13 * 17. Итак, перерыв это делится на 2 части, которые в конце объединяются: одна для мода 13 и одна для мода 17. Во-вторых, я считаю, что есть некоторое доказательство того, что a^(p-1) = 1 mod p для всех ненулевых a, что также помогает уменьшите свою проблему, поскольку 5 ^ 55 становится 5 ^ 3 для случая мода 13, поскольку 13 * 4 = 52. Если вы посмотрите на тему «Конечные поля», вы можете найти хорошие результаты о том, как решить эту проблему.
РЕДАКТИРОВАТЬ: причина, по которой я упоминаю факторы, заключается в том, что это создает способ разложения нуля на ненулевые элементы, как если бы вы попробовали что-то вроде 13 ^ 2 * 17 ^ 4 по модулю 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);
}
}
Просто предоставьте еще одну реализацию ответа Джейсона от 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;
}
Это называется модульным возведением в степень (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.
x * power
и power * power
могут переполняться, когда mod*mod > UINT_MAX + 1
.
- person chux - Reinstate Monica; 10.02.2018
x * power
, чтобы избежать OF. Если их нет, код может использовать это.
- person chux - Reinstate Monica; 30.10.2018