exponenciación modular en Java

necesito una manera de calcular:exponenciación modular en Java

(g^u * y^v) mod p

en Java.

he encontrado este algoritmo para calcular (g^u) mod p:

int modulo(int a,int b,int c) { 
    long x=1 
    long y=a; 
    while(b > 0){ 
     if(b%2 == 1){ 
      x=(x*y)%c; 
     } 
     y = (y*y)%c; // squaring the base 
     b /= 2; 
    } 
    return (int) x%c; 
}

y funciona muy bien, pero me parece que no puede encontrar una manera de hacer esto para

(g^u * y^v) mod p

ya que mis habilidades matemáticas son mediocres.

Para ponerlo en contexto, es para una implementación de Java de un DSA "reducido": la parte de verificación requiere que esto se resuelva.

Fuente

2010-11-01 Carl Hagen

Supongo que p es primordial, ¿no? –

sí, p es primo, creo que esto lo resuelve: (g^u * y^v) mod p = (g^u mod p) * (y^v mod p) mod p, aunque solo lo he probado con números pequeños hasta ahora –

¿Y es grande? La parte 'mod p' me parece como si quisieras usar' BigInteger' en lugar de long. –

Suponiendo que los dos factores que no rebose, creerte puede simplificar una expresión como esa de esta manera:

(x * y) mod p = ((x mod p)*(y mod p)) mod p. Estoy seguro de que puedes resolverlo desde allí.

Fuente

2010-11-01 06:45:51

sí, creo que este es el camino, hasta ahora he hecho pruebas con números pequeños con esto, y parece estar funcionando –

Supongo que probablemente no sea correcto supongamos que los factores no se desbordarán, pero no estoy seguro. –

Los factores no se desbordarán siempre que (p-1) * (p-1) encaje dentro de un 'int'. De lo contrario, tendremos que usar 'long's para xey. El hecho – MAK

Trate

(Math.pow (q, u) * Math.pow (y, v))% p

Fuente

2010-11-01 06:27:47 Rogach

Supongo que la razón por la que él está preguntando es que los números son demasiado grandes para que el simple enfoque funcione ... –

Si ese es el caso, ¿por qué no usar BigInteger? – Nicholas

Math.pow() toma y devuelve dobles. http://download.oracle.com/javase/1.4.2/docs/api/java/lang/Mathhtml # pow% 28double,% 20double% 29 – wnoise

Ese fragmento de código implementa el bien conocido algoritmo de "exponenciación rápida", también conocido como Exponentiation by squaring.

También utiliza el hecho de que (a * b) mod p = ((a mod p) * (b mod p)) mod p. (Tanto la suma como las multiplicaciones son estructuras conservadas que toman un módulo primo; es un homomorfismo). De esta forma, en cada punto del algoritmo reduce a números menores que p.

Si bien puede tratar de calcular estos en forma intercalada en un bucle, no hay un beneficio real para hacerlo. Simplemente calcúlelos por separado, multiplíquelos juntos, y tome el mod por última vez.

Se advirtió que obtendrá desbordamiento si p^2 es mayor que el mayor representable int, y que esto hará que tenga la respuesta incorrecta. Para Java, cambiar a un número entero grande puede ser prudente, o al menos hacer un control de tiempo de ejecución en el tamaño de p y lanzar una excepción.

Por último, si esto es para fines criptográficos, probablemente debería utilizar una biblioteca para hacer esto, en lugar de implementarlo usted mismo. Es muy fácil hacer algo ligeramente incorrecto que parece funcionar, pero proporciona una seguridad mínima o nula.

Fuente

2010-11-01 07:12:49 wnoise

es de hecho para fines criptográficos, pero es para una tarea escolar en la que debemos implementar el DSA. ¡Gracias por tu respuesta perspicaz! –

Respuesta

Cuestiones relacionadas