Eccellente e dettagliata l’esposizione fatta da Empty Head del metodo generale per trovare l’inverso di un polinomio modulo f(x) in un campo qualsiasi. Il metodo fornisce la soluzione nella totalità dei casi, anche se per polinomi di grado assai elevato, come ad esempio quelli usati in criptografia, può risultare di complessità computazionale immane. Nel caso si operi in campi a dimensione finita, ad esempio i campi di Galois, esistono degli algoritmi che agevolano di molto il calcolo. Prendiamo, a titolo di esempio, il GF 2^3, il quale è composto da polinomi di grado 3 in x i cui coefficienti appartengono alla classe degli interi modulo 2. Scegliendo come polinomio generatore…
g(x) = 1+x+x^3 (1)
… andiamo a calcolare le potenze distinte di x. Avremo…
x^0 =1
x^1= x
x^2=x^2
x^3=1+x
x^4=x+x^2
x^5=1+x+x^2
x^6=1+x^2
x^7=1 … (2)
E’ evidente che la successione delle potenze di x ha periodicità 7 ed è costituita dall’insieme dei polinomi del GF 2^3 diversi dal polinomio nullo. La sequenza illustrata dalla (2) può esser realizzata computazionalmente con lo schema rappresentato in figura, chiamato usualmente <i>linear feedback shift register</i>…
Se go, g1 e g2 sono i coefficienti di un generico polinomio memorizzati nella struttura, la moltiplicazione per x è effettuata semplicemente operando uno shift. Osservando la (2) si nota che ad ogni polinomio è possibile associare il suo ‘logaritmo’, vale a dire l’esponente da dare ad x per avere quel polinomio. L’impiego del logaritmo consente di semplificare di molto le operazioni di prodotto, divisione e calcolo dell’inverso. In particolare dato un polinomio di esponente k, il polinomio inverso avrà esponente pari al complemento a 7 di k. Se per esempio p(x)= 1+x [esponente k=3…] il suo inverso avrà esponente 7-3=4 e sarà quindi i(x)=x+x^2. L’enorme semplificazione e velocizzazione di calcolo rispetto al procedimento generale prima descritto è del tutto evidente…
cordiali saluti
lupo grigio