View Single Post
Old 2017-02-27, 23:12   #7
science_man_88's Avatar
"Forget I exist"
Jul 2009

203008 Posts

Originally Posted by mahbel View Post
the problem with Fermat factoring method is that it is just one of what I call sequential methods. You are looking for a square to add to your number to get another square. And because we have no way of knowing where to start, we end up having to try one square after another another. So they can't be made efficient. Under certain circumstances, it can worse than using simple division. Try using Fermat method for say 13*643 and see how fast it converges to the solution. Then try division by primes below sqrt(13*643).
though I don't use it I would argue you can use the fact that the squares are certain remainders on division by 8 to help 13*643 = 7 mod ( as it's called) 8 squares are 0,1,4 mod 8 so the square you add has to be either 1,2,5 mod 8 only one of which can be a square number so you are looking for a square that is 1 mod 8 the squares go:

0,1,4,1,0,1,4,1,0 so you know you are looking for an odd square and the sum will have to be an even square.
science_man_88 is offline   Reply With Quote