Archive

Posts Tagged ‘computer algebra system’

Compiling Sage on Linux and Mac OS X

14 November 2010 4 comments

Compiling Sage can be a difficult process. The difficulty is compounded by the many versions of the GNU/Linux and Mac OS X operating systems. In this post, I don’t want to cover every possible ways of compiling Sage on each operating system. My goal here is to provide a general overview of how to compile Sage on Ubuntu 10.10 and Mac OS X 10.6.x.

Ubuntu 10.10

For Linux, it should be sufficient to explain how to compile Sage under Ubuntu. The following commands were tested under Ubuntu 10.10. First, make sure you have the necessary tools for compiling Sage. To install these tools, execute the following command from a terminal window:

$ sudo apt-get install build-essential gfortran m4 readline-common libreadline-dev

Suppose you have downloaded the Sage source distribution and it is saved as the file named sage-x.y.z.tar. The file extension “.tar” signifies that sage-x.y.z.tar is a tar archive, also called a tar file or a tarball. To compile Sage, you need to launch a terminal window, extract the Sage source files from the tarball, and use development tools that come with Ubuntu to compile Sage. Suppose the Sage source tarball is located at

/home/username/sage-x.y.z.tar

where “username” is your username, the one you use to login to your Ubuntu system; you should replace “username” your actual username. Say you want to compile Sage under the directory /home/username/. From your terminal window, navigate to your home directory and extract the source tarball:

$ cd
$ tar -xf sage-x.y.z.tar

which will produce a directory called

/home/username/sage-x.y.z/

that contains all the packages that are distributed with the Sage source distribution. You are now ready to compile Sage as contained under the latter directory. Note that you can rename the latter directory to, say, /home/username/mysage/ as follows:

$ mv sage-x.y.z mysage

If you have a directory, say, /home/username/bin/ and you want to extract the Sage source tarball to that directory, you can do so as follows:

$ tar -xf sage-x.y.z.tar -C /home/username/bin

Here, it is assumed that you want to compile the Sage source as contained under

/home/username/sage-x.y.z/

This top-level directory is usually referred to as SAGE_ROOT and is where the compiled version of Sage resides. The next step is to navigate to the latter directory and start the automated compilation process:

$ cd /home/username/sage-x.y.z/
$ make

Usually, that is all you need to do. The rest of the compilation process is non-interactive and takes at most a few hours, depending on your system.

Note that compiling Sage is very taxing on your system’s resources, i.e. CPU, RAM, disk space, and so on. Make sure you have sufficient system resources; for example, you could close all running applications and ensure you have at least 2 GB of free disk space for Sage. Furthermore, the compilation process can take from a dozen or so minutes to a few hours, depending on your system’s hardware and how you customized the compilation process. By default, the compilation process uses one thread to compile Sage, which means that every component is compiled one after the other, i.e. serial compilation. Serial compilation of Sage is known to take up to an hour or more to complete.

On a multi-core or multi-CPU system, the compilation process can be parallelized. This means that many components of Sage can be compiled in parallel, hence reducing the time it takes for the compilation process to complete. The general steps to compile Sage in parallel are as follows. Determine the number of cores on your system and decide on how many threads you want to devote to a parallel compilation of Sage. On Ubuntu, detailed information about your system’s CPU is contained in the file

/proc/cpuinfo

Read through that file to determine the number of cores on your system. Say your system has two cores and you want to use two threads for compiling Sage in parallel. Then the necessary setup to compile Sage with two threads is:

$ SAGE_PARALLEL_SPKG_BUILD="yes"; export SAGE_PARALLEL_SPKG_BUILD
$ MAKE="make -j2"; export MAKE
$ make

This should initiate the process of compiling Sage in parallel. If your system allows for compiling Sage with more threads, e.g. 4 or 8 threads, then change “-j2” to “-j4” or “-j8” accordingly.

Once all components of Sage are successfully compiled, the compilation process will automatically build the HTML version of the Sage standard documentation. This documentation includes a tutorial, an FAQ, a collection of thematic tutorials, a reference manual, an installation guide, among other documents. Building the HTML version of the Sage standard documentation does not require \LaTeX. However, for best results, it is recommended that you have \LaTeX installed on your system. Furthermore, \LaTeX is a prerequisite for building the PDF version of the Sage standard documentation. The following command installs the full \LaTeX distribution that comes with Ubuntu:

