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).
http://wiki.sagemath.org/quickref]
The basic arithmetic operations, +, -, *, /, are available
from the keyboard. Note that the division operator returns a quotient
(eg 7/2 returns 7/2) so the answer should be truncated with
the "truncating division" // function (eg 7//2
returns 3). The modular reduction operator is represented by the mod
command (eg mod(7,2) returns 1). Exponentiation is represented
with the ^ 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.)
Examples:
mod(8 + 7, 13)mod(5 * 4, 13)7 // 23^2pow(2,6,11)
(returns an answer of 9)
In addition to the basic arithmetic operations for integers SAGE implements gcd and the extended gcd operations as basic functions:
gcd(15,6)xgcd(23,7)Modular inversion
is implemented with the inverse_mod command, so
inverse_mod(3,19)
returns the value 13.
Factoring and primality testing are implemented with the factor()
and is_prime() commands. Examples of their use are
factor(123456)
which returns 2^6 * 3 * 643 and the command
is_prime(643)
which returns the value True.
Other useful functions include:
prime_factors(1234)
divisors(1234)
next_prime(1234)
nth_prime(10)
is_prime(1234)
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
continued_fraction(x)
5.jacobi(1237) - Jacobi/Legendre/Kronecker symbol (also kronecker(5,1237)
square_root_mod_prime(mod(123,1001)) - 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:
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)
sage: gcd(3*x^2+6*x-9,5*x^3-2*x+2)
sage: xgcd(3*x^2+6*x-9,5*x^3-2*x+2)
sage: factor(3*x^5+5*x-8)
sage: (3*x^5+5*x-8).factor_mod(3) (Factor with coeffs in Z3)
sage: Z5P.<y> = GF(5)[]
sage: Z5P([1,2,3])
sage: (y^5 + 3*y^2 - 2*y + 7) // (y + 1)
sage: xgcd(3*y^2+6*y-9,2*y^3-2*y+3)
sage: factor(2*y^3-2*y+3)
sage: (2*y^3-2*y+3).is_irreducible() (is it irreducible?)
Polynomials are manipulated and combined with the same basic operations
as are used on integers, +, -, *, ^, //, %.
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()
sage: (i+2)*(3*i-5)
sage: (i+2)^10
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: (2+i1)^10
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
principle (cannot be generated by a single number in the ring).
sage: QF3.<sr3> = NumberField(x^2 + 3)
sage: ZQ3 = QF3.maximal_order()
sage: ZQ3.basis()
[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()
sage: ZQ5.basis()
[1, sr5]
sage: factor(ZQ5.ideal(12))
(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 FiniteField
(equivalently 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
reference manual
and in API documentation.
sage: GF125a.<b> = GF(5^3) # Let SAGE choose the representation
sage: b^15
sage: GF5.<x5>=GF(5)[]; GF125.<a> = GF(5^3,'a',modulus=x5^3+x5+1)
sage: GF125.multiplicative_generator()
sage: for i in range(124): # Compute order(a) the hard way
print i,a^i
sage: a.multiplicative_order() # The easy way
The continued_fraction function
produces continued fraction expansions and the value
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.value()
37/21
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.value()
159018721/64919121
sage: a=continued_fraction(pi,bits=30); a # 30-bit accuracy (about 9 digits)
[3, 7, 15, 1, 294]
sage: float(pi-a.value())
-1.2349787859022854e-09
sage: convergents(a)
[3, 22/7, 333/106, 355/113, 104703/33328]