6
$\begingroup$

Let $N$ be a prime, and $q$ be a positive integer. Given a polynomial $f(x)$ in $R = \mathbb Z[x]/(x^N-1)$, I want to find another polynomial $f_q(x)$ in $R_q = \mathbb Z_q[x]/(x^N-1)$, such that

$$f(x)f_q(x)=1 \pmod q$$

I want Mathematica to tell me

  1. whether the inverse polynomial $f_q(x)$ exists; and
  2. if so, find $f_q(x)$.

Examples for $N=11$ and $q=32$ are cited from Wikipedia's entry on NTRUEncrypt:

$f(x) = -1 + x + x^2 - x^4 + x^6 +x^9 - x^{10}$

$f_q(x) = 5 + 9x + 6x^2 + 16x^3 + 4x^4 + 15x^5 + 16x^6 + 22x^7 + 20x^8 + 18x^9 + 30x^{10}$

$\endgroup$

2 Answers 2

6
$\begingroup$

As it turns out, there's an (undocumented) function eminently suitable for the task:

poly = -1 + x + x^2 - x^4 + x^6 + x^9 - x^10;
PolynomialMod[Algebra`PolynomialPowerMod`PolynomialPowerMod[poly, -1, x, x^11 - 1], 32]
   5 + 9 x + 6 x^2 + 16 x^3 + 4 x^4 + 15 x^5 + 16 x^6 + 22 x^7 + 20 x^8 + 18 x^9 + 30 x^10

Check the result:

PolynomialMod[PolynomialRemainder[poly %, x^11 - 1, x], 32]
   1

If you're the conservative sort, and you're not too keen on the use of undocumented functions, then you might want to remember that the extended Euclidean algorithm is a very useful thing for the computation of modular inverses (Bézout's identity):

PolynomialMod[PolynomialExtendedGCD[-1 + x + x^2 - x^4 + x^6 + x^9 - x^10,
                                    x^11 - 1, x][[2, 1]], 32]
   5 + 9 x + 6 x^2 + 16 x^3 + 4 x^4 + 15 x^5 + 16 x^6 + 22 x^7 + 20 x^8 + 18 x^9 + 30 x^10
$\endgroup$
2
  • $\begingroup$ +1, great! While @Daniel Lichtblau's answer was very nice in that it made me learn a bit about Gröbner bases, this answer is excellent in its simplicity. Reading Mathematica's documentation, I think we can perform the task in an even simpler way: PolynomialMod[PolynomialRemainder[poly^-1, x^11 - 1, x], 32]. Am I right? $\endgroup$ Jun 5, 2013 at 20:19
  • $\begingroup$ @Sadeq, that works, but I'm personally more inclined to use PolynomialPowerMod[], in the same manner that I'd use PowerMod[] for the modular inversion of a number. $\endgroup$ Jun 6, 2013 at 1:18
6
$\begingroup$

Use a Gröbner basis.

The idea is to set up an equation for this multiplicative inverse, in a ring where both $x^{11}-1$ and $32$ are zero (that is, $\mathbf Z[x]/(32,x^{11}-1)$). Then unravel that equation using GroebnerBasis to get the variable representing this reciprocal to f in terms of x:

f = -1 + x + x^2 - x^4 + x^6 + x^9 - x^10;
defpoly = x^11 - 1;

Since we do not have a field for our coefficients, we compute a basis over the integers:

finv = First[finv /. Solve[Last[
             GroebnerBasis[{f*finv - 1, defpoly, 32}, {finv, x}, 
                           CoefficientDomain -> Integers]] == 0, finv]]

(* Out[97]= 5 + 9 x + 6 x^2 - 16 x^3 + 4 x^4 + 15 x^5 - 16 x^6 - 
 10 x^7 - 12 x^8 - 14 x^9 - 2 x^10 *)

finv = PolynomialMod[finv, 32]

(* Out[98]= 5 + 9 x + 6 x^2 + 16 x^3 + 4 x^4 + 15 x^5 + 16 x^6 + 
 22 x^7 + 20 x^8 + 18 x^9 + 30 x^10 *)

For more (perhaps painfully more) applications of such bases, here is a PDF link.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.