$ sudo apt-get install texlive-full

This will also install necessary tools for building both the HTML and PDF versions of the Sage documentation. To manually build the HTML version of the documentation, do the following from within the SAGE_ROOT directory:

$ ./sage -docbuild all html  # or
$ ./sage -docbuild --no-pdf-links all html

To build the PDF version of the documentation, do

$ ./sage -docbuild all pdf

For further options to customize your build of the Sage standard documentation, see the output of the following command:

$ ./sage -docbuild

You can also download the documentation from

http://www.sagemath.org/help.html

or view it online at

http://www.sagemath.org/doc

To customize the compilation process to your particular needs, refer to the file

SAGE_ROOT/Makefile

Once the compilation process completes, there is no separate installation process for your newly compiled Sage. You can think of Sage as being compiled and installed under SAGE_ROOT. To begin using your freshly compiled version of Sage, navigate to SAGE_ROOT and launch Sage as follows:

$ cd /home/username/sage-x.y.z/
$ ./sage

Mac OS X 10.6.x

For Mac OS X, most of the prerequisites for compiling Sage are bundled with XCode, which is freely available from Apple’s website. Install XCode as directed by Apple’s installation instructions and download the latest Sage stable source distribution from the Sage website. If you have XCode installed on your system, then the following commands should not result in any errors:

$ which gcc
/usr/bin/gcc
$ which g++
/usr/bin/g++
$ which make
/usr/bin/make
$ which m4
/usr/bin/m4
$ which perl
/usr/bin/perl
$ which tar
/usr/bin/tar
$ which ranlib
/usr/bin/ranlib

Suppose you have downloaded the Sage source distribution and it is saved as the file named sage-x.y.z.tar. The file extension “.tar” signifies that sage-x.y.z.tar is a tar archive, also called a tar file or a tarball. To compile Sage, you need to launch a terminal window, extract the Sage source files from the tarball, and use tools that come with XCode to compile Sage. A terminal window or a console is usually launched when you run the program Terminal, which is found at

/Applications/Utilities/Terminal.app

under Mac OS X 10.4.x. For Mac OS X 10.5.x and 10.6.x, use the application finder to locate Terminal and then launch Terminal. Suppose the Sage source tarball is located at

/Users/username/sage-x.y.z.tar

where “username” is your username, the one you use to login to your Mac OS X system; replace “username” with your actual username. Say you want to compile Sage under the directory /Users/username/. From your terminal window, navigate to your home directory and extract the source tarball:

$ cd
$ tar -xf sage-x.y.z.tar

which will produce a directory called

/Users/username/sage-x.y.z/

that contains all the packages that are distributed with the Sage source distribution. You are now ready to compile Sage as contained under the latter directory. Note that you can rename the latter directory to, say, /Users/username/mysage/ as follows:

$ mv sage-x.y.z mysage

If you have a directory, say, /Users/username/bin/ and you want to extract the Sage source tarball to that directory, you can do so as follows:

$ tar -xf sage-x.y.z.tar -C /Users/username/bin

Here, it is assumed that you want to compile the Sage source as contained under

/Users/username/sage-x.y.z/

This top-level directory is usually referred to as SAGE_ROOT and is where the compiled version of Sage resides. The next step is to navigate to the latter directory and start the automated compilation process:

$ cd /Users/username/sage-x.y.z/
$ make

Usually, that is all you need to do. The rest of the compilation process is non-interactive and takes at most a few hours, depending on your system.

Note that compiling Sage is very taxing on your system’s resources, i.e. CPU, RAM, disk space, and so on. Make sure you have sufficient system resources; for example, you could close all running applications and ensure you have at least 2 GB of free disk space for Sage. Furthermore, the compilation process can take from a dozen or so minutes to a few hours, depending on your system’s hardware and how you customized the compilation process. By default, the compilation process uses one thread to compile Sage, which means that every component is compiled one after the other, i.e. serial compilation. Serial compilation of Sage is known to take up to an hour or more to complete.

