Modulo di potere dei grandi numeri

Sto cercando di implementare il più SICURO+ algoritmo. L’algoritmo richiede trovare il modulo di una funzione di alimentazione come segue:

pow(45, x) mod 257

La variabile x è un byte, e quindi può variare da 0 a 255. Di conseguenza, il risultato della funzione di potenza può essere MOLTO grande con conseguente errata valori che, se attuate utilizzando 32 – o 64-bit interi.

Come posso eseguire questo calcolo?

  • che linguaggio di programmazione?
  • Se non sono completamente sbagliate e ricordo bene che non ci sono particolari formule per il calcolo di potenze nel modulo di spazi, il modulo di calcolo è la parte importante della domanda, quindi la domanda è indipendente dalla lingua.
  • Introduttivo di lettura: Il gruppo moltiplicativo dei numeri interi. Questo è troppo lungo fa per me rispondere, ma forse qualcuno la ricorda.
  • C’è un modo più SICURO+ di attuazione scritto in C, che si può studiare qui: schneier.com/book-applied-source.html
InformationsquelleAutor Eng. Aws | 2011-11-27



4 Replies
  1. 21

    alcuni pseudo codice

    function powermod(base, exponent, modulus) {
        if (base < 1 || exponent < 0 || modulus < 1)
            return -1
    
        result = 1;
        while (exponent > 0) {
           if ((exponent % 2) == 1) {
               result = (result * base) % modulus;
           }
           base = (base * base) % modulus;
           exponent = floor(exponent /2);
        }
        return result;
    }
    

    e chiamare

    powermod(45, x, 257)    
    
  2. 13

    Eseguire l’elevamento a potenza da ripetuti quadratura, riducendo il modulo dopo ogni operazione. Questa è una tecnica standard.

    Un esempio pratico: 45^13 mod 257:

    1. Primo calcolare 45^2, 45^4, 45^8 mod 257:

      45^2 mod 257 = 2025 mod 257 = 226

      45^4 mod 257 = 226^2 mod 257 = 51076 mod 257 = 190

      45^8 mod 257 = 190^2 mod 257 = 36100 mod 257 = 120

    2. Quindi utilizzare l’espansione binaria di 13 a combinare questi per ottenere il risultato:

      45^13 mod 257 = 45^1 * 45^4 * 45^8 mod 257

      45^13 mod 257 = 45 * 190 * 120 mod 257

      45^13 mod 257 = 8550 * 120 mod 257

      45^13 mod 257 = 69 * 120 mod 257

      45^13 mod 257 = 8280 mod 257

      45^13 mod 257 = 56

    Nota che i risultati intermedi del calcolo sono mai più di 257*257, quindi questo può essere facilmente eseguita in un numero intero a 32 bit tipo.

    • risposta più bella..
  3. 3

    Considerare il semplice identità:

    mod(A^2,p) = mod(A,p)*mod(A,p)
    

    Anche notare che

    A^4 = (A^2)^2
    

    Altri poteri sono banalmente calcolato se si conosce la rappresentazione binaria di finale esponente che si desidera calcolare.

Lascia un commento