Polynomials, Mod p, and Numpy

There’s one library in Python that probably makes Python the language of choice, and the reason it is so popular: NumPy. If you deal with numbers, the mighty Numpy library is there to help you. So let’s look at polynomials and the mod operator, and which are used in lattice cryptography.

In with polynomials, for an order of five, we have the form:

ax⁵+bx⁴+cx³+dx²+ex+f

We can then represent this as an integer array of:

[a,b,c,d,e,f]

In Python, the polynomial of 5x⁴+4x³+x²+11x+10 is implemented and printed as:

import numpy as np
A=[5,4,1,11,10]
print ("A:")
print(np.poly1d(A))

This gives:

A:
   4     3     2
5 x + 4 x + 1 x + 11 x + 10

Let’s take an example of:

A=10x²+6x+2

B=12x²+3x+2

If we add these we get:

A+B=10x²+6x+2+12x²+3x+2=22x²+9x+4

Now we can perform a (mod) operation on this, such as with (mod13):

A+B(mod 13)=22x²2+9x+4 (mod 13)=9x²+9x+4

Now let’s look at multiplication, for this we have: