This post will look at the time required to factor n − 1 each of the following prime numbers in Python (SymPy) and Mathematica. The next post will explain why I wanted to factor these numbers.

p = 2²⁵⁴ + 4707489544292117082687961190295928833
q = 2²⁵⁴ + 4707489545178046908921067385359695873
r = 2²⁵⁴ + 45560315531419706090280762371685220353
s = 2²⁵⁴ + 45560315531506369815346746415080538113

Here are the timing results.

    |   |   Python | Mathematica |
    |---+----------+-------------|
    | p |    0.913 |       0.616 |
    | q |    0.003 |       0.002 |
    | r |  582.107 |      14.915 |
    | s | 1065.925 |      20.763 |

This is hardly a carefully designed benchmark, but it’s enough to suggest Mathematica can be a couple orders of magnitude faster than Python.

Here are the factorizations.

p − 1 = 2³⁴ × 3 × 4322432633228119 × 129942003317277863333406104563609448670518081918257
q − 1 = 2³³ × 3 × 5179 × 216901160674121772178243990852639108850176422522235334586122689
r − 1 = 2³² × 3² × 463 × 539204044132271846773 × 8999194758858563409123804352480028797519453
s − 1 = 2³² × 3 × 1709 × 2485 × 1690502597179744445941507 × 10427374428728808478656897599072717

The post Time to factor big integers Python and Mathematica first appeared on John D. Cook.