What is the fastest way to do finite field arithmetic in SAGE?

Question

I am using SAGE to do some computations in a finite field of prime order $p$. I don't have much experience with SAGE (or any programming) so I'm looking for help with efficiency/speed. My computations involve products of terms of the form $a^{b^c}$. Now clearly, $b^c$ may be regarded modulo $(p-1)$ so rather than just using mod($a^{b^c}$,$p$), I thought it might be faster to reduce the exponent $b^c$ first. I've tried doing this as follows: Set R=Integers($p$) (I've tried R=GF(p) as well and this worked but didn't seem to change the run-time) and S=Integers($p-1$) and putting the terms R(a)^(S(b^c)) into my code. When $p=983$, this wasn't too slow (the largest $b$ and $c$ considered was $245$ for both). Now I'm doing a similar computation with $p=126131$ and the computer seems to be having some trouble. Is there a much more efficient way of computing these exponents? Thank you in advance.

Answer 1

I did some timings in SageMath. The function randint(i, j) produces a random integer between i and j.

sage: p = 126131
sage: S = Integers(p-1)
sage: %timeit pow(randint(100,200), randint(100, 200), p-1)
7.09 µs ± 245 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
sage: %timeit S(randint(100,200)^randint(100, 200))
4.48 µs ± 22.9 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
sage: %timeit S(randint(100,200))^randint(100, 200)
3.18 µs ± 45.5 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

So among the choices of pow, S(b^c), and S(b)^c, the last is fastest. It's just a factor of 2, and that may not be enough for what you're doing.