Editing NTRUEncrypt (section)

==Decryption==
Anybody knowing '''r''' could compute the message '''m''' by evaluating '''e''' - '''rh'''; so '''r''' must not be revealed by Alice. In addition to the publicly available information, Bob knows his own private key. Here is how he can obtain '''m''': 
First he multiplies the encrypted message '''e''' and part of his private key '''f'''
:<math> \textbf{a} = \textbf{f} \cdot \textbf{e} \pmod q </math>

By rewriting the polynomials, this equation is actually representing the following computation:

:<math> \textbf{a} = \textbf{f} \cdot \textbf{e} \pmod q </math>
:<math> \textbf{a} = \textbf{f} \cdot (\textbf{r} \cdot \textbf{h}+\textbf{m}) \pmod q </math>
:<math> \textbf{a} = \textbf{f} \cdot (\textbf{r} \cdot p\textbf{f}_q \cdot \textbf{g} + \textbf{m}) \pmod q </math>
:<math> \textbf{a} = p\textbf{r} \cdot \textbf{g} + \textbf{f} \cdot \textbf{m} \pmod q </math>

Instead of choosing the coefficients of '''a''' between 0 and ''q'' – 1 they are chosen in the interval [-''q''/2, ''q''/2] to prevent that the original message may not be properly recovered since Alice chooses the coordinates of her message '''m''' in the interval [-''p''/2, ''p''/2]. This implies that all coefficients of <math> \ p\textbf{r} \cdot \textbf{g} + \textbf{f} \cdot \textbf{m} </math> already lie within the interval [-''q''/2, ''q''/2] because the polynomials '''r''', '''g''', '''f''' and '''m''' and prime ''p'' all have coefficients that are small compared to ''q''. This means that all coefficients are left unchanged during reducing modulo ''q'' and that the original message may be recovered properly.

The next step will be to calculate '''a''' modulo ''p'':

:<math> \textbf{b} = \textbf{a} \pmod p = \textbf{f} \cdot \textbf{m} \pmod p </math>
because <math> \ p\textbf{r} \cdot \textbf{g} \pmod p =0 </math>.

Knowing '''b''' Bob can use the other part of his private key <math> \ \left(\textbf{f}_p \right)</math> to recover Alice's message by multiplication of '''b''' and <math> \ \textbf{f}_p </math>

:<math> \textbf{c} = \textbf{f}_p \cdot \textbf{b} = \textbf{f}_p \cdot \textbf{f} \cdot \textbf{m} \pmod p </math>
:<math> \textbf{c} = \textbf{m} \pmod p </math>

because the property <math> \ \textbf{f} \cdot \textbf{f}_p =1 \pmod p </math> was required for <math> \ \textbf{f}_p </math>.

'''Example''': 
The encrypted message '''e''' from Alice to Bob is multiplied with polynomial '''f'''
:<math>  \textbf{a} = \textbf{f} \cdot \textbf{e} \pmod {32} = 3 -7X-10X^2-11X^3+10X^4+7X^5+6X^6+7X^7+5X^8-3X^9-7X^{10} \pmod {32}, </math>
where Bob uses the interval [-''q''/2, ''q''/2] instead of the interval [0, ''q'' – 1]  for the coefficients of polynomial '''a''' to prevent that the original message may not be recovered correctly.

Reducing the coefficients of '''a''' mod ''p'' results in
:<math> \textbf{b} = \textbf{a} \pmod 3 = -X-X^2+X^3+X^4+X^5+X^7-X^8-X^{10} \pmod 3 </math>
which equals <math> \ \textbf{b} = \textbf{f} \cdot \textbf{m}\pmod 3 </math>.

In the last step the result is multiplied with <math> \ \textbf{f}_p </math> from Bob's private key to end up with the original message '''m'''
:<math> \textbf{c} = \textbf{f}_p \cdot \textbf{b} = \textbf{f}_p \cdot \textbf{f} \cdot \textbf{m} \pmod 3 = \textbf{m} \pmod 3 </math>
:<math> \textbf{c} = -1+X^3-X^4-X^8+X^9+X^{10} </math>
Which indeed is the original message Alice has sent to Bob!