Empirical explorations of faster Fermat factorisation, part 7

by Stephen Hewitt | Published 2 September 2022 | Last updated 4 September 2022

Introduction

This is the seventh in a series of technical articles presenting original work towards an open-source, free software implementation of the Fermat factorisation algorithm optimised for speed.

This article uses concepts and terminology introduced in the previous articles and is not intended to be understood without them. See the Related section below for the other articles in the series.

Part 3 reported a fourfold increase in speed after tuning the YAFU filter for a particular chosen value of number to factor. This article reports an empirical test of speed with tuning, across the full range of numbers to factor, representative of a random distribution.

Terminology

big square

Successful factorisation finds b² - s² = N where b² is called here the big square. See Part 1.

GPL

GNU general public license

LSB

least significant bit

LSD

least significant digit

M

The input range, or modulus, of the filter. In effect, what happens during filtering is that a big presquare candidate is reduced mod M and the residue tested in the filter to discover whether it is viable. This is named after the variable in the YAFU code. See Part 3.

N

The number to factorise, of the form pq where p and q are large primes; possibly the modulus of an RSA public key.

presquare

The root x of any square x² will be called the presquare.

RR

reduction ratio, defined in Part 3.

RSA

Rivest Shamir Adleman

small square

Successful factorisation finds b² - s² = N where s² is called here the small square. See Part 1.

YAFU

Yet Another Factorisation Utility. See Part 2.

Experiment

For each of the 24 categories of N a design value of filter modulus M was selected from the Appendix in Part 5. These values are shown in Table 1.

Two modified versions of the YAFU Fermat factorisation function, zFermat(), were created. One was with a compact filter table of size M/RR (as discussed in Part 3 and in Part 5) and one with the original YAFU filter table of size M.

The modified compact table version allows M to be changed at run time, so that it can be tuned.

The benchmark software factorises each test number in three different ways.

1. It uses the original YAFU zFermat() filter table size of M with the fixed YAFU M value of 176400.
2. For the tuned filter it categorises each number to be factorised into one of the 24 categories and uses the value of M shown in Table 1 for that category.
3. It uses the same version of zFermat() with a compact filter table, but with the original YAFU fixed value of M = 176400.

Results

The mean in Table 2 has been adjusted to reflect the fact that all categories of N occur with equal probability except for categories ending in '3' which occur twice as often. (This is because the '3' ending reflects either the LSB pattern 011 or 111 in N, whereas '5' reflects the bit pattern 101 only and '1' reflects the bit pattern 001 only, as described in Part 3)

Discussion

The results in Table 2 show that the version of the factorisation function modified to use a compact filter table (without tuning) factored the number in about 65-70% of the time of the version using the original sparse filter table, for every value of N.

As expected, the tuned version was faster than the untuned version, and multiplication in speed correlated with the calculated improvement in filter RR due to tuning. The last two columns of Table 2 illustrate this. However the correlation is not exact, and it is noticeable that the empirical improvement in almost all cases is only around 85% of the improvement in RR. For example for the category AAA1, the improvement in RR from tuning is a factor of 12 but the measured time reduction is only a factor of 10. For the category BBB5, the improvement in RR is 2 but the measured improvement is 1.7 Exceptions to this are the categories ending '3' where the RR is 1.0 or 2.2.

GPL free software to download

The open-source software here produces benchmark timings like the ones in Table 2.

It consists of the following files with the following SHA256 hashes at the following locations on this website.

3972dc9744f6499f0f9b2dbf76696f2ae7ad8af9b23dde66d6af86c9dfb36986  /download/GPLv3.txt
2af8c3410899a696f6d3945993f5a0b2e227d4d41191912e1d157e18209d175f  /download/benchmark.cc
a68feaaaea73d4d9f6574de8ac61541dc49599d73f0e1591af52ab39e6b41c03  /download/benchmark.mk
6d06e857886ab6290412af17dcf294de54908e8c4bf02f5c3c96df74fdf1b388  /download/check.c
2daaa50eff3d0953a912c1b1ae8a089886264a37aea334eb4986108011601cbc  /download/generate.cc
8037db0a4b7fc32e9e96741950e0d154e34c8580c680c22571fb1503522f4df8  /download/optima.gh
0ac100ee43662d69f9695728a5a9cd79332d14bcfb752b80cb99c428deb02365  /download/timings.cc
e855144097e59ba7036e18f0ceecc08b937b085e8d14266fc51ed2bb42be6f1b  /download/timings.h
b9f239a4e595122a27d0c715cc05136ea46f493146c996be33b2a41ad1d0003e  /download/zf.h
ed0fd4971718c76b1ff7fe8ee641ddb4d674d4577f649e4afed103852af08b42  /download/zf1.c
2de98117dbb6ea4066facf91d111a05431f045e7ec5dcf9113ecf1b5bc2deda9  /download/zf2.c

The files zf1.c and zf2.c each contain a modified version of the zFermat() factorisation function from YAFU. This code generated the times recorded in the benchmarks in Table 2.

This build also requires a generated header file lsd2series.gh which is the output from the programme lsd2.cc, released in Part 6.