On a multi-core or multi-CPU system, the compilation process can be parallelized. This means that many components of Sage can be compiled in parallel, hence reducing the time it takes for the compilation process to complete. The general steps to compile Sage in parallel are as follows. Determine the number of cores on your system and decide on how many threads you want to devote to a parallel compilation of Sage. On Mac OS X, detailed information about your system’s hardware is obtained via the command

$ system_profiler

Say your system has two cores and you want to use two threads for compiling Sage in parallel. Then the necessary setup to compile Sage with two threads is:

$ SAGE_PARALLEL_SPKG_BUILD="yes"; export SAGE_PARALLEL_SPKG_BUILD
$ MAKE="make -j2"; export MAKE
$ make

This should initiate the process of compiling Sage in parallel. If your system allows for compiling Sage with more threads, e.g. 4 or 8 threads, then change “-j2” to “-j4” or “-j8” accordingly.

Once all components of Sage are successfully compiled, the compilation process will automatically build the HTML version of the Sage standard documentation. This documentation includes a tutorial, an FAQ, a collection of thematic tutorials, a reference manual, an installation guide, among other documents. Building the HTML version of the Sage standard documentation does not require \LaTeX. However, for best results, it is recommended that you have \LaTeX installed on your system. Furthermore, \LaTeX is a prerequisite for building the PDF version of the Sage standard documentation. To manually build the HTML version of the documentation, do the following from within the SAGE_ROOT directory:

$ ./sage -docbuild all html  # or
$ ./sage -docbuild --no-pdf-links all html

To build the PDF version of the documentation, do

$ ./sage -docbuild all pdf

For further options to customize your build of the Sage standard documentation, see the output of the following command:

$ ./sage -docbuild

You can also download the documentation from

http://www.sagemath.org/help.html

or view it online at

http://www.sagemath.org/doc

To customize the compilation process to your particular needs, refer to the file

SAGE_ROOT/Makefile

Once the compilation process completes, there is no separate installation process for your newly compiled Sage. You can think of Sage as being compiled and installed under SAGE_ROOT. To begin using your freshly compiled version of Sage, navigate to SAGE_ROOT and launch Sage as follows:

$ cd /Users/username/sage-x.y.z/
$ ./sage
Advertisements

Converting from binary to integer

26 October 2010 1 comment

The following is an updated and edited version of my posts to this sage-support thread.

Problem

You have a bitstring as output by

sage.crypto.stream.blum_blum_shub

and you want to convert that bitstring to an integer. Or in general, you want to convert a bit vector to its integer representation.

Solution

Here are two ways, assuming that you want the bits in little-endian order, i.e. you read the bits from right to left in increasing order of powers of 2.

sage: version()
'Sage Version 4.5.3, Release Date: 2010-09-04'
sage: from sage.crypto.stream import blum_blum_shub
sage: b = blum_blum_shub(length=6, lbound=10**4, ubound=10**5); b
100110
sage: type(b)
<class 'sage.monoids.string_monoid_element.StringMonoidElement'>
sage: # read in little-endian order
sage: # conversion using Python's built-in int()
sage: int(str(b), base=2)
38
sage: # conversion using Sage's built-in Integer()
sage: Integer(str(b), base=2)
38

Now assume you read the bitstring as output by blum_blum_shub in big-endian order, i.e. from left to right in increasing order of powers of 2. You simply convert the bitstring to a string, reverse that string, and apply any of the above two methods.

sage: # reversing a string
sage: str(b)
'100110'
sage: str(b)[::-1]
'011001'
sage: # read in big-endian order
sage: int(str(b)[::-1], base=2)
25
sage: Integer(str(b)[::-1], base=2)
25

Or you can do as follows:

sage: b = "100110"
sage: sum(Integer(i) * (2^Integer(e)) for e, i in enumerate(b))
25
sage: sum(Integer(i) * (2^Integer(e)) for e, i in enumerate(b[::-1]))
38

Another way is to use Horner’s method. Here’s a Sage function that computes the integer representation of a bit vector read using big-endian order. A usage example is also shown.

