Ask Your Question
1

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

asked 2012-02-27 07:39:15 +0100

anonymous user

Anonymous

updated 2012-08-04 00:17:51 +0100

vdelecroix gravatar image

I need to calculate (X + a)^n mod (n, X^r - 1), where n can be very large.

I use the following code:

R.<x>=PolynomialRing(Integers(n)) pow(x + a, n, X^r - 1)

A better (i.e. faster) solution?

Thanks.

edit retag flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted
0

answered 2012-08-04 00:15:27 +0100

vdelecroix gravatar image

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
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2012-02-27 07:39:15 +0100

Seen: 1,157 times

Last updated: Aug 04 '12