Power of a polynomial mod (n, X^r - 1)

edit

Hello,

The following should be more adapted. I assume that you defined n, r and a:

sage: R.<x> = PolynomialRing(Integers(n), 'x')
sage: RR.<xx> = R.quotient(x^r - 1)
sage: (xx+a)^n
...

The last command evaluates the power within the quotient by x^r - 1 and is hence much faster then computing the power and then taking the quotient. As an example

sage: n = 3240
sage: r = 26
sage: a = 33
sage: (x+a)^n
x^3240 + 1620*x^3238 + 2430*x^3236 + 1944*x^3235 + 1620*x^3234
...
405*x^8 + 1620*x^6 + 1296*x^5 + 2430*x^4 + 1620*x^2 + 81
sage: RR((x+a)^n)      # slow method
648*xx^z5 + 2349*xx^24 + 2592*xx^23 + 1701*xx^22 + 1701*xx^20
...
648*xx^5 + 324*xx^4 + 2592*xx^3 + 2916*xx^2 + 648*xx + 1701
sage: (RR(xx+a))^n     # fast method
648*xx^z5 + 2349*xx^24 + 2592*xx^23 + 1701*xx^22 + 1701*xx^20
...
648*xx^5 + 324*xx^4 + 2592*xx^3 + 2916*xx^2 + 648*xx + 1701

You can then check on that example:

sage: RR((x+a)^n) == RR(x+a)^n 
True
sage: %timeit RR((x+a)^n)
125 loops, best of 3: 1.98 ms per loop
sage: %timeit RR((x+a))^n
625 loops, best of 3: 680 µs per loop