Factoring[8 616 460 799] like 100 years ago

[Thomas Puettmann]

(09-16-2022 04:48 PM)Albert Chan Wrote:  Why test for isSqr(N+y^2), instead of more efficient isSqr(x^2-N) ?

The reason is to go to automatization as straight as possible.

U. Meyer, who built the LEGO machine, did the same, and I guess for the same reason.

The machine requires a lot of explanation and configuration already. I wanted to avoid any further difficulties.

In order to follow the Fermat method literally, you need to compute
s = ceil(sqrt(N)) = min x (by hand, if you want to be authentic). The number x starting from s does not fit into the counter. The counter hence wouldn't display x nor y but the number of the current step in the Fermat method. The configuration table for a chain with k links would be indexed by (s+n)^2 - N mod k instead of N + n^2 mod k. The "-" looks innocent but from my experience, in practice, it is not.

From what I remember the Lehmers and Carissans never used the Fermat method literally but developed an individual sieving strategy for every single integer they were interested in. This way they could factorize integers of a different magnitude. But, in my opinion, it wouldn't make sense to explain this to a general audience.

Actually, I guess the Lehmers would not even have thought to factorize the Jevons' number on a machine, since they could do it in say 20 min by hand (see the paper of Solomon Golomb in Thomas Klemm's link above).

So, yes, you are absoultely right: I could shorten the runtime significantly, but at the cost of a slightly more difficult configuration and of a less straightforward explanation.