Factoring[8 616 460 799] like 100 years ago

[Albert Chan]

(09-06-2022 04:51 PM)Thomas Puettmann Wrote:  The machine stops if the last digits of \( 8 616 460 799 + n^2 \) is that of a square in all the number systems above. Then the laser beam can pass without obstruction to the photo transistor. You then have to check manually whether \( 8 616 460 799 + n^2 \) actually is a square integer. If it is not, you let the machine continue. If yes, you factor the number as shown in the video.

N = x^2 - y^2

Why test for isSqr(N+y^2), instead of more efficient isSqr(x^2-N) ?

N = 8616460799 = 92880^2 - 3199^2

min(y) = 0
y to be tested = 0 to 3199, or 3200 cases

min(x) = ceil(sqrt(N)) = 92825
x to be tested = 92825 to 92880, or 56 cases

We could limit tested x further ...

mod3: N ≡ -1 = 0 - 1 --> x ≡ 0 (mod 3)
mod8: N ≡ -1 = 0 - 1 --> x ≡ 0 (mod 4)      // odd^2 = (4k±1)^2 ≡ 1 (mod 8)

--> x = 92832 to 92880 step 12, or 5 cases.