Modi migliori per implementare un'operazione modulo (domanda algoritmo)

Question

Ho cercato di implementare un esponenziale di recente modulare. Sto scrivendo il codice in VHDL, ma sto cercando consigli di natura più algoritmica. Il componente principale del exponentiator modulare è un moltiplicatore modulare che devo anche implementare. Non ho avuto problemi con l'algoritmo di moltiplicazione - è solo l'aggiunta e lo spostamento e ho fatto un buon lavoro di capire cosa significano tutte le mie variabili in modo da poter moltiplicare in un tempo abbastanza ragionevole.

Il problema che sto avendo è con l'implementazione dell'operazione modulo nel moltiplicatore. So che eseguire sottrazioni ripetute funzionerà, ma sarà anche lento. Ho scoperto che potevo spostare il modulo per sottrarre efficacemente i grandi multipli del modulo, ma penso che potrebbero esserci ancora modi migliori per farlo. L'algoritmo che sto usando opere qualcosa di simile (pseudocodice strano segue):

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

Quindi ... è questo un buon algoritmo, o almeno un buon punto di partenza? Wikipedia non discute veramente gli algoritmi per implementare l'operazione modulo, e ogni volta che cerco di cercare altrove trovo documenti di ricerca davvero interessanti ma incredibilmente complicati (e spesso non correlati). Se c'è un modo ovvio per implementare ciò che non vedo, apprezzerei davvero qualche feedback.

Answer 1

Per modulo in sé, non sono sicuro. Per modulo come parte della più ampia operazione esponenziale modulare, hai cercato Montgomery multiplication come menzionato nella pagina di wikipedia su modular exponentiation? È passato un po 'di tempo da quando ho esaminato questo tipo di algoritmo, ma da quello che ricordo, è comunemente usato nell'esponenziazione modulare veloce.

modifica: per quello che vale, il tuo algoritmo modulo sembra ok a prima vista. In pratica stai facendo una divisione che è un algoritmo di sottrazione ripetuto.

Answer 2

Non sono sicuro di cosa si sta calcolando lì per essere onesti. Si parla di funzionamento modulo, ma in genere un'operazione di modulo è tra due numeri a e b e il suo risultato è il resto della divisione a per b. Dove sono lo a e lo nel tuo pseudocodice ...?

In ogni caso, forse questo aiuterà: a mod b = a - floor(a/b) * b.

Non so se questo è più veloce o meno, dipende dal fatto che si possa fare o meno divisione e moltiplicazione più velocemente di molte sottrazioni.

Un altro modo per accelerare l'approccio di sottrazione consiste nell'utilizzare la ricerca binaria. Se si desidera a mod b, è necessario sottrarre b da a fino a a è inferiore a b. Quindi, in pratica è necessario trovare k tale che:

a - k*b < b, k is min

Un modo per trovare questo k è una ricerca lineare:

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

return a - k*b; 

Ma si può anche ricerca binaria è (correva solo alcuni test ma ha funzionato su tutti):

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; 

Sto immaginando che la soluzione di ricerca binaria sarà la più veloce quando si tratta con grandi numeri.

Se si desidera calcolare a mod b e solo a è un numero grande (è possibile memorizzare b su un tipo di dati di base), si può fare ancora più veloce:

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

Questo funziona perché possiamo scrivere a come 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 + ...

Penso che la ricerca binaria sia ciò che stai cercando.

Answer 3

Se si utilizza lo spostamento e l'aggiunta per la moltiplicazione (che non è affatto il modo più veloce) è possibile eseguire l'operazione modulo dopo ogni passaggio di aggiunta. Se la somma è maggiore del modulo, sottrai il modulo. Se è possibile prevedere l'overflow, è possibile eseguire l'addizione e la sottrazione allo stesso tempo. Fare il modulo in ogni fase ridurrà anche la dimensione complessiva del moltiplicatore (stessa lunghezza dell'input anziché del doppio).

Lo spostamento del modulo che stai facendo è quello di ottenere il massimo verso un algoritmo di divisione completa (modulo sta solo prendendo il resto).

EDIT Qui è la mia applicazione in 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 

Questa è solo la moltiplicazione modulare (risultato = a * b mod m). Le operazioni modulo in alto non sono necessarie, ma servono a ricordare che l'algoritmo presuppone che a e b siano inferiori a m.

Ovviamente per l'esponenziazione modulare avrete un ciclo esterno che esegue l'intera operazione in ogni fase eseguendo quadratura o moltiplicazione. Ma penso che tu lo sapessi.

Answer 4

Quel test (modulus(n-1) != 1) // un po 'di test?

-sembra ridondante combinato con (modulus<result).

Progettando per l'implementazione hardware, sarei consapevole del più piccolo/maggiore rispetto ai test che implicano più logica (sottrazione) rispetto alle operazioni bit a bit e ramificazione su zero.

Se siamo in grado di fare test bit per bit con facilità, questo potrebbe essere rapida:

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 } 

(codice non testato può contenere trucchi)

result è repetively decrementato di modulus spostato in modo che corrisponda al bit più significativi.

Dopo ogni sottrazione: result ha una ~ 50/50 possibilità di perdere più di 1 msb. Inoltre ha ~ 50/50 possibilità di andare in negativo, l'aggiunta della metà di ciò che è stato sottratto lo rimetterà sempre in positivo. > Dovrebbe essere rimesso in positivo se spostamento non fosse = 0

Il lavoro ciclo termina quando viene result underrun e 'shift' era di 0