ulimyhmpqs

ulimyhmpqs is an implementation of the Hypercube Multiple Polynomial Quadratic Sieve (HMPQS), an algorithm for the factorisation of large (up to about 110 digits, where the Number Field Sieve (NFS) algorithms become more efficient) integers. It was written by Uli Meyer and has been tested on the following implementations so far:

Macintosh Common Lisp Version 4.3.5 (OS9.2)
CMUCL 19c (MacOS 10.4)
clisp 2.41 (Windows XP)
LispWorks (Windows XP)

From the description of the algorithm: The intention of the author was not to present a record-breaking implementation of this well-known algorithm, but

to understand himself what science of the last decades has in stock, to reverse the very simple and fundamental operation of multiplying two integers, in spite of having only basic knowledge in number theory
to have a ready-to-go, easy-to-use and still powerful LISP module for factoring large numbers.

The run time needed to factor a hard (i.e. two large prime factor) integer n can be read off the following plot. To use it, download the source code (a single Lisp file), compile and load it. To factor the seventh Fermat number F₇ = 2¹²⁸+1, evaluate

  (setf *default-float-format* 'double-float) ; clisp produces floating overflows
                                              ; for (> n 1e40) without this.

  (load "ulimyhmpqs"); assumes that (compile-file "ulimyhmpqs.lisp") has
                     ; been done once.
  (factors (+ (expt 2 128) 1)
           :report t) ; enables the report shown below

which produces the following report and the two factors (59649589127497217 5704689200685129054721).

----------------- 340282366920938463463374607431768211457 ----------------
log10(N) (M  24235) (h(x*)) (a_ideal) (a_primes) (  4950/619  squares) thr
 38.53      4.38     23.50    15.03   1.83  3.45   3.84   6.90  d +0.0  16
fctrbase (B   1156) {-1 2 11 13 17 19 ; 31 37 59 61 67 71 89 97 ... 20731}
cub a-error #h(x)  equ/min new/min  #equ  #due done%    est/min      0.009
1   .25329%    64  4702.04 4702.04   229     1  19.8      0.254      0.057
2   .74957%   128  4848.89 4996.56   471     6  40.7      0.243      0.106
3   .47386%   192   4989.7 5269.02   729    13  63.1      0.236      0.155
4   .88492%   256  4696.65 4028.18   987    22  85.4      0.261      0.219
5   0.9952%   286  4209.07 2035.99  1083    23  93.7      0.302      0.266
#h(x)*2M/equation  non/triv   #slp   452  due% saved%
1.386d+7  1.28d+4   1 + 5    0.69% 65536   2.1   6.3                 16.0s
--------------- (59649589127497217 5704689200685129054721) ---------------

I hope those of you who like Mathematics will enjoy this program. A detailed descrption of the algorithm is available both in english and (slightly older) in german.

This page is linked from: Roland Kaufmann

CLiki pages can be edited by anyone at any time. Imagine a fearsomely comprehensive disclaimer of liability. Now fear, comprehensively