The Mod P polynomials are used in some of the proposed methods in quantum computer robust cryptography. This page outlines the operation of Mod P polynomials:
Mod P Polynomial OperationsTheoryLet's say we have: \(a = 2x^4 + 3x^3 + 10x + 3\) \(b = 3x^5 + 14x^3 + 10x + 4\) Then to add Mod 17, we get: \(3x^5 + 2x^4 + 3x + 7\) Then to subtract Mod 17, we get: \(14x^5 + 2x^4 + 6x^3 + 16\) Then to multiply Mod 17, we get: \(6x^9 + 9x^8 + 11x^7 + 4x^6 + 12x^5 + 8x^4 + 3x^3 + 15x^2 + 2x + 12\) A sample run is: a(x)= [3, 10, 0, 3, 2] b(x)= [4, 10, 0, 14, 0, 3] p= 17 == Operations === A + B (mod p): [7, 3, 0, 0, 2, 3] A * B (mod p): [12, 2, 15, 3, 8, 12, 4, 11, 9, 6] A - B (mod p): [16, 0, 0, 6, 2, 14] Using Polynomial notation a(x)= 2x^4 + 3x^3 + 10x + 3 b(x)= 3x^5 + 14x^3 + 10x + 4 p= 17 == Operations === A + B (mod p): 3x^5 + 2x^4 + 3x + 7 A * B (mod p): 6x^9 + 9x^8 + 11x^7 + 4x^6 + 12x^5 + 8x^4 + 3x^3 + 15x^2 + 2x + 12 A - B (mod p): 14x^5 + 2x^4 + 6x^3 + 16 CodingHere is an outline of the code: import sys import fracModulo import math from fractions import gcd from fractions import Fraction as frac from operator import add from operator import neg from operator import mod if (len(sys.argv)>1): p=int(sys.argv[1]) if (len(sys.argv)>2): a=eval("["+sys.argv[2]+"]") if (len(sys.argv)>3): b=eval("["+sys.argv[3]+"]") def modPoly(c,k): if(k==0): print("Error in modPoly(c,k). Integer k must be non-zero") else: return [fracModulo.fracMod(x,k) for x in c] def subPoly(c1,c2): [c1,c2]=resize(c1,c2) c2=list(map(neg,c2)) out=list(map(add, c1, c2)) return trim(out) def multPoly(c1,c2): order=(len(c1)-1+len(c2)-1) out=[0]*(order+1) for i in range(0,len(c1)): for j in range(0,len(c2)): out[j+i]=out[j+i]+c1[i]*c2[j] return trim(out) def resize(c1,c2): if(len(c1)>len(c2)): c2=c2+[0]*(len(c1)-len(c2)) if(len(c1)<len(c2)): def resize(c1,c2): if(len(c1)>len(c2)): c2=c2+[0]*(len(c1)-len(c2)) if(len(c1)<len(c2)): c1=c1+[0]*(len(c2)-len(c1)) return [c1,c2] def trim(seq): if len(seq) == 0: return seq else: for i in range(len(seq) - 1, -1, -1): if seq[i] != 0: break return seq[0:i+1] def divPoly(N,D): N, D = list(map(frac,trim(N))), list(map(frac,trim(D))) degN, degD = len(N)-1, len(D)-1 if(degN>=degD): q=[0]*(degN-degD+1) while(degN>=degD and N!=[0]): d=list(D) [d.insert(0,frac(0,1)) for i in range(degN-degD)] q[degN-degD]=N[degN]/d[len(d)-1] d=[x*q[degN-degD] for x in d] N=subPoly(N,d) degN=len(N)-1 r=N else: q=[0] r=N return [trim(q),trim(r)] def addPoly(c1,c2): [c1,c2]=resize(c1,c2) out=list(map(add, c1, c2)) return trim(out) def addPoly(c1,c2): [c1,c2]=resize(c1,c2) out=list(map(add, c1, c2)) return trim(out) class Poly(list): def __repr__(self): # joiner[first, negative] = str joiner = { (True, True): '-', (True, False): '', (False, True): ' - ', (False, False): ' + ' } result = [] for power, coeff in reversed(list(enumerate(self))): j = joiner[not result, coeff < 0] coeff = abs(coeff) if coeff == 1 and power != 0: coeff = '' f = {0: '{}{}', 1: '{}{}x'}.get(power, '{}{}x^{}') if (coeff!=0): result.append(f.format(j, coeff, power)) return ''.join(result) or '0' p=17 a=[3,10,0,3,2] b=[4,10,0,14,0,3] print("a(x)=\t",a) print("b(x)=\t",b) print("p=\t",p) print("\n== Operations ===") print("A + B (mod p):\t",modPoly(addPoly(a,b),p)) print("A * B (mod p):\t",modPoly(multPoly(a,b),p)) print("A - B (mod p):\t",modPoly(subPoly(a,b),p)) print("\nUsing Polynomial notation") print("a(x)=\t",Poly(a)) print("b(x)=\t",Poly(b)) print("p=\t",p) print("\n== Operations ===") print("A + B (mod p):\t",Poly(modPoly(addPoly(a,b),p))) print("A * B (mod p):\t",Poly(modPoly(multPoly(a,b),p))) print("A - B (mod p):\t",Poly(modPoly(subPoly(a,b),p))) A sample run is: a(x)= [3, 10, 0, 3, 2] b(x)= [4, 10, 0, 14, 0, 3] p= 17 == Operations === A + B (mod p): [7, 3, 0, 0, 2, 3] A * B (mod p): [12, 2, 15, 3, 8, 12, 4, 11, 9, 6] A - B (mod p): [16, 0, 0, 6, 2, 14] Using Polynomial notation a(x)= 2x^4 + 3x^3 + 10x + 3 b(x)= 3x^5 + 14x^3 + 10x + 4 p= 17 == Operations === A + B (mod p): 3x^5 + 2x^4 + 3x + 7 A * B (mod p): 6x^9 + 9x^8 + 11x^7 + 4x^6 + 12x^5 + 8x^4 + 3x^3 + 15x^2 + 2x + 12 A - B (mod p): 14x^5 + 2x^4 + 6x^3 + 16 Presentation |