Factoring[8 616 460 799] like 100 years ago

[Albert Chan]

Another way, we can avoid mod screening tests and later square confirmation.
see Algorithm FnPS, https://thesai.org/Downloads/Volume11No1...rithms.pdf

Let r = (x^2 - y^2 - n)/2

If r < 0, we update r, with new x = x+1
If r > 0, we update r, with new y = y+1

Δ(x^2)/2 = x+1/2

Code:

function fermat(n)      -- assumed odd n
    local x, y = ceil(sqrt(n)), 0
    local r = (x*x - n)/2
    repeat
        while r<0 do r=r+(x+0.5); x=x+1 end
        while r>0 do r=r-(y+0.5); y=y+1 end
        print(x,y,r)
    until r==0
    return x-y, x+y     -- factors
end

lua> fermat(8616460799)
92825    141      -27.5
92826    454      -319.5
92827    626      -373
92828    760      -407.5
...
92877    3111    -995.5
92878    3141    -1898
92879    3170    -529
92880    3199    0
89681   96079

Update 1:

For positive n, x-y ≥ 1 --> x ≥ y+1
This leads to slightly faster version.

Code:

function fermat(n)      -- assumed odd n
    local x, y = floor(sqrt(n)), 0
    local r = (x*x - n)/2
    while r ~= 0 do     -- invariant r <= 0
        r, x, y = r+(x-y), x+1, y+1
        while r>0 do r=r-(y+0.5); y=y+1 end
        print(x,y,r)
    end
    return x-y, x+y     -- factors
end

Update 2:

mod 4: odd^2 ≡ 1, even^2 ≡ 0

odd x, even y: n = x^2 - y^2 ≡ 1 - 0 ≡ 1 (mod 4)
even x, odd y: n = x^2 - y^2 ≡ 0 - 1 ≡ 3 (mod 4)

With parity of (x,y) maintained, z = ((x+y)*(x-y)-n)/4 is integer

Code:

function fermat(n)      -- assumed odd n
    local x = floor(sqrt(n+1))
    if n%4 == x%2*2+1 then x = x-1 end
    local y = 1 - x%2   -- x +/- y odd
    local z = ((x+y)*(x-y)-n)/4
    while z ~= 0 do     -- invariant z <= 0
        z, y = z+(x-y), y+3
        while z>0 do z=z-y; y=y+2 end
        x, y = x+2, y-1
        print(x,y,z)
    end
    return x-y, x+y     -- factors
end

lua> fermat(8616460799)
92826    455      -387
92828    761      -584
92830    975      -631
92832    1149     -194
...
92874    3021     -1841
92876    3081     -496
92878    3141     -949
92880    3199     0
89681   96079