Come calcolare il modulo di grandi numeri?

Come calcolare il modulo del modulo 5 ^ 55 221 senza molto uso del calcolatore?

Immagino ci siano alcuni semplici principi nella teoria dei numeri nella crittografia per calcolare tali cose.

Ok, quindi vuoi calcolare a^b mod m . Per prima cosa adotteremo un approccio ingenuo e poi vedremo come possiamo perfezionarlo.

Innanzitutto, riduci a mod m . Ciò significa, trovare un numero a1 modo che 0 <= a1 < m a = a1 mod m . Quindi ripetutamente in un ciclo moltiplicare per a1 e ridurre nuovamente mod m . Quindi, in pseudocodice:

 a1 = a reduced mod m p = 1 for(int i = 1; i <= b; i++) { p *= a1 p = p reduced mod m } 

In questo modo evitiamo numeri più grandi di m^2 . Questa è la chiave. Il motivo per cui evitiamo numeri più grandi di m^2 è perché ad ogni passo 0 <= p < m e 0 <= a1 < m .

Ad esempio, calcoliamo 5^55 mod 221 . Innanzitutto, 5 è già ridotto mod 221 .

  1. 1 * 5 = 5 mod 221
  2. 5 * 5 = 25 mod 221
  3. 25 * 5 = 125 mod 221
  4. 125 * 5 = 183 mod 221
  5. 183 * 5 = 31 mod 221
  6. 31 * 5 = 155 mod 221
  7. 155 * 5 = 112 mod 221
  8. 112 * 5 = 118 mod 221
  9. 118 * 5 = 148 mod 221
  10. 148 * 5 = 77 mod 221
  11. 77 * 5 = 164 mod 221
  12. 164 * 5 = 157 mod 221
  13. 157 * 5 = 122 mod 221
  14. 122 * 5 = 168 mod 221
  15. 168 * 5 = 177 mod 221
  16. 177 * 5 = 1 mod 221
  17. 1 * 5 = 5 mod 221
  18. 5 * 5 = 25 mod 221
  19. 25 * 5 = 125 mod 221
  20. 125 * 5 = 183 mod 221
  21. 183 * 5 = 31 mod 221
  22. 31 * 5 = 155 mod 221
  23. 155 * 5 = 112 mod 221
  24. 112 * 5 = 118 mod 221
  25. 118 * 5 = 148 mod 221
  26. 148 * 5 = 77 mod 221
  27. 77 * 5 = 164 mod 221
  28. 164 * 5 = 157 mod 221
  29. 157 * 5 = 122 mod 221
  30. 122 * 5 = 168 mod 221
  31. 168 * 5 = 177 mod 221
  32. 177 * 5 = 1 mod 221
  33. 1 * 5 = 5 mod 221
  34. 5 * 5 = 25 mod 221
  35. 25 * 5 = 125 mod 221
  36. 125 * 5 = 183 mod 221
  37. 183 * 5 = 31 mod 221
  38. 31 * 5 = 155 mod 221
  39. 155 * 5 = 112 mod 221
  40. 112 * 5 = 118 mod 221
  41. 118 * 5 = 148 mod 221
  42. 148 * 5 = 77 mod 221
  43. 77 * 5 = 164 mod 221
  44. 164 * 5 = 157 mod 221
  45. 157 * 5 = 122 mod 221
  46. 122 * 5 = 168 mod 221
  47. 168 * 5 = 177 mod 221
  48. 177 * 5 = 1 mod 221
  49. 1 * 5 = 5 mod 221
  50. 5 * 5 = 25 mod 221
  51. 25 * 5 = 125 mod 221
  52. 125 * 5 = 183 mod 221
  53. 183 * 5 = 31 mod 221
  54. 31 * 5 = 155 mod 221
  55. 155 * 5 = 112 mod 221

Pertanto, 5^55 = 112 mod 221 .

Ora, possiamo migliorare questo usando l' esponenziazione quadrando ; questo è il famoso trucco in cui riduciamo l'esponenziazione a richiedere solo moltiplicazioni log b invece di b . Si noti che con l'algoritmo che ho descritto sopra, l'elevazione a potenza con il miglioramento della squadratura, si finisce con il metodo binario da destra a sinistra .

 a1 = a reduced mod m p = 1 while (b > 0) { if (b is odd) { p *= a1 p = p reduced mod m } b /= 2 a1 = (a1 * a1) reduced mod m } 

