SAGE has basic commands and subroutines which implement all basic number theory (and many other things). A general introduction to SAGE use and how SAGE can be accessed at UMBC can be found in a separate document.
SAGE supports the use of integers of arbitrary length and a number of other basic data types such as polynomials. In addition to SAGE's native functions, the extensive functionality of PARI/GP can also be used from within SAGE (tutorial).
The basic arithmetic operations,
+, -, *, /, are available
from the keyboard. Note that the division operator returns a quotient
7/2 returns 7/2) so the answer should be truncated with
the "truncating division"
// function (eg
returns 3). The modular reduction operator is represented by the
mod(7,2) returns 1). Exponentiation is represented
^ symbol. The pow() function can be used for
exponentiation if called with two parameters, or efficient modular
exponentiation if called with three parameters. (pow(a,b,c) returns the same
result as ((a^b) % c), but is much more efficient.)
mod(8 + 7, 13)
mod(5 * 4, 13)
7 // 2
In addition to the basic arithmetic operations for integers SAGE implements gcd and the extended gcd operations as basic functions:
is implemented with the
inverse_mod command, so
returns the value 13.
Factoring and primality testing are implemented with the factor()
and is_prime() commands. Examples of their use are
which returns 2^6 * 3 * 643 and the command
which returns the value
Other useful functions include:
prime_pi(1234)- number of primes less than n
euler_phi(1234)- φ(n) = number of integers coprime to n
CRT(ra,rb,a,b)- Chinese Remainder Theorem: find ra, rb such that ra*a+rb*b = gcd(a,b)
primitive_root(p)- generator of Zp* for prime p
5.jacobi(1237)- Jacobi/Legendre/Kronecker symbol (also
mod(123,1001).sqrt()- Modular square root (Shanks/Tonelli/RESSOL algorithm)
Polynomials are constructed explicitly in SAGE, with the coefficients specified. This is similar to MAGMA, but differs from the much more casual approach in Maple and Mathematica, where polynomials are viewed formally as symbols with at most a generic treatment of coefficients. Some examples are:
(Factor with coeffs in Z3)
sage: ZP.<x> = ZZ
sage: (x^5 + 3*x^2 - 2*x + 7) // (x + 1)
sage: (x^5 + 3*x^2 - 2*x + 7).quo_rem(x + 1)
(is it irreducible?)
sage: Z5P.<y> = GF(5)
sage: (y^5 + 3*y^2 - 2*y + 7) // (y + 1)
Polynomials are manipulated and combined with the same basic operations
as are used on integers,
+, -, *, ^, //, %.
Polynomials with coefficients over a finite field can be enumerated with the following trick: sage: Z2P.<z> = GF(2) sage: for num in range(32): # Enumerate polys of degree 5 ....: print z^5 + sum([coeff*z^i for i,coeff in enumerate([(num//2**i)%2 for i in range(5)])])
and a search for low density primitive polynomials can be implemented with a python generator for low-density lists (ref). Here we list all density 5 primitive polynomials over GF2 of degree 32. You can also check and confirm that there are no lower density primitive polynomials of that degree. sage: def fixeddensity(len, density): ....: if len == density: yield *len ....: elif density == 0: yield *len ....: else: ....: for leftlist in fixeddensity(len-1, density): ....: yield leftlist +  ....: for leftlist in fixeddensity(len-1, density-1): ....: yield leftlist +  sage: for it in fixeddensity(31,4): ....: thepoly = z^32 + sum([coeff*z^i for i,coeff in enumerate(it)]) ....: if thepoly.is_primitive(): print thepoly
SAGE currently has no convenient and complete way to work with Gaussian integers.
A kludge which allows simple operations with the Gaussian integers is
to represent them as a formal polynomial ring quotient. This allows you
to add and multiply elements, but there is no concept of division, modular
reduction or factoring:
sage: ZZP = PolynomialRing(ZZ,'x'); x = ZZP.gen(); GI = ZZP.quotient(x^2 + 1, 'i'); i=GI.gen()
A more exotic representation (but more appropriate for more general
quadratic number fields) is to represent the Gaussian Integers as the
maximal order in the number field Q(√-1).
sage: QFi.<sr1> = NumberField(x^2 + 1)
sage: GI = QFi.order(sr1) # Create the Gaussian Integers
sage: i1 = QFi(sr1)
sage: 120 // (2-sr1)
sage: factor(GI.ideal(25+sr1)) # Factor as ideals
# So 25 + sqrt(-1) = (1 + 4 sqrt(-1))(1 + sqrt(-1))(1 + 2 sqrt(-1))
(Fractional ideal (4*sr1 + 1)) * (Fractional ideal (sr1 + 1)) * (Fractional ideal (2*sr1 + 1))
The ideal factorization is the best we can do for all of the fields without unique factorization, and it is not too hard to translate back to usual factorization by eye in the case of the Gaussian integers.
Some examples are the Eisenstein Integers, the ring of integers
in Q(√-3), and the integers in Q(√-5),
where unique factorization fails, so many of the ideals are not
principal (cannot be generated by a single number in the ring).
sage: QF3.<sr3> = NumberField(x^2 + 3)
sage: ZQ3 = QF3.maximal_order()
[1/2*sr3 + 1/2, sr3]
sage: factor(ZQ3.ideal(7)) # 7 splits as 7 = (2 - sqrt(-3))(2 + sqrt(-3))
(Fractional ideal (sr3 - 2)) * (Fractional ideal (-sr3 - 2))
sage: QF5.<sr5> = NumberField(x^2 + 5)
sage: ZQ5 = QF5.maximal_order()
(Fractional ideal (2, sr5 + 1))^4 * (Fractional ideal (3, sr5 + 1)) * (Fractional ideal (3, sr5 - 1))
Finite fields are cleanly represented in SAGE by the
GF) class. A finite field can be created with
SAGE choosing the representation, or a specific defining polynomial can
be specified. This is well documented in the SAGE
and in API documentation.
sage: GF125a.<b> = GF(5^3) # Let SAGE choose the representation
sage: GF5.<x5>=GF(5); GF125.<a> = GF(5^3,'a',modulus=x5^3+x5+1)
sage: for i in range(124): # Compute order(a) the hard way
sage: a.multiplicative_order() # The easy way
You can also specify the defining polynomial for the finite field explicitly. The following code illustrates how to search for a primitive polynomial (i.e. so that the root w has full multiplicative order in the resulting Galois field) of a particular form.
sage: Z2P.<z> = GF(2)
sage: for num in range(2**10): # Find primitive degree 128 polys
thepoly = z^128 + sum([coeff*z^i for i,coeff in enumerate([(num//2**i)%2 for i in range(10)])])
if thepoly.is_primitive(): print thepoly
sage: GF2p128.<w> = GF(2^128,'w',modulus=z^128+z^7+z^2+z+1)
And now you can confirm that the root w has full order, by checking all possible factors of the group order.
3 * 5 * 17 * 257 * 641 * 65537 * 274177 * 6700417 * 67280421310721
w^125 + w^123 + w^120 + w^118 + ... (certainly not 1)
w^126 + w^125 + w^124 + w^123 + ... (again not 1)
sage: for p in prime_factors(2**128-1): # Check all possible cofactors
....: if w^((2^128-1)/p)==1:
....: print "Not primitive, w^((2**128-1)/",p," is 1"
(Confirm the operation of the code by running it against (w+1) instead of w, observing that (w+1) does not have full order.)
produces continued fraction expansions and the
function can convert continued fraction expansions to numbers.
SAGE currently does not correctly deal with periodic continued fractions
produced by quadratic surds.
sage: a = continued_fraction(74/42); a
[1, 1, 3, 5]
sage: a=continued_fraction(sqrt(6)); a # a truncated value
[2, 2, 4, 2, 4, 2, 4, 2, 4, 2, 4, 2, 4, 2, 4, 2, 2, 1]
sage: a=continued_fraction(pi,bits=30); a # 30-bit accuracy (about 9 digits)
[3, 7, 15, 1, 294]
[3, 22/7, 333/106, 355/113, 104703/33328]