Content deleted Content added
Category:Computational hardness assumptions |
→Background: missing 'of the' |
||
Line 11:
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>). 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" />
If the degree of the polynomial <math>\Phi(x)</math> is <math display="inline">n</math>, the sub-ring becomes the ring of polynomials of degree less than <math>n</math> modulo <math>\Phi(x)</math> with coefficients from <math>F_q</math>. The values <math display="inline">n</math>, <math display="inline">q</math>, together with the polynomial <math>\Phi(x)</math> partially define the mathematical context for the RLWE problem.
Another concept necessary for the RLWE problem is the idea of "small" polynomials with respect to some norm. The typical norm used in the RLWE problem is known as the infinity norm (also called the [[uniform norm]]). The infinity norm of a polynomial is simply the largest coefficient of the polynomial when these coefficients are viewed as integers. Hence, <math>||a(x)||_\infty = b</math> states that the infinity norm of the polynomial <math>a(x)</math> is <math>b</math>. Thus <math>b</math> is the largest coefficient of <math>a(x)</math>.
| |||