Moltiplicazione di due polinomi

Question

Questa è una domanda posta in alcune domande dell'intervista.

Dati tre polinomi f (x), g (x), h (x) in cui il coefficiente di costo è binario. Dare [f (x) * g (x)] mod h (x) [Tutte le operazioni in coefficiente binario]

I polinomi sono indicati in questo formato ... x3 + x + 1 è indicato come "1011". Scrivi un programma char * multmod (char * f, char * g, char * h) che emetterà polinomio ... (f * g) mod h

Quale potrebbe essere l'approccio? possiamo fare qualcosa a livello di bit?

Answer 1

Questa è una domanda di conoscenza. Fondamentalmente, a meno che tu non sia intelligente come Gauss o conosci già la matematica della congruenza, nota anche come "aritmetica modulare", sei fregato. Un libro che potresti voler leggere per conoscere questa roba è "Introduzione alla teoria dei numeri con l'informatica" di Allenby.

In definitiva, la conoscenza chiave è che la congruenza può essere calcolata con diversi metodi, il migliore dei quali è il metodo "quadrato e moltiplica" che è piuttosto antico. Fondamentalmente, ogni volta che si ha un binario 1, si è entrambi quadrati e multipli, ma quando si ha uno 0, si piazza semplicemente. L'algoritmo completo e la spiegazione sono a p. 79 di Allenby.

Un altro approccio userebbe il termine residuo cinese, che è probabilmente l'obiettivo del questionario.

Dove stai facendo domanda? La NSA? Los Alamos? Questa è una domanda piuttosto difficile.

---

Grande, a bassa quota per essere l'unica persona che ha effettivamente risposto alla domanda. Giusto per essere chiari qui: indubbiamente l'intervistatore si aspettava lo sfruttamento dell'algoritmo quadrato e multiplo, come ho detto sopra. Quadrato e multiplo viene utilizzato all'interno di algoritmi RSA/crittografia per eseguire operazioni rapide modulo. Vedi p. 225 per una descrizione di questo algoritmo e dell'applicazione RSA: Implementation of Multinomial Standard Product for RSA State. L'intervistatore probabilmente ha lavorato su RSA ed è per questo che sapeva del metodo.

Answer 2

Quello che stai facendo essenzialmente è operazioni binarie. Puoi vedere come la tua CPU implementa tali operazioni.

http://en.wikipedia.org/wiki/Multiplication_algorithm http://en.wikipedia.org/wiki/Modulo_operation

Answer 3

Questo appare come un semplice moltiplicazione polinomiale e lungo problema di divisione. Basta moltiplicare i polinomi e quindi dividerli. Moltiplicazione è abbastanza semplice con due cicli for innestati, per la divisione lungo veda:

http://www.sosmath.com/algebra/factor/fac01/fac01.html

http://en.wikipedia.org/wiki/Polynomial_long_division

Answer 4

motivazione

coefficienti binari qui significa che i coefficienti sono modulo 2, nel campo Z_2, o semplicemente assumere i valori 0 e 1 e operare come bit. Non significa che i coefficienti sono interi arbitrari rappresentati nella seconda base. Essi sono binari (assumono esattamente due valori), anziché essere semplicemente espressi in un sistema di numeri binari.

Con questa idea ben precisa, questa domanda è abbastanza facile da rispondere, e sì, le operazioni bit a bit di XOR e di spostamenti a sinistra saranno sufficienti. Sebbene non sia richiesto di rispondere a questa domanda, questa domanda è motivata dalla crittografia. Dimostra il collegamento tra alcune operazioni bit a bit comunemente utilizzate nell'hash e alcuni schemi di crittografia e algebra astratta, in modo che i risultati sui polinomi su campi finiti possano essere sfruttati nella crittanalisi. Prendendo il modulo del modulo un altro polinomio serve a impedire che il livello del risultato cresca oltre un certo limite. Le operazioni sui registri macchina lo fanno naturalmente come trabocco.

aggiunta

Prima parliamo di aggiunta. Poiché i coefficienti sono modulo 2, aggiungere x + x = 2x = 0x = 0 dal 2 mod 2 = 0. Quindi, ogni volta che c'è lo stesso termine, si annulla e, quando ce n'è uno solo, persiste. Questo è lo stesso comportamento di XOR. Ad esempio, l'aggiunta (x^4 + x^2 + 1) + (x^3 + x^2):

