Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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}$

share|improve this question

2 Answers 2

up vote 4 down vote accepted

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
share|improve this answer
    
+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? –  Sadeq Dousti Jun 5 '13 at 20:19
    
@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. –  J. M. Jun 6 '13 at 1:18

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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