In this example, we will use polynomial operations for add, subtract, multiply and divide, and with the numpy library.
Polynomials Operations (mod p) |
Theory
A basic linear equation has the form of:
\(y=a x + b\)
and where \(a\) is defined as the gradient of the straight line, and \(b\) is the point at which is cuts the y-axis. This is known as a polynomial of order 1. For a polynomial with an order of two, we generate a quadratic equation:
\(y=a x^2 + bx +c\)
An example of a quadratic equation is \(y=x^2-2x+1\), and where \(a=1\), \(b=-2\) and \(c=1\). With polynomials with an order of five, we have the form:
\(a x^5 + b x^4 + c x^3 +d x^2 + e x + f\)
We can then represent this as an integer array of:
\([a,b,c,d,e,f]\)
In Python, a polynomial of \(5x^4 + 4x^3 + x^2 + 11 x + 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
In Lattice cryptography, we perform mathematical operations on these polynomials, such as adding, subtracting, multiplying, dividing and finding inverses. So let's take an example of:
\(A = 10 x^2 + 6x + 2\)
\(B = 12 x^2 + 3x + 2\)
If we add these we get:
\(A+B = 10 x^2 + 6x + 2 + 12 x^2 + 3x + 2 = 22 x^2 + 9x + 4\)
Now we can perform a (mod) operation on this, such as with \(\pmod {13}\):
\(A+B \pmod {13} = 22 x^2 + 9x + 4 \pmod{13} = 9 x^2 + 9x +4\)
Now let's look at multiplication, for this we have:
\(A \times B = (10 x^2 + 6x + 2) \times (12 x^2 + 3x + 2) = 120x^4 + 30 x^3 + 20 x^2 + 72 x^3 + 18 x^2 + 12 x + 24x^2 + 6x + 4\)
\(A \times B = 120x^4 + 102 x^3 + 62 x^2 + 18 x + 4\)
And now \(\pmod {13}\):
\(A \times B \pmod {13} = 120x^4 + 102 x^3 + 62 x^2 + 18 x + 4 \pmod{13} = 3x^4+11x^3+10x^2 + 5x + 4\)
Next we will perform a polynomial subtraction:
\(A-B = (10 x^2 + 6x + 2) - (12 x^2 + 3x + 2) = -2 x^2 + 3x\)
And now \(\pmod {13}\):
\(A-B \pmod{13} = -2 x^2 + 3x = 11 x^2 + 3x\)
Next we will perform a polynomial division. For this we will try \(A=x^2+2x+1\) and \(B=x+1\), and which will divide in with a remainder:
\(A \div B = (x^2 + 2x + 1) \div (x+1) = x+1\)
And now \(\pmod {13}\):
\(A \div B \pmod{13} = x-1\)
We use the\(\pmod p\) operation in cryptography to create a finite field, and where all the values range between zero and \(p-1\). This limits the integers values we have and is often represented as \(\mathbb{Z}_p\). Overall a\(\pmod p\) operation returns the remainder from an integer divide. With polynomials, we constrain each of the factors of the polynonials to a value between \(0\) and \(p-1\), and where we take each polynomial factor and perform a\(\pmod p\) operation with it. Some example code to implement this is:
import numpy as np import sys q=13 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)[0]) print("Divide:\n",np.poly1d(res)) res=np.floor(np.polydiv(A,B)[1]) print("Remainder:\n",np.poly1d(res)) res=np.floor(np.polydiv(A,B)[0])%q print ("\n\nA div B (mod",q,"):") print(np.poly1d(res)) print("\n\nA div B (mod {0} ):".format(q)) print(np.poly1d(res))
A sample run using \(A=4x^3+x^2+11x+10\) and \(B=3x^3+5x^2+2x+4\) is:
A: 3 2 4 x + 1 x + 11 x + 10 B: 3 2 3 x + 5 x + 2 x + 4 ====== A+B ===== 3 2 7 x + 6 x + 13 x + 14 A+B (mod 13 ): 3 2 7 x + 6 x + 1 ====== A*B ===== 6 5 4 3 2 12 x + 23 x + 46 x + 103 x + 76 x + 64 x + 40 A*B (mod 13 ): 6 5 4 3 2 12 x + 10 x + 7 x + 12 x + 11 x + 12 x + 1 ====== A-B ===== 3 2 1 x - 4 x + 9 x + 6 A-B (mod 13 ): 3 2 1 x + 9 x + 9 x + 6 A/B ===== Divide: 1 Remainder: 2 -6 x + 8 x + 4 A div B (mod 13 ): 1 A div B (mod 13 ): 1
The code is here: