Forma rápida de modificar manualmente un número

Question

Necesito ser capaz de calcular (a^b)% c para valores muy grandes de ayb (que individualmente están presionando el límite y que causan errores de desbordamiento cuando intenta calcular un^segundo). Para números suficientemente pequeños, usar la identidad (a^b)% c = (a% c)^b% c funciona, pero si c es demasiado grande, esto realmente no ayuda. Escribí un bucle para hacer la operación mod manualmente, una a la vez un:

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; 
    } 

pero esto lleva un tiempo muy largo. ¿Hay alguna manera simple y rápida de hacer esta operación sin tener que tomar un poder de b y sin usar bucles que consumen mucho tiempo? Si todo lo demás falla, puedo crear una matriz de bool para representar un tipo de datos enorme y descubrir cómo hacerlo con operadores bit a bit, pero tiene que haber una forma mejor.

Answer 1

A menos que escriba su propio fast modular exponentiation, la idea más simple que puedo idear es usar el tipo F # BigInt: Microsoft.FSharp.Math.Types.BigInt que admite operaciones a gran escala arbitrariamente, incluida la exponenciación y la aritmética modular.

Es un tipo incorporado que formará parte del completo .NET Framework con la próxima versión. No necesita usar F # para usar BitInt; puede usarlo directamente en C#.

Answer 2

Recomiendo revisar la documentación de Decimal y ver si cumple con sus requisitos, ya que es un tipo incorporado y puede usar el operador de mod. Si no, entonces necesitarás una biblioteca de precisión arbitraria como Bignum de Java.

Answer 3

¿Se puede factorizar a, b, o c? ¿C tiene un rango conocido?

¡Estos son enteros de 32 bits! Ir comprobar esto site

Por ejemplo, aquí es cómo se obtiene el mod de n% d donde d 1 >> s (1,2,4,8, ...)

int n = 137;  // numerator 
    int d = 32;  // denom d will be one of: 1, 2, 4, 8, 16, 32, ... 
    int m;   // m will be n % d 
    m = n & (d - 1); 

Hay código para n% d donde d es 1 >> s - 1 (1, 3, 7, 15, 31, ...)

Esto solo ayudará si c es pequeño, como dijiste.

Answer 4

La exponenciación modular rápida (creo que así es como se llama) podría funcionar.

 
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. 

Ahora, cómo vas a hacer eso con los tipos de datos, no sé. Siempre que su tipo de datos pueda admitir c^2, creo que estará bien.

Si usa cadenas, solo cree cadenas de versiones para sumar, restar y multiplicar (no demasiado). Este método debe ser lo suficientemente rápido para hacer eso. (y puede comenzar el paso 1 con un mod c de modo que a nunca sea mayor que c).

EDITAR: Oh, mira, una página wiki en Modular Exponentiation.

Answer 5

Usted podría intentar esto:

C#: Haciendo una operación de módulo (MOD) en un número muy grande (> 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 6

Usted puede tratar de factorizar 'a' en números suficientemente pequeños.

Si los factores de 'a' son 'x', 'y', y 'z', entonces

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

continuación, puede utilizar su identidad: (a^b)% c = (a% c)^b% c

Answer 7

Me parece que hay algún tipo de relación entre el poder y mod. El poder simplemente se repite la multiplicación y el mod se relaciona con la división. Sabemos que la multiplicación y la división son inversas, por lo que a través de esa conexión asumiría que hay una correlación entre el poder y la mod.

Por ejemplo, tome potencias de 5:

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

El patrón es claro que 5^b% 4 = 1 para todos los valores de b.

Es menos claro en esta situación:

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

Pero todavía hay un patrón.

Si pudieras calcular los cálculos detrás de los patrones, no me sorprendería si pudieras descubrir el valor de la modificación sin utilizar la potencia real.

Answer 8

Python tiene pow (a, b, c) que devuelve (a ** b)% c (solo más rápido), por lo que debe haber alguna forma inteligente de hacerlo. Quizás solo hagan la identidad que mencionaste.

Answer 9

Parece tarea en criptografía.

Sugerencia: echa un vistazo a Fermat's little theorem.

Answer 10

Te supongo buscas: http://en.wikipedia.org/wiki/Montgomery_reduction o la manera más simple basado en modular Exponenciación (de Wikipedia)

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 11

He aquí un ejemplo de rápido modular Exponenciación (sugerido en una de las respuestas anteriores) en Java . No debería ser muy difícil de convertir eso en C#

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

y la fuente ...

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