LTK SageMath (2023)
Last updated on 14/04/2023
Contents
SageMath basics
For installation etc. refer to LTK.
Notebooks
Refer also to LW0200MATHEMATICS.
Invocation:
- 'sage' in a console starts a Sage session. To quit the session enter quit and then press .
- To start a Jupyter Notebook instead of a Sage console, run the command 'sage -n jupyter', then select 'New'
- HELP takes you to tutorials etc
Alternatively, there's the online version
Useful:
- With some minor exceptions, Sage uses the Python programming language, so most introductory books on Python will help you to learn Sage.
- Preceding a command with 'time' shows the time it took to perform the calculation.
- Use 'parent' to find out the construction
Object-orientation
Python
In Python, everything is an object so there isn’t any difference between types and classes. One can get the class of the object el by type(el). Behavior is defined through methods.
Sage specifics about classes
Compared to Python, Sage has particular ways to handle objects:
- Any classes for mathematical objects in Sage should inherit from SageObject rather than from object. Most of the time, they actually inherit from a subclass such as Parent or Element.
- Printing should be done through _repr_ instead of __repr__ to allow for renaming.
- More generally, Sage-specific special methods are usually named _meth_ rather than __meth__. For example, lots of classes implement _hash_ which is used and cached by __hash__. In the same vein, elements of a group usually implement _mul_, so that there is no need to take care about coercions as they are done in __mul__.
For more details, see the Sage Developer’s Guide.
Numbers
Some mathematical expressions return ‘exact’ values, rather than numerical approximations.
To get a numerical approximation, use either the function N or the method n (and both of these have a longer name, numerical_approx, and the function N is the same as n)). These take optional arguments prec, which is the requested number of bits of precision, and digits, which is the requested number of decimal digits of precision; the default is 53 bits of precision.
- If n is a number, len(n.str(2)) gives n's lenght as binary string.
- If n is a number, len(n.str(10)) gives n's lenght as decimal number.
Dynamic typing:
- a = 5 # a is an integer
- type(a)
- class 'sage.rings.integer.Integer'
- a = 5/3 # now a is a rational number
- type(a)
- class 'sage.rings.rational.Rational'
- a = 'hello' # now a is a string
- type(a)
- <... 'str'>
Operations
- 2**3 # ** means exponent
- 2^3 # ^ is a synonym for ** (unlike in Python)
- 10 % 3 # for integer arguments, % means mod, i.e., remainder
- 10/4
- 10//4 # for integer arguments, // returns the integer quotient
SageMath Number Theory
Basics
- Constructions - general “How do I construct … in Sage?”
- Constructions - number theory modular power, discrete log, primes, divisors, quadratic residus, ...
- Rings - general
- the integers, called ZZ in Sage
- the rational numbers – i.e., fractions, or ratios, of integers – called QQ in Sage
- the real numbers, called RR in Sage
- the complex numbers, called CC in Sage
Sage also knows about other rings, such as finite fields, p-adic integers, the ring of algebraic numbers, polynomial rings, and matrix rings. Here are constructions of some of these:
- GF(3)
- Finite Field of size 3
- GF(27, 'a') # need to name the generator if not a prime field
- Finite Field in a of size 3^3
- Zp(5)
- 5-adic Ring with capped relative precision 20
- sqrt(3) in QQbar # algebraic closure of QQ
- True
Sage has extensive functionality for number theory.
- Finite Rings and Fields
- Integer Mod Ring
-
Defining a finite ring of integers:
- One way:
- R = Integers(97)# 'Integers' creates a finite ring of integers mod 97
- R
- Ring of integers modulo 97
- list(R)
- 0...96
- parent(R)
- class 'sage.rings.finite_rings.integer_mod_ring.IntegerModRing_generic_with_category'
- Another way:
- R = IntegerModRing(97) # 'IntegerModRing(x) creates apparently the same of the preceding example
- parent(R)
- class 'sage.rings.finite_rings.integer_mod_ring.IntegerModRing_generic_with_category>
Working with elements:
- a = R(5)
- a
- 5
- parent(a)
- Ring of integers modulo 97
- a = R(2) / R(3)
- a
- 33
- a.rational_reconstruction()
- 2/3
- b = R(47)
- b^20052005
- 50
- b.modulus()
- 97
- b.is_square()
- True
Factorisation - often using integers or polynomials
The 'Factorization' class provides a structure for holding quite general lists of objects with integer multiplicities. These may hold the results of an arithmetic or algebraic factorization, where the objects may be primes or irreducible polynomials and the multiplicities are the (non-zero) exponents in the factorization.
Functions include:
- gcd(m, n)
- factor(n) - calls Pari’s factor C library function.
- qsieve (n) - Bill Hart - the best algorithm for factoring numbers of the form pq up to around 100 digits.
- ecm.factor(n) - GMP-ECM - Paul Zimmerman
- The elliptic curve factorization (ECM) algorithm is the best algorithm for factoring numbers of the form n=pm, where p is not “too big”. ECM is due to Hendrik Lenstra, which works by “pretending” that n is prime, choosing a random elliptic curve over Z/nZ, and doing arithmetic on that curve - if something goes wrong when doing arithmetic, we factor n.
To factor polynomials: e.g. define the sets of polynomials with rational coefficients and real coefficients:
- ratpoly. = PolynomialRing(QQ)
- realpoly. = PolynomialRing(RR)
You can then factor polynomials:
- factor(t^2-2)
- t^2 - 2
- factor(z^2-2)
- (z - 1.41421356237310) * (z + 1.41421356237310)
Congruences
Relative primes and Euler phi (totient) and theorem
Mod(x,p)
Mod(33,9) = 6
Euler's phi-function
phi(n) is the amount of numbers that are relatively prime to n.
- For a prime: phi(p)=p-1
- For a composite: phi(20)=phi(4)*phi(5)=8, and this is {1, 3, 7, 9, 11, 13, 17, 19}
Euler's Theorem
If gcd(x,n)=1 then xphi(n)=1 (mod n).
Relative primes
How to get list of relative primes for a given number? See ask.sagemath.org.
There are multiple ways to list integers coprime to a given integer in Sage.
One way is to build the ring of integers modulo m, then list the multiplicative group of that ring.
- sage: m = 8
- sage: Zmod(m).list_of_elements_of_multiplicative_group()
- [1, 3, 5, 7]
Note that this returns a list of Python integers:
- sage: type(Zmod(m).list_of_elements_of_multiplicative_group()[0])
To get Sage integers one would need
- sage: m = 8/li>
- sage: [ZZ(k) for k in Zmod(m).list_of_elements_of_multiplicative_group()]
- [1, 3, 5, 7]
Check:
- sage: [ZZ(k) for k in Zmod(m).list_of_elements_of_multiplicative_group()][0].parent()
- Integer Ring
Another way is to use the method coprime integers, which expects another argument to say how far you want to list integers that are coprime to m. To get them up to m - 1:
- sage: m = 8
- sage: m.coprime_integers(m)
To get them further:
- sage: m.coprime_integers(29) # list up to 29 (excluded)
- [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27]
These are returned as Sage integers:
- sage: m.coprime_integers(m)[0].parent()
- Integer Ring
Elliptic curves
Oblivious Transfer