Quindi, dal 55 = 110111 in binario

  1. 1 * (5^1 mod 221) = 5 mod 221
  2. 5 * (5^2 mod 221) = 125 mod 221
  3. 125 * (5^4 mod 221) = 112 mod 221
  4. 112 * (5^16 mod 221) = 112 mod 221
  5. 112 * (5^32 mod 221) = 112 mod 221

Quindi la risposta è 5^55 = 112 mod 221 . Il motivo per cui funziona è perché

 55 = 1 + 2 + 4 + 16 + 32 

così che

 5^55 = 5^(1 + 2 + 4 + 16 + 32) mod 221 = 5^1 * 5^2 * 5^4 * 5^16 * 5^32 mod 221 = 5 * 25 * 183 * 1 * 1 mod 221 = 22875 mod 221 = 112 mod 221 

Nel passo in cui calcoliamo 5^1 mod 221 , 5^2 mod 221 , ecc. Notiamo che 5^(2^k) = 5^(2^(k-1)) * 5^(2^(k-1)) perché 2^k = 2^(k-1) + 2^(k-1) modo che possiamo prima calcolare 5^1 e ridurre mod 221 , quindi quadrato questo e ridurre mod 221 per ottenere 5^2 mod 221 , ecc.

L'algoritmo di cui sopra formalizza questa idea.

Per aggiungere alla risposta di Jason:

Puoi accelerare il processo (che potrebbe essere utile per esponenti molto grandi) usando l’espansione binaria dell’esponente. Per prima cosa calcola 5, 5 ^ 2, 5 ^ 4, 5 ^ 8 mod 221 – fai questo ripetendo la quadratura:

  5^1 = 5(mod 221) 5^2 = 5^2 (mod 221) = 25(mod 221) 5^4 = (5^2)^2 = 25^2(mod 221) = 625 (mod 221) = 183(mod221) 5^8 = (5^4)^2 = 183^2(mod 221) = 33489 (mod 221) = 118(mod 221) 5^16 = (5^8)^2 = 118^2(mod 221) = 13924 (mod 221) = 1(mod 221) 5^32 = (5^16)^2 = 1^2(mod 221) = 1(mod 221) 

Ora possiamo scrivere

 55 = 1 + 2 + 4 + 16 + 32 so 5^55 = 5^1 * 5^2 * 5^4 * 5^16 * 5^32 = 5 * 25 * 625 * 1 * 1 (mod 221) = 125 * 625 (mod 221) = 125 * 183 (mod 183) - because 625 = 183 (mod 221) = 22875 ( mod 221) = 112 (mod 221) 

Puoi vedere come per esponenti molto grandi questo sarà molto più veloce (credo che sia log piuttosto che lineare in b, ma non certo).

 /* The algorithm is from the book "Discrete Mathematics and Its Applications 5th Edition" by Kenneth H. Rosen. (base^exp)%mod */ int modular(int base, unsigned int exp, unsigned int mod) { int x = 1; int power = base % mod; for (int i = 0; i < sizeof(int) * 8; i++) { int least_sig_bit = 0x00000001 & (exp >> i); if (least_sig_bit) x = (x * power) % mod; power = (power * power) % mod; } return x; } 
 5^55 mod221 = ( 5^10 * 5^10 * 5^10 * 5^10 * 5^10 * 5^5) mod221 = ( ( 5^10) mod221 * 5^10 * 5^10 * 5^10 * 5^10 * 5^5) mod221 = ( 77 * 5^10 * 5^10 * 5^10 * 5^10 * 5^5) mod221 = ( ( 77 * 5^10) mod221 * 5^10 * 5^10 * 5^10 * 5^5) mod221 = ( 183 * 5^10 * 5^10 * 5^10 * 5^5) mod221 = ( ( 183 * 5^10) mod221 * 5^10 * 5^10 * 5^5) mod221 = ( 168 * 5^10 * 5^10 * 5^5) mod221 = ( ( 168 * 5^10) mod 221 * 5^10 * 5^5) mod221 = ( 118 * 5^10 * 5^5) mod221 = ( ( 118 * 5^10) mod 221 * 5^5) mod221 = ( 25 * 5^5) mod221 = 112 

Quello che stai cercando è l’esponenziazione modulare, in particolare l’esponenziazione binaria modulare. Questo link wikipedia ha uno pseudocodice.

