Editing NTRUEncrypt (section)

==Public key generation==

Sending a secret message from Alice to Bob requires the generation of a public and a private key. The public key is known by both Alice and Bob and the private key is only known by Bob. To generate the key pair two polynomials '''f''' and '''g''', with degree at most <math> \  N-1 </math> and with coefficients in {-1,0,1} are required. They can be considered as representations of the residue classes of polynomials modulo <math> \ X^N-1 </math> in ''R''. The polynomial <math>  \textbf{f} \in L_f </math> must satisfy the additional requirement that the inverses modulo ''q'' and modulo ''p'' (computed using the [[Euclidean algorithm]]) exist, which means that 
<math> \ \textbf{f} \cdot \textbf{f}_p = 1 \pmod p </math> and <math> \ \textbf{f} \cdot \textbf{f}_q = 1 \pmod q </math> must hold.
So when the chosen '''f''' is not invertible, Bob has to go back and try another '''f'''.

Both '''f''' and <math> \ \mathbf{f}_p </math> (and <math> g </math>) are Bob's private key. The public key '''h''' is generated computing the quantity
:<math> \textbf{h} = p\textbf{f}_q \cdot \textbf{g} \pmod q. </math>

'''Example''':
In this example the parameters (''N'', ''p'', ''q'') will have the values ''N''  = 11, ''p'' = 3 and ''q'' = 32 and therefore the polynomials '''f''' and '''g''' are of degree at most 10. The system parameters (''N'', ''p'', ''q'') are known to everybody. The polynomials are randomly chosen, so suppose they are represented by

:<math> \textbf{f} = -1 + X + X^2 - X^4 + X^6 +X^9 - X^{10} </math>
:<math> \textbf{g} = -1 + X^2 +X^3 + X^5 -X^8 - X^{10} </math>

Using the Euclidean algorithm the inverse of '''f''' modulo ''p'' and modulo ''q'', respectively, is computed

:<math> \textbf{f}_p = 1 + 2X + 2X^3 +2X^4 + X^5 +2X^7 + X^8+2X^9 \pmod 3 </math>
:<math> \textbf{f}_q = 5 + 9X +6X^2+16X^3 + 4X^4 +15X^5 +16X^6+22X^7+20X^8+18X^9+30X^{10} \pmod {32} </math>

Which creates the public key '''h''' (known to both Alice and Bob) computing the product

:<math> \textbf{h} = p\textbf{f}_q \cdot \textbf{g} \pmod {32} = 8 - 7X - 10X^2 - 12X^3 + 12X^4 - 8X^5 + 15X^6 - 13X^7 + 12X^8 - 13X^9 + 16X^{10} \pmod {32} </math>