math - hallar - ¿Cómo calcular el módulo de números grandes?
calcular el modulo y el argumento de un numero complejo (10)
Esto es parte del código que hice para la validación de IBAN. Siéntase libre de usar.
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);
}
Cómo calcular el módulo de 5 ^ 55 módulo 221 sin mucho uso de la calculadora?
Supongo que hay algunos principios simples en la teoría de números en la criptografía para calcular tales cosas.
Esto se denomina exponenciación modular ( https://en.wikipedia.org/wiki/Modular_exponentiation ).
Supongamos que tiene la siguiente expresión:
19 ^ 3 mod 7
En lugar de activar 19 directamente, puede hacer lo siguiente:
(((19 mod 7) * 19) mod 7) * 19) mod 7
Pero esto también puede llevar mucho tiempo debido a una gran cantidad de multiplicaciones secuenciales, por lo que puedes multiplicar en valores al cuadrado:
x mod N -> x ^ 2 mod N -> x ^ 4 mod -> ... x ^ 2 |log y| mod N
El algoritmo de exponenciación modular hace suposiciones de que:
x ^ y == (x ^ |y/2|) ^ 2 if y is even
x ^ y == x * ((x ^ |y/2|) ^ 2) if y is odd
Y el algoritmo de exponenciación modular recursivo se verá así en 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);
}
Un agradecimiento especial a chux por el error encontrado con un valor de retorno incorrecto en el caso de la comparación yy 0.
La respuesta de Jason en Java (nota 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);
}
}
Lo que está buscando es exponenciación modular, específicamente exponenciación binaria modular. Este enlace de wikipedia tiene pseudocódigo.
Para agregar a la respuesta de Jason:
Puede acelerar el proceso (lo que podría ser útil para exponentes muy grandes) utilizando la expansión binaria del exponente. Primero calcule 5, 5 ^ 2, 5 ^ 4, 5 ^ 8 mod 221 - usted hace esto al cuadrar repetidamente:
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)
Ahora podemos escribir
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)
Puedes ver cómo para exponentes muy grandes esto será mucho más rápido (creo que es log en lugar de lineal en b, pero no es cierto).
Simplemente proporcione otra implementación de la respuesta de Jason por C.
Después de discutir con mis compañeros de clase, en base a la explicación de Jason, me gusta más la versión recursiva si no te importa mucho el rendimiento:
Por ejemplo:
#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;
}
El teorema del remanente chino viene a la mente como un punto inicial como 221 = 13 * 17. Entonces, divide esto en 2 partes que se combinan al final, una para la mod 13 y otra para la mod 17. En segundo lugar, creo que hay alguna prueba de a ^ (p-1) = 1 mod p para todo no cero a, que también ayuda a reducir su problema, ya que 5 ^ 55 se convierte en 5 ^ 3 para el caso de mod 13 como 13 * 4 = 52. Si miras bajo el tema de "Campos finitos", puedes encontrar algunos buenos resultados sobre cómo resolver esto.
EDITAR: La razón por la que menciono los factores es que esto crea una forma de factorizar cero en elementos distintos de cero, como si hubiera intentado algo como 13 ^ 2 * 17 ^ 4 mod 221, la respuesta es cero desde 13 * 17 = 221. Una gran cantidad de números grandes no van a ser primos, aunque hay formas de encontrar números primos grandes ya que se usan mucho en criptografía y otras áreas dentro de Matemáticas.
De acuerdo, entonces quieres calcular a^b mod m
. Primero tomaremos un enfoque ingenuo y luego veremos cómo podemos refinarlo.
Primero, reduce a mod m
. Eso significa, encontrar un número a1
para que 0 <= a1 < m
y a = a1 mod m
. Luego repetidamente en un ciclo multiplique por a1
y reduzca de nuevo mod m
. Por lo tanto, en pseudocódigo:
a1 = a reduced mod m
p = 1
for(int i = 1; i <= b; i++) {
p *= a1
p = p reduced mod m
}
Al hacer esto, evitamos números mayores que m^2
. Esta es la clave. La razón por la que evitamos números mayores que m^2
es porque en cada paso 0 <= p < m
0 <= a1 < m
.
Como ejemplo, calculemos 5^55 mod 221
. Primero, 5
ya está reducido 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
Por lo tanto, 5^55 = 112 mod 221
.
Ahora, podemos mejorar esto usando la exponenciación cuadrando ; este es el famoso truco en el que reducimos la exponenciación para requerir solo multiplicaciones de log b
lugar de b
. Tenga en cuenta que con el algoritmo que describí anteriormente, la exponenciación por mejora de cuadratura, termina con el método binario de derecha a izquierda .
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
}
Por lo tanto, desde 55 = 110111 en binario
-
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
Por lo tanto, la respuesta es 5^55 = 112 mod 221
. La razón por la que esto funciona es porque
55 = 1 + 2 + 4 + 16 + 32
así que eso
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
En el paso donde calculamos 5^1 mod 221
, 5^2 mod 221
, etc. notamos que 5^(2^k)
= 5^(2^(k-1)) * 5^(2^(k-1))
porque 2^k = 2^(k-1) + 2^(k-1)
para que primero podamos calcular 5^1
y reducir el mod 221
, luego cuadrar esto y reducir el mod 221
para obtener 5^2 mod 221
, etc.
El algoritmo anterior formaliza esta idea.
/* 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