sage: def horner(A, x0):
...       # Evaluate the polynomial P(x) at x = x_0.
...       #
...       # INPUT
...       #
...       # - A -- list of coefficients of P where A[i] is the coefficient of
...       #   x_i.
...       # - x0 -- the value x_0 at which to evaluate P(x).
...       #
...       # OUTPUT
...       #
...       # An evaluation of P(x) using Horner's method.
...       i = len(A) - 1
...       b = A[i]
...       i -= 1
...       while i >= 0:
...           b = b*x0 + A[i]
...           i -= 1
...       return b
sage: A = [1, 0, 0, 1, 1, 0]
sage: horner(A, 2)
25

As an exercise, modify the function horner to output the integer representation of a bit vector that is read using little-endian order.

Number theory & RSA public key cryptography

14 October 2010 Leave a comment

I have released version 1.1 of the Sage tutorial “Number theory and the RSA public key cryptosystem”. There is little change in terms of content. However, note that I now use the GNU Free Documentation License v1.3+ for the tutorial. Here are the relevant files you can download for your reading pleasure.

All versions of the tutorial are available from the download page on its website. For the adventurous of heart, I have also made the full \LaTeX source of the document available.

The tutorial is meant to be educational. I don’t pretend that it is complete in any way. Any suggestions and/or criticisms for improving the tutorial are more than welcome. Enjoy and happy Sage’ing.

Sage Math weekly Facebook update: 2010-09-08

8 September 2010 Leave a comment

Here is this week’s summary for the Sage Math Facebook page:

  • 335 monthly active users; 17 since last week
  • 1,752 people like this; 15 since last week
  • 13 wall posts and comments this week; no change since last week
  • 460 visits this week; 87 since last week

Typesetting Sage code listings in LaTeX

27 June 2010 Leave a comment

I needed to typeset Sage code listings in a LaTeX document. I have used the listings package before, but I want to customize with colours for keywords, comments, strings, etc. Borrowing some customization from William Stein’s ICMS 2010 paper, I think I have my customization just about right. The relevant code snippet for the preamble is:

%% For typesetting code listings                                                
\usepackage{listings}
\lstdefinelanguage{Sage}[]{Python}
{morekeywords={False,sage,True},sensitive=true}
\lstset{
  frame=none,
  showtabs=False,
  showspaces=False,
  showstringspaces=False,
  commentstyle={\ttfamily\color{dgreencolor}},
  keywordstyle={\ttfamily\color{dbluecolor}\bfseries},
  stringstyle={\ttfamily\color{dgraycolor}\bfseries},
  language=Sage,
  basicstyle={\fontsize{10pt}{10pt}\ttfamily},
  aboveskip=0.3em,
  belowskip=0.1em,
  numbers=left,
  numberstyle=\footnotesize
}
\definecolor{dblackcolor}{rgb}{0.0,0.0,0.0}
\definecolor{dbluecolor}{rgb}{0.01,0.02,0.7}
\definecolor{dgreencolor}{rgb}{0.2,0.4,0.0}
\definecolor{dgraycolor}{rgb}{0.30,0.3,0.30}
\newcommand{\dblue}{\color{dbluecolor}\bf}
\newcommand{\dred}{\color{dredcolor}\bf}
\newcommand{\dblack}{\color{dblackcolor}\bf}

And here’s an example

\begin{lstlisting}
sage: R.<x> = ZZ[]
sage: type(R.an_element())
<type 'sage.rings...Polynomial_integer_dense_flint'>
sage: R.<x,y> = ZZ[]
sage: type(R.an_element())
<type 'sage.rings...MPolynomial_libsingular'>
sage: R = PolynomialRing(ZZ, 'x', implementation='NTL')
sage: type(R.an_element())  # this is a comment
<type 'sage.rings...Polynomial_integer_dense_ntl'>
sage: def abc():
...       """
...       This should be a very long comment.
...       That should span multiple lines.
...       To illustrate what colour Sage comments look like.
...       To get a feel for the color when rendered using LaTeX.
...       """
...       return 2
\end{lstlisting}

This renders as follows:

Pushing towards 90% doctest coverage for Sage 5.0

10 June 2010 Leave a comment

This is an edited version of my post to sage-devel. One of the main goals of the upcoming Sage 5.0 release is to get doctest coverage of the Sage library up to at least 90%. As of Sage 4.4.4.alpha0, the overall weighted coverage is 82.7%. To get a sense of which modules in the Sage library need work on their coverage scores, you could use the coverage script as follows:

