modular exponentiation for polynomial ring

asked 2019-07-28 20:34:19 +0200

anonymous user


Hello, I have the following:

p = 1119823

F.<x> = PolynomialRing(Integers(p))

f = F(x^6 + 1119810*x^5 + 60*x^4 + 1119733*x^3 + 1119688*x^2 + 567*x + 1119338)

I have big n and want to calculate f^n but I don't know how I can do It fast in Sage. I know that if I can find order of element f then I can do f^(n % f_order).But I don't know order and how find It in this case. So please explain me how I can calculate f^n fast?

edit retag flag offensive close merge delete


How big is $n$? Also try GF(p) instead of Integers(p).

rburing gravatar imagerburing ( 2019-07-29 16:03:00 +0200 )edit

The leading term of $f^n$ is $x^{6n}$, so it will never be equal to 1 for $n>0$, so $f$ has infinite order, as most elements of polynomial rings do. In a quotient ring the order can be finite.

rburing gravatar imagerburing ( 2019-07-29 18:08:15 +0200 )edit

Thank you for reply. Let's say n is around 73 binary digits. GF(P) seems to give the same result - I can't calculate f^n because it's too slow

ddwew gravatar imageddwew ( 2019-07-29 18:13:35 +0200 )edit

Please can you explain me how to use quotient ring in this case?

ddwew gravatar imageddwew ( 2019-07-29 18:14:46 +0200 )edit

Please explain why do you need the polynomial f^n of big degree $6n$ in x. Do you take it modulo some polynomial after this? Which is the framework for the whole story. (People doing cryptology tend to be very criptic sometimes, this is not the case in the present post, we have a lot of code and a clear situation, but there is still a tendency, in this case we need some details about the things to be done after having the polynomial.)

dan_fulea gravatar imagedan_fulea ( 2019-07-29 18:58:09 +0200 )edit