Polynomials and Mod p in Numpy

Polynomials and Mod p in Numpy

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.

Polynomials and (mod p)

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 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 (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 (mod 13):

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

Coding

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 ("\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))

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 (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:

https://asecuritysite.com/pqc/poly4

and:

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. For Post Quantum Cryptography standardization, NIST selected two lattice methods: CRYSTALS-KYBER (for key exchange and public key encryption) and CRYSTALS-DILITHIUM (for digital signatures). As lattice methods use polynomials and mod operations, the operations I have outlined are going to be important for the future of the security of the Internet.