formas mejores para poner en práctica una operación de módulo (pregunta algoritmo)

Question

que han estado tratando de implementar un exponenciador modular recientemente. Estoy escribiendo el código en VHDL, pero estoy buscando consejos de naturaleza más algorítmica. El componente principal del exponenciador modular es un multiplicador modular que también tengo que implementar yo mismo. No he tenido ningún problema con el algoritmo de multiplicación, solo está agregando y cambiando, y he hecho un buen trabajo al determinar qué significan todas mis variables para poder multiplicarlas en un tiempo bastante razonable.

El problema que estoy teniendo es con la implementación de la operación de módulo en el multiplicador. Sé que realizar repetidas restas funcionará, pero también será lento. Descubrí que podía cambiar el módulo para restar efectivamente grandes múltiplos del módulo, pero creo que aún podría haber mejores formas de hacerlo. El algoritmo que estoy usando algo como esto funciona (pseudocódigo raro sigue):

result,modulus : integer (n bits) (previously defined) 
shiftcount : integer (initialized to zero) 
while((modulus<result) and (modulus(n-1) != 1)){ 
    modulus = modulus << 1 
    shiftcount++ 
} 
for(i=shiftcount;i>=0;i--){ 
    if(modulus<result){result = result-modulus} 
    if(i!=0){modulus = modulus >> 1} 
} 

Así que ... esto es un buen algoritmo, o al menos un buen lugar para empezar? Wikipedia realmente no discute los algoritmos para implementar la operación de módulo, y cada vez que trato de buscar en otra parte, encuentro artículos de investigación y publicaciones realmente interesantes pero increíblemente complicados (ya menudo no relacionados). Si hay una forma obvia de implementar esto que no estoy viendo, realmente agradecería algunos comentarios.

Answer 1

Para modulo en sí, no estoy seguro. Para módulo como parte de la operación exponencial modular más grande, ¿buscó Montgomery multiplication como se menciona en la página de wikipedia en modular exponentiation? Ha pasado un tiempo desde que investigué este tipo de algoritmo, pero por lo que recuerdo, se usa comúnmente en exponenciación modular rápida.

edit: Por lo que sea, su algoritmo de módulo parece correcto a primera vista. Básicamente estás haciendo una división que es un algoritmo de resta repetido.

Answer 2

no estoy seguro de lo que estás calculando allí para ser honesto. Usted habla sobre el funcionamiento del módulo, pero generalmente una operación de módulo está entre dos números a y b, y su resultado es el resto de la división a entre b. ¿Dónde está el a y b en su pseudocódigo ...?

De todos modos, tal vez esto ayude: a mod b = a - floor(a/b) * b.

No sé si esto es más rápido o no, depende de si puedes o no dividir y multiplicar más rápido que muchas sustracciones.

Otra forma de acelerar el enfoque de la resta es utilizar la búsqueda binaria. Si desea a mod b, debe restar b de a hasta que a sea menor que b. Así que, básicamente, es necesario encontrar k tal que:

a - k*b < b, k is min

Una forma de encontrar este k es una búsqueda lineal:

k = 0; 
while (a - k*b >= b) 
    ++k; 

return a - k*b; 

Pero también se puede búsqueda binaria que (sólo corrió algunas pruebas pero funcionó en todos ellos):

k = 0; 
left = 0, right = a 
while (left < right) 
{ 
    m = (left + right)/2; 
    if (a - m*b >= b) 
     left = m + 1; 
    else 
     right = m; 
} 

return a - left*b; 

supongo la solución de búsqueda binaria será más rápido cuando el acuerdo ing con grandes números.

Si se desea calcular a mod b y sólo a es un número grande (se puede almacenar b en un tipo de datos primitivo), que puede hacer que sea aún más rápido:

for each digit p of a do 
    mod = (mod * 10 + p) % b 
return mod 

Esto funciona porque podemos escribir a como a_n*10^n + a_(n-1)*10^(n-1) + ... + a_1*10^0 = (((a_n * 10 + a_(n-1)) * 10 + a_(n-2)) * 10 + ...

Creo que la búsqueda binaria es lo que estás buscando.

Answer 3

Si está utilizando shift-and-add para la multiplicación (que de ninguna manera es la manera más rápida) puede hacer la operación de módulo después de cada paso de adición. Si la suma es mayor que el módulo, resta el módulo. Si puede predecir el desbordamiento, puede hacer la suma y la resta al mismo tiempo. Hacer el módulo en cada paso también reducirá el tamaño total de su multiplicador (la misma longitud que la entrada en lugar del doble).

El desplazamiento del módulo que está haciendo le lleva la mayor parte del camino hacia un algoritmo de división completa (el módulo solo está tomando el resto).

EDITAR Aquí está mi aplicación en Python:

 
def mod_mul(a,b,m): 
    result = 0 
    a = a % m 
    b = b % m 
    while (b>0): 
     if (b&1)!=0: 
      result += a 
      if result >= m: result -= m 
     a = a << 1 
     if a>=m: a-= m 
     b = b>>1 
    return result 

Esto es sólo multiplicación modular (resultado = a * b mod m). Las operaciones de módulo en la parte superior no son necesarias, pero sirven para recordar que el algoritmo supone que a y b son menores que m.

Por supuesto para la exponenciación modular tendrá un bucle externo que realiza toda esta operación en cada paso haciendo cuadratura o multiplicación. Pero creo que tú lo sabías.

Answer 4

Esa prueba (modulus(n-1) != 1) // ¿una prueba de bit?

-parece redundante combinado con (modulus<result).

Diseñar para la aplicación de hardware yo estaría consciente de la menor/mayor que las pruebas que implican más lógica (resta) de operaciones bit a bit y se ramifican en cero.

Si podemos hacer pruebas a nivel de bits con facilidad, esto podría ser rápido:

m=msb_of(modulus) 

while(result>0) 
{ 
    r=msb_of(result) //countdown from prev msb onto result 
    shift=r-m  //countdown from r onto modulus or 
        //unroll the small subtraction 

    takeoff=(modulus<<(shift)) //or integrate this into count of shift 

    result=result-takeoff; //necessary subtraction 

    if(shift!=0 && result<0) 
    { result=result+(takeoff>>1); } 

    } //endwhile 

if(result==0) { return result } 
else   { return result+takeoff } 

(código no probado puede contener trampas)

result se decrementa repetively por modulus desplazada para que coincida con los bits más significativos al.

Después de cada resta: result Ocasión ~ 50/50 de perder más de 1 MSB. También tiene ~ 50/50 posibilidad de ir negativo, Además de la mitad de lo que se resta, siempre lo pondrá de nuevo en positivo. > Debe ser puesto de nuevo en positivo si cambio no era = bucle termina 0

El trabajo cuando se result empotramiento y 'desplazamiento' era 0.