Come trovare un valore variabile nell'espressione MOD?

Question

9 = 2 ^ X mod 11

Che cos'è X e come si trova X?

È legato alla ricerca del testo semplice nell'algoritmo RSA e sto scrivendo un programma C per esso.

Answer 1

La risposta è 6 + 10i per qualsiasi numero intero i.

Un modo semplice per ottenere soluzioni per piccoli moduli è iterare su tutti i valori di x. Devi solo controllare tra 0 e 10 (= 11 - 1) per trovare la prima soluzione, se esiste una soluzione.

x = 0
while x < 50:
    if 9 == 2**x % 11:
         print x
    x += 1

Output:

6
16
26
36
46

Ovviamente ciò richiederà molto tempo se il modulo è grande.

Ulteriori informazioni sono disponibili nella pagina Logarithm discreto . Nota:

  

Nessun algoritmo classico efficiente per   calcolo logaritmi discreti generali   logbg è noto. L'algoritmo ingenuo è   per elevare b a poteri sempre più alti   k fino a trovare la g desiderata; Questo   a volte viene chiamato processo   moltiplicazione. Questo algoritmo   richiede un tempo di esecuzione lineare in   dimensione del gruppo G e quindi   esponenziale nel numero di cifre in   la dimensione del gruppo.

Se fosse facile invertire l'esponiazione modulare, non sarebbe una buona primitiva crittografica.

Answer 2

Ovviamente, la sequenza di 2 ^ n mod 11 sarà ciclica.

2 ^ 0 mod 11 = 1
2 ^ 1 mod 11 = 2
2 ^ 2 mod 11 = 4
2 ^ 3 mod 11 = 8
2 ^ 4 mod 11 = 5
2 ^ 5 mod 11 = 10
2 ^ 6 mod 11 = 9
2 ^ 7 mod 11 = 7
2 ^ 8 mod 11 = 3
2 ^ 9 mod 11 = 6
2 ^ 10 mod 11 = 1
2 ^ 11 mod 11 = 2

Quindi, la durata del ciclo è 10.

2 ^ n mod 11 = 9 per n = 6 + 10 * m dove m è intero

Answer 3

Penso che possa essere risolto usando aritmetica modulare . Un altro modo è calcolare 9 = 2 ^ X in F ₁₁ (Z / 11Z), ma anche questo fa parte dell'aritmetica modulare.

Un'altra soluzione (dove troverai solo UNA soluzione) è quella di risolvere numericamente l'equazione, probabilmente è più facile in un programma C.