modular exponentiation for polynomial ring
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?
How big is $n$? Also try
GF(p)instead ofIntegers(p).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.
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^nbecause it's too slowPlease can you explain me how to use quotient ring in this case?
Please explain why do you need the polynomial
f^nof big degree $6n$ inx. 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.)