The security of modern cryptography, in particular [[Public-key cryptography|Public Key Cryptography]], is based on the difficultyassumed intractability of solving certain computational problems believed to be intractable if the size of the problem is large enough and the instance of the problem to be solved is chosen randomly.<ref>{{Cite journal|title = Public-key cryptography|url = https://en.wikipedia.org/w/index.php?title=Public-key_cryptography&oldid=670016308|date = 2015}}</ref> The classic example that has been used since the 1970s is the [[integer factorization]] problem.<ref>{{Cite journal|title = RSA (cryptosystem)|url = https://en.wikipedia.org/w/index.php?title=RSA_(cryptosystem)&oldid=669826149|date = 2015}}</ref> It is believed that it is computationally intractable to factor the product of two prime numbers if those prime numbers are large enough and chosen at random. As of 2015 research has led to the factorization of the product of two 384-bit primes but not the product of two 512-bit primes. Integer factorization forms the basis of the widely used [[RSA (cryptosystem)|RSA]] cryptographic algorithm.<ref>{{Cite journal|title = Integer factorization records|url = https://en.wikipedia.org/w/index.php?title=Integer_factorization_records&oldid=669003206|date = 2015}}</ref>
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 a(x) is expressed as:
