Subsections

10. Taking powers


10.1 Integers

To compute $ 51^{2006} \pmod{97}$ in SAGE, type

sage: R = Integers(97)
sage: a = R(51)
sage: a^2006
12

Instead of R = Integers(97) you can also type R = IntegerModRing(97).


10.2 Matrices

The syntax is illustrated by the example below.

sage: R = IntegerModRing(51)
sage: M = MatrixSpace(R,3,3)
sage: A = M([1,2,3, 4,5,6, 7,8,9])
sage: A^2006
[42  0  9]
[30 45  9]
[18 39  9]


10.3 Polynomials

To compute $ x^{2006} \pmod x^3 + 7$ in $ GF(97)[x]$ , we create the quotient ring $ GF(97)[x]/(x^3+7)$ , and compute $ x^2006$ in it. As a matter of SAGE notation, we must distinguish between the $ x$ in $ GF(97)[x]$ and the corresponding element (which we denote by $ a$ ) in the quotient ring $ GF(97)[x]/(x^3+7)$ .

sage: R = PolynomialRing(GF(97),'x')
sage: x = R.gen()
sage: S = R.quotient(x^3 + 7, 'a')
sage: a = S.gen()
sage: S
Univariate Quotient Polynomial Ring in a over 
Finite Field of size 97 with modulus x^3 + 7
sage: a^2006
4*a^2

Another approach to this:

sage: R = PolynomialRing(GF(97),'x')
sage: x = R.gen()
sage: S = R.quotient(x^3 + 7, 'a')
sage: a = S.gen()
sage: time a^20062006
CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s
Wall time: 0.03
80*a
sage: gap.eval("R:= PolynomialRing( GF(97))")
'PolynomialRing(..., [ x_1 ])'
sage: gap.eval("i:= IndeterminatesOfPolynomialRing(R)")
'[ x_1 ]'
sage: gap.eval("x:= i[1];;")
''
sage: gap.eval("f:= x;;")
''
sage: gap.eval("PowerMod( R, x, 20062006, x^3+7 ); time;")
'Z(97)^41*x_1\n5'
sage: time gap.eval("PowerMod( R, x, 20062006, x^3+7 ); time;")
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00
'Z(97)^41*x_1\n0'
sage: gap.eval("PowerMod( R, x, 2006200620062006, x^3+7 ); time;")
'Z(97)^4*x_1^2\n0'
sage: time a^2006200620062006
CPU times: user 0.04 s, sys: 0.00 s, total: 0.05 s
Wall time: 0.06
43*a^2
sage: gap.eval("PowerMod( R, x, 2006200620062006, x^3+7 ); time;")
'Z(97)^4*x_1^2\n0'
We can see that GAP is a bit faster. (NOTE: GAP's ``time'' command returns the number of ``GAP stones'' the computation took, not the ``CPU time'' or ``Wall time''.)

See About this document... for information on suggesting changes.