Empirical explorations of faster Fermat factorisation, part 4

by | Published

Introduction

This is the fourth 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. It reports a new empirical discovery and a consequent conjecture about reduction ratios, which were defined in Part 3 and it is written to be understood only in conjunction with Part 3. It presents open source, GPL software for download, which demonstrates the conjecture.

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

The new discovery: The reduction ratio at first digit is a simple expression

Part 3 reported that there are two series of filter reduction ratios for each odd prime base used in a filter. These were designated series ‘A’ and series ‘B’. Table 2 in Part 3 presented values of RR as (approximate) floating point numbers for the first few prime bases.

These were calculated by iterating exhaustively through all possible big presquare (b) LSD patterns and keeping a count of each one that represented a stop pattern, defined as value that causes a pattern of LSDs in the small square (s2) candidate that cannot possibly be LSDs of a square.

The new empirical observation is that the RR for filter using a single LSD (k = 1) is given by a simple expression and iteration is not necessary to calculate it. The observed number of stop patterns in odd prime base p is:

stop patterns (A series) = (p - 1)/2

stop patterns (B series) = (p + 1)/2

Now by definition for a filter using a single LSD:

RR = p/(p - stop patterns)

Therefore the reduction ratios are given by the following:

RR (A series) = 2p/(p + 1)

RR (B series) = 2p/(p - 1)

These expressions are consistent with the empirical observation of Part 3 “The larger the base, the closer to 2 is the reduction ratio of both series at first digit”.

This article does not attempt a derivation or proof of this expression, so here it remains a conjecture that this holds for all odd primes p. It has been proven by exhaustion for the first odd primes up to 127 by the free software available to download in the next section.

Note that this discovery is of more theoretical interest than practical consequence since iterating over a single digit is trivial.

Another empirical observation, which could already be noticed in Figure 1 of Part 3, is that an LSD value of 1 in N results in series ‘A’, for all primes so far tested.

GPL free software

The C++ software available here prints the mapping that was presented in Figure 1 of Part 3, which shows how the LSD of N decides series A or series B for the reduction ratios. It has been extended to print more primes, up to 127 (and could easily be extended further).

To demonstrate the new conjecture here, it calculates the RR by iterating over all possible big presquare LSD patterns and compares the result with the values for RR produced by the expressions above. If there were a discrepancy it would halt with an error message including “conjecture failure”, followed by more details.

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

c16abd8b178887ba4c46f7fd85fd089ca8e9844015fc73aab029cff195ce9b7c  /download/lsd.cc
15c711dd1eaafaa7e571201849d1b958c77ad55f74ed773bd90859aef952de9f  /download/stop.cc
78b4082a811816f3c3c75ccca51cc7b69ff381fe9065489c9706257c45261319  /download/stop.h

Terminology

big square
Successful factorisation finds b2 - s2 = N where b2 is called here the big square. See Part 1.
GPL
GNU GENERAL PUBLIC LICENSE
LSB
least significant bit
LSD
least significant digit
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 x2 will be called the presquare.
RR
reduction ratio, defined in Part 3.
small square
Successful factorisation finds b2 - s2 = N where s2 is called here the small square. See Part 1.

Related