Empirical explorations of faster Fermat factorisation, part 5

by Stephen Hewitt | Published 12 August 2022 | Last updated 16 August 2022

Introduction

This is the fifth 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. In particular it continues the explorations of Part 3.

Part 3 included a demonstration of tuning YAFU's filtering modulus, M, for a particular number to factorise, N, where N was chosen to illustrate the advantages of tuning. This article will explore a more general way to tune the YAFU primary filter or any filter that works in a similar way, for any N.

See the Related section below for the other articles in the series.

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.

A systematic approach to tuning the filter

As described in Part 3, in its search loop, YAFU reduces the big presquare modulo 176,400 and uses an array with 176,400 elements, called skip[], indexed by this residue, to decide which values in that range are possible big presquares. The impossible ones are skipped. The table is computed for N before the main search loop. The modulus is represented in the code by the variable M and is set as follows:

uint32 M = 2 * 2 * 2 * 2 * 3 * 3 * 5 * 5 * 7 * 7;

Here we will put some arbitrary limits on the task by using only the primes from YAFU's main filter. The motivation for this is also that these small primes are the ones where the most benefit is to be gained. As the prime base becomes larger, its reduction ratio tends towards 2, and the difference between its A and B series becomes smaller. There is therefore less scope for gains from tuning.

Further limits here are to restrict these choices to a maximum number of LSDs as follows:

• 10 digits of base 2,
• 5 digits of base 3
• 3 digits of base 5
• 2 digits of base 7

These are somewhat arbitrary choices but the motivation is that there is a law of diminishing returns for increasing the number of digits, as shown by Table 3 in Part 3. For example, adding a third LSD of base 7 would increase the filter RR from 3.06 to only 3.24 while increasing the size of the table by almost a factor of 7.

The idea is to tune this filter for a particular modulus by selecting how many LSDs from each of these bases to include in the filter.

As discovered in Part 3, there are two series of filter reduction ratios for an odd prime base and three series for the even prime base. This means that depending on N

• for base 2 there are 3 possible series,
• for base 3 there is series A or B
• for base 5 there is series A or B
• for base 7 there is series A or B

So in total there are 3 x 2 x 2 x 2 = 24 different possible combinations.

At factorisation time the factorising programme will categorise N by inspecting its single least significant digit in each of these bases and determining the resulting series as in Figure 1 in Part 3. It will then accordingly select one of 24 predetermined optimum values of the filter modulus M. The task of determining those 24 optimum values is not part of factorisation but is part of the design of the implementation.

With the above restrictions, the tuned modulus for the filter can be any combination of:

• 0 to 10 digits of base 2
• 0 to 5 digits of base 3
• 0 to 3 digits of base 5
• 0 to 2 digits of base 7

So there are a total of 11 x 6 x 4 x 3 = 792 possible values for M. This means it is quite tractable to conduct an exhaustive search to find the optimum, providing we can define what optimum means.

This is a standard optimisation problem. There are two variables:

• RR, which we would like to maximise
• The number of entries in the table required to implement the filter, which we would like to minimise.

This article does not investigate the trade-off between table size and reduction ratio but simply produces a list of all the possible optimum values. This list can be called a Pareto front because it does not include any combination where another combination has both a better reduction ratio and a better or equal number of table entries.

In this case the optimisation has been done on the basis that the table size is the number of entries that pass the filter rather than M, the input range of the filter. As noted in Part 3, the YAFU implementation made the table size M.

The Appendix contains the list that results from this optimisation. It was generated by software which exhaustively tried all the viable combinations and then eliminated those that could not be an optimum. In the section below, the software is released as open source, free software under a GPL licence.

The categories of N have been named systematically as a string of four characters, with each character representing the series that N generates in a particular base. Each of the first three characters is either ‘A’ or ‘B’, representing the series in bases 7, 5 and 3 respectively. The last character is ‘1’, ‘3’ or ‘5’, representing the bit pattern associated with each of the three series in base 2.

For example “ABB1” means:

• in base 7 N generates series A
• in base 5 N generates series B
• in base 3 N generates series B
• in base 2 N has an LSB pattern of ...001, generating the series shown in Table 1 of Part 3.

GPL free software to download

The open-source software here generates the values in the table in the Appendix. It consists of the following files with the following SHA256 hashes at the following locations on this website.

3972dc9744f6499f0f9b2dbf76696f2ae7ad8af9b23dde66d6af86c9dfb36986  /download/GPLv3.txt
3cf75b0d2f736b4b9d905b44e293c907429c72021b64b9f5be23a14ff2ad2119  /download/optimise.cc
cf1691cbe1464625dbb331e80c743388eb4d0f002da28fc877c0b1e5f4f7c1df  /download/optimise.mk
0bb2e110cd620c477abe2eb5fa76d504f3c0848c8776e5a4e3ad740f0d7e9b88  /download/series.cc
bec26e3f1db46594409c8ead98d078129547783c77093e60870c57a4a0ce0117  /download/stop2.cc
ad05fa368d32fc3cc3a7521eed6cb4a6a52ba196a39ec3e928580d1d3a687b84  /download/stop2.h

The makefile optimise.mk builds two executable programmes, series and optimise. The programme series computes general information related to reduction ratio series based on the first few primes. The programme optimise generates the Pareto front, using a header file generated by series.

With further processing, the information produced by series could also be used for other purposes, including generating the three tables of reduction ratios in Part 3.

Appendix - Tabulated possible optimum values of filter modulus M for each category of N