There’s one library in Python that probably makes Python the language of choice, and one of the reasons it is so popular: NumPy. If you deal with numbers, the mighty Numpy library is there to help you.
In a lattice-based cryptography world, we represent our data values in terms of polynomials. So let’s look at polynomials and the mod operator. 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 npA=[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 (mod 13):
A+B (mod 13)=22x²+9x+4 (mod 13)=9x²+9x+4
Now let’s look at multiplication, for this we have:
A×B=(10x²+6x+2)×(12x²+3x+2)=120x⁴+30x³+20x²+72x³+180x²+12x+24x²+6x+4
A×B=120x⁴+102x³+62x²+18x+4
And now (mod 13):
A×B (mod 13)=120x⁴+102x³+62x²+18x+4(mod13)=3x⁴+11x³+10x²+5x+4
Next we will perform a polynomial subtraction:
A−B=(10x²+6x+2)−(12x²+3x+2)=−2x²+3x
And now (mod13):
A−B (mod 13)=−2x²+3x=11x²+3x
Next we will perform a polynomial division:
A÷B=(10x²+6x+2)÷(12x²+3x+2)=3x
And now (mod 13):
A÷B (mod 13)=3x
The code for this is [here]:
import numpy as np
import numpy as np
import sys
import numpy
q=13
n=3
A=[5,4,1,11,10]
B=[3,5,2,4]
if (len(sys.argv)>1):
A=list(eval(sys.argv[1]))
if (len(sys.argv)>2):
B=list(eval(sys.argv[2]))
print (“A:”)
print(np.poly1d(A))
print (“B:”)
print(np.poly1d(B))
print (“nn====== A+B =====”)
res=np.polyadd(A,B)
print(np.poly1d(res))
res=np.polyadd(A,B)%q
print (“nA+B (mod”,q,”):”)
print(np.poly1d(res))
print (“nn====== A*B =====”)
res=np.polymul(A,B)
print(np.poly1d(res))
res=np.polymul(A,B)%q
print (“nnA*B (mod”,q,”):”)
print(np.poly1d(res))
print (“nn====== A-B =====”)
res=np.polysub(A,B)
print(np.poly1d(res))
res=np.polysub(A,B)%q
print (“nnA-B (mod”,q,”):”)
print(np.poly1d(res))
print (“nnA/B =====”)
res=np.floor(np.polydiv(A,B)[1])
print(np.poly1d(res))
res=np.floor(np.polydiv(A,B)[1])%q
print (“nnA/B (mod”,q,”):”)
print(np.poly1d(res))
A sample run is [here]:
A:
2
10 x + 6 x + 2
B:
2
12 x + 3 x + 2
====== A+B =====
2
22 x + 9 x + 4
A+B (mod 13 ):
2
9 x + 9 x + 4
====== A*B =====
4 3 2
120 x + 102 x + 62 x + 18 x + 4
A*B
Read more