solo - residuo en c#

El operador de módulo(%) da un resultado diferente para diferentes versiones de.NET en C#

Question

Estoy encriptando la entrada del usuario para generar una cadena para la contraseña. Pero una línea de código ofrece resultados diferentes en diferentes versiones del marco. Código parcial con el valor de la tecla presionada por el usuario:

Tecla presionada: 1. ascii variable es 49. Valor de ''e'' y ''n'' después de algunos cálculos:

e = 103, 
n = 143,

Math.Pow(ascii, e) % n

Resultado del código anterior:

• En .NET 3.5 (C #)

  Math.Pow(ascii, e) % n

  da 9.0 .

• En .NET 4 (C #)

  Math.Pow(ascii, e) % n

  da 77.0 .

Math.Pow() da el resultado correcto (mismo) en ambas versiones.

¿Cuál es la causa y existe una solución?

Answer 1

Aparte del hecho de que su función de hash no es muy buena ^* , el mayor problema con su código no es que devuelva un número diferente según la versión de .NET, sino que en ambos casos devuelve un número completamente sin sentido: la respuesta correcta al problema es

49 ¹⁰³ mod 143 = es 114. ( enlace a Wolfram Alpha )

Puede usar este código para calcular esta respuesta:

private static int PowMod(int a, int b, int mod) {
    if (b == 0) {
        return 1;
    }
    var tmp = PowMod(a, b/2, mod);
    tmp *= tmp;
    if (b%2 != 0) {
        tmp *= a;
    }
    return tmp%mod;
}

La razón por la que su cálculo produce un resultado diferente es que para producir una respuesta, utiliza un valor intermedio que deja caer la mayoría de los dígitos significativos del número 49 ¹⁰³ : ¡solo los primeros 16 de sus 175 dígitos son correctos!

1230824813134842807283798520430636310264067713738977819859474030746648511411697029659004340261471771152928833391663821316264359104254030819694748088798262075483562075061997649

Los 159 dígitos restantes son todos incorrectos. Sin embargo, la operación de modificación busca un resultado que requiera que cada dígito sea correcto, incluidos los últimos. Por lo tanto, incluso la mejora más Math.Pow a la precisión de Math.Pow que puede haberse implementado en .NET 4, daría lugar a una diferencia drástica de su cálculo, que esencialmente produce un resultado arbitrario.

^* Dado que esta pregunta se refiere a elevar enteros a las altas potencias en el contexto del hashing de contraseñas, puede ser una buena idea leer este _{enlace de} respuesta antes de decidir si su enfoque actual debería cambiarse por uno potencialmente mejor.

Answer 2

Hay muchas respuestas sobre la forma en que el código es malo. Sin embargo, en cuanto a por qué el resultado es diferente ...

Las FPUs de Intel usan el formato de 80 bits internamente para obtener más precisión para los resultados intermedios. Entonces, si hay un valor en el registro del procesador, obtiene 80 bits, pero cuando se escribe en la pila, se almacena en 64 bits .

Espero que la versión más nueva de .NET tenga un mejor optimizador en su compilación Just in Time (JIT), por lo que mantiene un valor en un registro en lugar de escribirlo en la pila y luego leerlo nuevamente desde la pila.

Es posible que el JIT ahora pueda devolver un valor en un registro en lugar de en la pila. O pase el valor a la función MOD en un registro.

Consulte también Pregunta de desbordamiento de pila ¿ Cuáles son las aplicaciones / beneficios de un tipo de datos de precisión extendida de 80 bits?

Otros procesadores, por ejemplo, el ARM darán resultados diferentes para este código.

Answer 3

La precisión del punto flotante puede variar de una máquina a otra e incluso en la misma máquina .

Sin embargo, .NET crea una máquina virtual para sus aplicaciones ... pero hay cambios de una versión a otra.

Por lo tanto, no debe confiar en que produzca resultados consistentes. Para el cifrado, use las clases proporcionadas por el Framework en lugar de desplegar las suyas propias.

Answer 4

Lo que ves es un error de redondeo en doble. Math.Pow funciona con el doble y la diferencia es la siguiente:

.NET 2.0 y 3.5 => var powerResult = Math.Pow(ascii, e); devoluciones:

1.2308248131348429E+174

.NET 4.0 y 4.5 => var powerResult = Math.Pow(ascii, e); devoluciones:

1.2308248131348427E+174

Observe el último dígito antes de E y eso está causando la diferencia en el resultado. No es el operador de módulo (%) .

Answer 5

Tal vez sea mejor calcularlo usted mismo usando solamente aritmética de enteros. Algo como:

int n = 143;
int e = 103;
int result = 1;
int ascii = (int) ''a'';

for (i = 0; i < e; ++i) 
    result = result * ascii % n;

Puede comparar el rendimiento con el rendimiento de la solución BigInteger publicada en las otras respuestas.

Answer 6

Math.Pow funciona en números de punto flotante de precisión doble; por lo tanto, no debe esperar que los primeros 15-17 dígitos del resultado sean precisos:

Todos los números de punto flotante también tienen un número limitado de dígitos significativos, que también determina con qué precisión un valor de coma flotante se aproxima a un número real. Un valor Double tiene hasta 15 dígitos decimales de precisión, aunque un máximo de 17 dígitos se mantiene internamente.

Sin embargo, la aritmética de módulo requiere que todos los dígitos sean precisos. En su caso, está calculando 49 ¹⁰³ , cuyo resultado consta de 175 dígitos, lo que hace que la operación del módulo carezca de sentido en ambas respuestas.

Para calcular el valor correcto, debe usar la aritmética de precisión arbitraria, tal como lo proporciona la clase BigInteger (presentada en .NET 4.0).

int val = (int)(BigInteger.Pow(49, 103) % 143);   // gives 114

Editar : Como señaló Mark Peters en los comentarios a continuación, debe utilizar el método BigInteger.ModPow , que está destinado específicamente para este tipo de operación:

int val = (int)BigInteger.ModPow(49, 103, 143);   // gives 114