Ring learning with errors: Difference between revisions

Revision as of 18:52, 2 February 2016

Revision as of 18:54, 2 February 2016

Line 8:

The Ring Learning with Errors (RLWE) problem is built on the arithmetic of [[polynomials]] with coefficients from a [[finite field]].<ref name=":0" /> A typical polynomial <math display="inline">a(x)</math> is expressed as:

:<math>a(x) = a_0 + a_1x + a_2x^2 + ...\ldots + a_{n-2}x^{n-2} + a_{n-1}x^{n-1}</math>

Polynomials can be added and multiplied in the usual fashion. In the RLWE context the coefficients of the polynomials and all operations involving those coefficients will be done in a finite field, typically the field <math display="inline">\mathbf{Z}/q\mathbf{Z} = \mathbf{F}_q</math> for a prime integer <math display="inline">q</math>. The set of polynomials over a finite field with the operations of addition and multiplication forms an infinite [[polynomial ring]] (<math display="inline">\mathbf{F}_q[x]</math>).<ref>{{Cite journal|title = Polynomial ring|url = https://en.wikipedia.org/w/index.php?title=Polynomial_ring&oldid=661646453|date = 2015}}</ref> The RLWE context works with a finite sub-ring of this infinite ring. The sub-ring is typically the finite [[Quotient ring|quotient (factor) ring]] formed by reducing all of the polynomials in <math display="inline">\mathbf{F}_q[x]</math> modulo an [[irreducible polynomial]] <math display="inline">\Phi(x)</math>. This finite quotient ring can be written as <math>\mathbf{F}_q[x]/\Phi(x)</math> though many authors write <math>\mathbf{Z}_q[x]/\Phi(x)</math> .<ref name=":0" />