# FactHacks

RSA factorization
in the real world

 Introduction Sage
 Basic subroutines: Euclid Product tree Remainder tree
 Weak primes: Batch gcd Fermat Lattice
 Small primes: Batch trial division rho p-1 ECM
 Small keys: Smooth QS NFS

## Sage

The FactHacks code snippets use Sage, a mathematical front-end to Python. The big advantage of Sage over Python is that it has many built-in math libraries.

The algorithms we discuss are built from simple arithmetic operations such as addition, subtraction, multiplication, division, etc. Our goal in each code snippet is for the reader to understand the sequence of arithmetic operations in the algorithm. There are many ways to speed up the code without changing the sequence of operations: Python and Sage often use unnecessarily slow methods to perform these arithmetic operations, and often impose severe overheads beyond the arithmetic operations. The simplest way to save time, without changing programming language, is to use Sage's Integer type, which generally offers much faster arithmetic operations than Python's long type:

```     sage: # laptop performance
sage: x = randrange(2**1000000)
sage: y = randrange(2**500000)
sage: time r = x % y
Time: CPU 9.15 s, Wall: 9.21 s
sage: time s = x * y
Time: CPU 1.06 s, Wall: 1.06 s
sage: x2 = Integer(x)
sage: y2 = Integer(y)
sage: time r2 = x2 % y2
Time: CPU 0.05 s, Wall: 0.05 s
sage: time s2 = x2 * y2
Time: CPU 0.02 s, Wall: 0.02 s
sage: r2 == r
True
sage: s2 == s
True
```

## Changes in syntax between Sage and Python

If you use Python then you won't have any serious trouble reading or writing Sage code, but there are a few important syntactic differences to keep in mind:
• ^ is exponentiation in Sage but xor in Python. For example, 2^3 is 8 in Sage and 1 in Python.
• / is exact division in Sage (producing an integer or rational) and in Python 3 (producing a floating-point number), but it is truncated division in Python 2. Python 2, Python 3, and Sage all support // for truncated division.

## Using Sage

There are three different ways that you can try Sage:
```     aptitude install \
build-essential m4 gfortran imagemagick texlive dvipng libssl-dev dpkg-dev
wget http://mirrors.xmission.com/sage/src/sage-5.5.tar
tar -xf sage-5.5.tar
cd sage-5.5
env MAKE="make -j4" make
```
This takes a while so you should start now (and make sure your laptop has long-term power).
• Use one of the online Sage notebooks.
Command-line usage example:
```     \$ sage
----------------------------------------------------------------------
| Sage Version 5.5, Release Date: 2012-12-22                         |
| Type "notebook()" for the browser-based notebook interface.        |
| Type "help()" for help.                                            |
----------------------------------------------------------------------
sage: 2+2
4
sage:
```

Version: This is version 2012.12.27 of the sage.html web page.