Factoring[8 616 460 799] like 100 years ago

[Albert Chan]

(09-05-2022 07:24 PM)C.Ret Wrote:  Why this curious series of numbers { 25 36 21 23 22 29 23 31 }
Why aren't they all primes?

n = (x+y) * (x-y)
x^2 = n + y^2

Modulo b, both x^2 and y^2 has same list of possibilities.
We want base b, such that x^2 % b has very few candidates, for better screening power.

>>> modsqr = lambda b: set(i*i%b for i in range(b))
>>> modsqr(11)
set([0, 1, 3, 4, 5, 9])
>>> modsqr(12)
set([0, 1, 4, 9])

>>> for i in range(20,41): print i, len(modsqr(i))/i
...
20 0.3
21 0.380952380952
22 0.545454545455
23 0.521739130435
24 0.25
25 0.44
26 0.538461538462
27 0.407407407407
28 0.285714285714
29 0.51724137931
30 0.4
31 0.516129032258
32 0.21875
33 0.363636363636
34 0.529411764706
35 0.342857142857
36 0.222222222222
37 0.513513513514
38 0.526315789474
39 0.358974358974
40 0.225

Prime base has bad screening power.
Perhaps we should have pick base with high screening power? (low ratios)
(with this metric, base 22 is bad, pow-of-2, say 32, is good)