(1x^4+0x^3+1x^2+0x^1+1x^0)+(0x^4+1x^3+1x^2+0x^1+0x^0) = (1x^4+1x^3+0x^2+0x^1+1x^0) 

o, utilizzando il coefficiente compatto unico notazione,

10101 XOR 01100 = 11001 

Moltiplicazione

Moltiplicazione per x aumenta la potenza di ogni termine per uno. Nella notazione compatta, ciò equivale allo spostamento bit a sinistra sinistro.

(1x^4+0x^3+1x^2+0x^1+1x^0) * x = (1x^5+0x^4+1x^3+0x^2+1x^1+0x^0) 
10101 << 1 = 101010 

Così, per moltiplicare polinomi f(x) * g(x) possiamo moltiplicare f(x) da ogni termine di g(x) separatamente, ciascuno equivalente a un cambiamento, e quindi aggiungere, l'aggiunta equivalente a XOR. Moltiplichiamo (x^4 + x^2 + 1) * (x^3 + x^2)

(x^4 + x^2 + 1) * (x^3 + x^2) = (x^4 + x^2 + 1)*x^3 + (x^4 + x^2 + 1) *x^2 
(10101 << 3) XOR (10101 << 2) = 10101000 XOR 01010100 = 11111100 

Quindi, la risposta è x^7 + x^6 + x^5 + x^4 + x^3 + x^2.

Modulo Riduzione

Riduzione modulo h(x) è anche abbastanza facile. Certamente lo non richiede di ricordare come eseguire una divisione lunga. Come la moltiplicazione, lo faremo per termini. Continuiamo con lo stesso esempio, e portarlo MODULO h(x) = x^5 + x

(x^7 + ... + x^2) mod (x^5+x) = [x^7 mod (x^5+x)] + ... + [x^2 mod (x^5+x)] 

Ora, se il grado, n, di x^n è più piccolo di quello di h(x), qui 5, allora non c'è niente da fare perché h(x) vinto' t dividere x^n.

[x^2 mod (x^5+x)] = x^2 or 00000100 
[x^3 mod (x^5+x)] = x^3 or 00001000 
[x^4 mod (x^5+x)] = x^4 or 00010000 

Quando poi gradi sono uguali, possiamo dire h(x) divide x^n una volta, e abbiamo oltrepassato dai restanti termini di h(x). Che abbiamo superato invece di underhot difficilmente importa, né fa il segno sul resto dal -1 mod 2 = 1. Qui,

x^5 = (x^5 + x) – x, so 
[x^5 mod (x^5+x)] = x, or 00000010 

In generale, [x^n mod h (x)] = [h (x) -x^n] quando n = degree(h).In forma compatta, questo equivale a spegnere il n esimo bit, che può essere fatto da XOR-zione la rappresentazione della h(x) con la rappresentazione di x^n:

00100010 XOR 00100000 = 00000010. 

Quando x^n ha un grado maggiore di h(x) possiamo moltiplicare h(x) per x^k per far coincidere i gradi e procedere come nel caso precedente.

x^6 = (x^5 + x) * x - (x) * x = -x^2, quindi [x^6 mod (x^5 + x)] = x^2, o 00000100, o in forma compatta (00100010 < < 1) XOR (00100000 < < 1) = 00000100

Ma, in modo più efficiente, basta spostare la risposta precedente, che faremo per x^7:

[x^7 mod (x^5+x)] = x^3, or 00001000 

Quindi per raccogliere, abbiamo bisogno di aggiungere questi risultati, che è XOR-ing nella rappresentazione compatta.

x^2 + x^3 + x^4 + x + x^2 + x^3 = x^4 + 2x^3 + 2x^2 + x = x^4 + x, or 
00000100 XOR 00001000 XOR 00010000 XOR 00000010 XOR 00000100 XOR 00001000 = 00010010 

Osservazioni conclusive

Possiamo chiedere Wolfram Alpha per verificare questo risultato per noi da una lunga divisione. Il resto indicato è x^4 - x, che equivale a x^4 + x quando i coefficienti sono modulo 2.

Le fasi di moltiplicazione e di modulo a termine possono essere combinate, ad es. moltiplicare per x e modulo il prodotto, per un algoritmo più efficiente, che sarà uno spostamento e XOR se il grado del prodotto è almeno quello di h(x). Quindi ripetere sul risultato, moltiplicare per x e modulo il prodotto, e registrare quella risposta per la moltiplicazione per x^2. E così via ...