RSA factorization
in the real world

Basic subroutines:
Product tree
Remainder tree
Weak primes:
Batch gcd
Small primes:
Batch trial division
Small keys:


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
     sage: s2 == s

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: 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

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