numero hallar conjugado complejo como calcular argumento math modulo

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. 1 * 5 = 5 mod 221
  2. 5 * 5 = 25 mod 221
  3. 25 * 5 = 125 mod 221
  4. 125 * 5 = 183 mod 221
  5. 183 * 5 = 31 mod 221
  6. 31 * 5 = 155 mod 221
  7. 155 * 5 = 112 mod 221
  8. 112 * 5 = 118 mod 221
  9. 118 * 5 = 148 mod 221
  10. 148 * 5 = 77 mod 221
  11. 77 * 5 = 164 mod 221
  12. 164 * 5 = 157 mod 221
  13. 157 * 5 = 122 mod 221
  14. 122 * 5 = 168 mod 221
  15. 168 * 5 = 177 mod 221
  16. 177 * 5 = 1 mod 221
  17. 1 * 5 = 5 mod 221
  18. 5 * 5 = 25 mod 221
  19. 25 * 5 = 125 mod 221
  20. 125 * 5 = 183 mod 221
  21. 183 * 5 = 31 mod 221
  22. 31 * 5 = 155 mod 221
  23. 155 * 5 = 112 mod 221
  24. 112 * 5 = 118 mod 221
  25. 118 * 5 = 148 mod 221
  26. 148 * 5 = 77 mod 221
  27. 77 * 5 = 164 mod 221
  28. 164 * 5 = 157 mod 221
  29. 157 * 5 = 122 mod 221
  30. 122 * 5 = 168 mod 221
  31. 168 * 5 = 177 mod 221
  32. 177 * 5 = 1 mod 221
  33. 1 * 5 = 5 mod 221
  34. 5 * 5 = 25 mod 221
  35. 25 * 5 = 125 mod 221
  36. 125 * 5 = 183 mod 221
  37. 183 * 5 = 31 mod 221
  38. 31 * 5 = 155 mod 221
  39. 155 * 5 = 112 mod 221
  40. 112 * 5 = 118 mod 221
  41. 118 * 5 = 148 mod 221
  42. 148 * 5 = 77 mod 221
  43. 77 * 5 = 164 mod 221
  44. 164 * 5 = 157 mod 221
  45. 157 * 5 = 122 mod 221
  46. 122 * 5 = 168 mod 221
  47. 168 * 5 = 177 mod 221
  48. 177 * 5 = 1 mod 221
  49. 1 * 5 = 5 mod 221
  50. 5 * 5 = 25 mod 221
  51. 25 * 5 = 125 mod 221
  52. 125 * 5 = 183 mod 221
  53. 183 * 5 = 31 mod 221
  54. 31 * 5 = 155 mod 221
  55. 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. 1 * (5^1 mod 221) = 5 mod 221
  2. 5 * (5^2 mod 221) = 125 mod 221
  3. 125 * (5^4 mod 221) = 112 mod 221
  4. 112 * (5^16 mod 221) = 112 mod 221
  5. 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