Resultant of a polynomial with x^n–1
- by devin.omalley
Resultant of a polynomial with x^n–1 (mod p)
I am implementing the NTRUSign algorithm as described in http://grouper.ieee.org/groups/1363/lattPK/submissions/EESS1v2.pdf , section 2.2.7.1 which involves computing the resultant of a polynomial. I keep getting a zero vector for the resultant which is obviously incorrect.
private static CompResResult compResMod(IntegerPolynomial f, int p) {
int N = f.coeffs.length;
IntegerPolynomial a = new IntegerPolynomial(N);
a.coeffs[0] = -1;
a.coeffs[N-1] = 1;
IntegerPolynomial b = new IntegerPolynomial(f.coeffs);
IntegerPolynomial v1 = new IntegerPolynomial(N);
IntegerPolynomial v2 = new IntegerPolynomial(N);
v2.coeffs[0] = 1;
int da = a.degree();
int db = b.degree();
int ta = da;
int c = 0;
int r = 1;
while (db > 0) {
c = invert(b.coeffs[db], p);
c = (c * a.coeffs[da]) % p;
IntegerPolynomial cb = b.clone();
cb.mult(c);
cb.shift(da - db);
a.sub(cb, p);
IntegerPolynomial v2c = v2.clone();
v2c.mult(c);
v2c.shift(da - db);
v1.sub(v2c, p);
if (a.degree() < db) {
r *= (int)Math.pow(b.coeffs[db], ta-a.degree());
r %= p;
if (ta%2==1 && db%2==1)
r = (-r) % p;
IntegerPolynomial temp = a;
a = b;
b = temp;
temp = v1;
v1 = v2;
v2 = temp;
ta = db;
}
da = a.degree();
db = b.degree();
}
r *= (int)Math.pow(b.coeffs[0], da);
r %= p;
c = invert(b.coeffs[0], p);
v2.mult(c);
v2.mult(r);
v2.mod(p);
return new CompResResult(v2, r);
}
There is pseudocode in http://www.crypto.rub.de/imperia/md/content/texte/theses/da_driessen.pdf which looks very similar.
Why is my code not working?
Are there any intermediate results I can check?
I am not posting the IntegerPolynomial code because it isn't too interesting and I have unit tests for it that pass. CompResResult is just a simple "Java struct".
