Factoring[8 616 460 799] like 100 years ago
|
09-16-2022, 04:48 PM
(This post was last modified: 09-23-2022 01:41 AM by Albert Chan.)
Post: #17
|
|||
|
|||
RE: Factoring[8 616 460 799] like 100 years ago
(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. |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: 1 Guest(s)