$ ./sage -coverage /path/to/module.py[x]

Or you could do the following to get the coverage scores of all modules, including a coverage summary:

$ ./sage -coverageall

You might be interested in knowing which modules have a certain coverage percentage, in which case you could save the output of -coverageall to a text file and then grep that file for certain coverage scores. At this repository is a script to generate various types of coverage analysis reports. You can also find the script here. The script currently supports the following reports

  1. The coverage summary of all modules.
  2. Modules with 100% coverage.
  3. Modules with zero coverage.
  4. Modules with between 1% and 9% coverage.
  5. Modules with between 10% and 19% coverage.
  6. Modules with between 20% and 29% coverage.
  7. Modules with between 30% and 39% coverage.
  8. Modules with between 40% and 49% coverage.
  9. Modules with between 50% and 59% coverage.
  10. Modules with between 60% and 69% coverage.
  11. Modules with between 70% and 79% coverage.
  12. Modules with between 80% and 89% coverage.
  13. Modules with between 90% and 99% coverage.

Each report has links to detailed reports for individual modules. To run the script, copy it to the SAGE_ROOT of a Sage source or binary installation and do

[mvngu@sage sage-4.4.4.alpha0]$ ./coverage-status.py 
Coverage report of all modules...
Summary of doctest coverage...
Modules with 0% coverage...
Modules with 100% coverage...
Coverage reports within certain ranges...
Detailed coverage report for all modules...
Format the detailed coverage reports...
Format the summary reports...
Generate index.html...

And you’re done. Here is a report generated by the script. The idea is to provide an overview of which modules need work. I’d be interested to know what other types of doctest coverage reports people would like to see. Comments, suggestions, critiques, etc. are welcome.

Hill cipher in Sage

2 June 2010 1 comment

Let’s first consider how Hill cipher encryption is commonly presented in introductory texts on cryptography or even Wikipedia. Let {M} be a {3 \times 3} invertible matrix over {\mathbf{Z}_{26}} and let {P} be a {3 \times n} matrix also over {\mathbf{Z}_{26}}. We call {M} the encryption key and {P} is referred to as the plaintext. The ciphertext {C} corresponding to {P} is given by

\displaystyle  C = MP \pmod{26}.

According to this scheme of encryption, given

\displaystyle   M = \begin{bmatrix} 6 & 24 & 1 \\ 13 & 16 & 10 \\ 20 & 17 & 15 \end{bmatrix} \ \ \ \ \ (1)

and

\displaystyle   P = \begin{bmatrix} 0 \\ 2 \\ 19 \end{bmatrix} \ \ \ \ \ (2)

then the ciphertext is

\displaystyle  C = \begin{bmatrix} 6 & 24 & 1 \\ 13 & 16 & 10 \\ 20 & 17 & 15 \end{bmatrix} \begin{bmatrix} 0 \\ 2 \\ 19 \end{bmatrix} = \begin{bmatrix} 15 \\ 14 \\ 7 \end{bmatrix}.

Hill cipher encryption in Sage works differently from that presented above. If {M} is the encryption matrix key and {P} is the plaintext matrix, then the ciphertext is the matrix {PM}. Here, {M} is still a square ({3 \times 3}) matrix and {P} is an {n \times 3} matrix where the entries are filled from left to right, top to bottom. According to this scheme of encryption, with {M} and {P} as in (1) and (2), respectively, we get

\displaystyle  C = P^T M = \begin{bmatrix} 0 & 2 & 19 \end{bmatrix} \begin{bmatrix} 6 & 24 & 1 \\ 13 & 16 & 10 \\ 20 & 17 & 15 \end{bmatrix} = \begin{bmatrix} 16 & 17 & 19 \end{bmatrix}.

Or using Sage:

sage: version()
Sage Version 4.4.1, Release Date: 2010-05-02
sage: H = HillCryptosystem(AlphabeticStrings(), 3)
sage: M = Matrix(IntegerModRing(26), [[6,24,1], [13,16,10], [20,17,15]])
sage: P = H.encoding("ACT")
sage: H.enciphering(M, P)
QRT