Il teorema del resto cinese mi viene in mente come un punto iniziale come 221 = 13 * 17. Quindi, suddividilo in 2 parti che vengono combinate alla fine, una per il mod 13 e una per il mod 17. In secondo luogo, credo ci sia qualche prova di a ^ (p-1) = 1 mod p per tutti i non zero a che aiuta anche a ridurre il tuo problema in quanto 5 ^ 55 diventa 5 ^ 3 per il caso 13 mod come 13 * 4 = 52. Se guardi sotto il tema “Campi finiti” potresti trovare dei buoni risultati su come risolvere questo problema.

EDIT: Il motivo per cui ho menzionato i fattori è che questo crea un modo per calcolare zero in elementi diversi da zero come se si provasse qualcosa come 13 ^ 2 * 17 ^ 4 mod 221, la risposta è zero dal 13 * 17 = 221. Un sacco di grandi numeri non saranno primi, anche se ci sono modi per trovare i numeri primi grandi in quanto vengono utilizzati molto nella crittografia e in altre aree della Matematica.

Questo fa parte del codice che ho fatto per la convalida IBAN. Sentiti libero di usare.

  static void Main(string[] args) { int modulo = 97; string input = Reverse("100020778788920323232343433"); int result = 0; int lastRowValue = 1; for (int i = 0; i < input.Length; i++) { // Calculating the modulus of a large number Wikipedia http://en.wikipedia.org/wiki/International_Bank_Account_Number if (i > 0) { lastRowValue = ModuloByDigits(lastRowValue, modulo); } result += lastRowValue * int.Parse(input[i].ToString()); } result = result % modulo; Console.WriteLine(string.Format("Result: {0}", result)); } public static int ModuloByDigits(int previousValue, int modulo) { // Calculating the modulus of a large number Wikipedia http://en.wikipedia.org/wiki/International_Bank_Account_Number return ((previousValue * 10) % modulo); } public static string Reverse(string input) { char[] arr = input.ToCharArray(); Array.Reverse(arr); return new string(arr); } 

La risposta di Jason in Java (nota i < exp ).

 private static void testModulus() { int bse = 5, exp = 55, mod = 221; int a1 = bse % mod; int p = 1; System.out.println("1. " + (p % mod) + " * " + bse + " = " + (p % mod) * bse + " mod " + mod); for (int i = 1; i < exp; i++) { p *= a1; System.out.println((i + 1) + ". " + (p % mod) + " * " + bse + " = " + ((p % mod) * bse) % mod + " mod " + mod); p = (p % mod); } } 

Questo è chiamato esponenziazione modulare ( https://en.wikipedia.org/wiki/Modular_exponentiation ).

Supponiamo che tu abbia la seguente espressione:

 19 ^ 3 mod 7 

Invece di alimentare direttamente 19 puoi fare quanto segue:

 (((19 mod 7) * 19) mod 7) * 19) mod 7 

Ma questo può richiedere anche molto tempo a causa di molti multipli sequenziali e quindi puoi moltiplicare sui valori al quadrato:

 x mod N -> x ^ 2 mod N -> x ^ 4 mod -> ... x ^ 2 |log y| mod N 

L’algoritmo di esponenziazione modulare fa supposizioni che:

 x ^ y == (x ^ |y/2|) ^ 2 if y is even x ^ y == x * ((x ^ |y/2|) ^ 2) if y is odd 

E così l’algoritmo di esponenziazione modulare ricorsivo sarà simile a questo in java:

 /** * Modular exponentiation algorithm * @param x Assumption: x >= 0 * @param y Assumption: y >= 0 * @param N Assumption: N > 0 * @return x ^ y mod N */ public static long modExp(long x, long y, long N) { if(y == 0) return 1 % N; long z = modExp(x, Math.abs(y/2), N); if(y % 2 == 0) return (long) ((Math.pow(z, 2)) % N); return (long) ((x * Math.pow(z, 2)) % N); } 

Un ringraziamento speciale a @chux per l’errore trovato con il valore restituito errato in caso di confronto y e 0.

Fornisci un’altra implementazione della risposta di Jason di C.

Dopo aver discusso con i miei compagni di class, sulla base della spiegazione di Jason, mi piace la versione ricorsiva di più se non ti interessa molto la performance:

Per esempio:

 #include int mypow( int base, int pow, int mod ){ if( pow == 0 ) return 1; if( pow % 2 == 0 ){ int tmp = mypow( base, pow >> 1, mod ); return tmp * tmp % mod; } else{ return base * mypow( base, pow - 1, mod ) % mod; } } int main(){ printf("%d", mypow(5,55,221)); return 0; }