Polynomials, Mod p, and Numpy

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:

A×B=(10x²+6x+2)×(12x²2+3x+2)=120x⁴4+30x³3+20x²+72x³+180x²2+12x+24x²+6x+4

A×B=120x⁴+102x³+62x²+18x+4

And now (mod13):

A×B(mod13)=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(mod13)=−2x²+3x=11x²+3x

Next we will perform a polynomial division:

A÷B=(10x²+6x+2)÷(12x²+3x+2)=3x

And now (mod13):

A÷B(mod13)=3x

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 ("\n\n====== 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 ("\n\n====== A*B =====")
res=np.polymul(A,B)
print(np.poly1d(res))

res=np.polymul(A,B)%q

print ("\n\nA*B (mod",q,"):")
print(np.poly1d(res))



print ("\n\n====== A-B =====")
res=np.polysub(A,B)

print(np.poly1d(res))

res=np.polysub(A,B)%q

print ("\n\nA-B (mod",q,"):")
print(np.poly1d(res))

print ("\n\nA/B =====")

res=np.floor(np.polydiv(A,B)[1])
print(np.poly1d(res))

res=np.floor(np.polydiv(A,B)[1])%q
print ("\n\nA/B (mod",q,"):")
print(np.poly1d(res))



print ("\n\nA/B (mod",q,"):")
print(np.poly1d(res))

A sample run is:

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 (mod 13 ):
   4      3      2
3 x + 11 x + 10 x + 5 x + 4


====== A-B =====
    2
-2 x + 3 x


A-B (mod 13 ):
    2
11 x + 3 x


A/B =====
 
3 x


A/B (mod 13 ):
 
3 x


A/B (mod 13 ):
 
3 x

And code:

Here is a running version:

Conclusion

And so the usage of RSA, Elliptic Curve and Discrete Logs will likely to be replaced soon, as they can be cracked by quantum computers. Currently NIST are assessing the likely replaced, and lattice cryptography is likely to be one of the main contenders for a winner. As lattice methods use polynomials and mod operations, the operations I have outlined are going to be important for the future of the Internet.