1
$\begingroup$

Look at wikipedia link: http://en.wikipedia.org/wiki/Fermat%27s_factorization_method and look for basic method that is written there, where you have while loop.

For every loop you have to square number and if it is not right you add 1 and go to the next number and square it again.

We all know that Differrence between square numbers is sum of consecutive odd numbers.

example: 1 + 3 + 5 = 9 or 1 + 3 + 5 + 7 = 16 and so on

So why dont we memorize the number we just got squared/ckecked and then just add another next odd integer for next square number? Is that less compute-time consuming?

And what about that improvement? And some other improvements on the Fermat factorization method : Let us not use it for even numbers (that is anyway) and for numbers with digit sum that equals 3,6,9.

In therms of digit sum of squares there are only for posibilities 1,4,7,9

I also found out that in case of equation of the diference of squares there is always digit sum number 9 involved!

So if I shorten story up there are only next squared digit sum cases possible for difference of squares equation: 1 = 1 - 9 ; 2 = 9 - 7 ; 4 = 4 - 9 ; 5 = 9 - 4 ; 7 = 7 - 9 ; 8 = 9 - 1 ;

Example: 341 => digit sum is 8, so the only possible way is 8 = 9 - 1. As you know digit sum 9 is 21 squared and digit sum 1 represents 10 squared. So we know how does bigger squared number look like and how does the smaller, so we can jump only to those squared numbers which are needed.

  • 0
    Fermat's method is only efficient for factors of about equal size, no matter how you try to improve its steps. A better method, but in the spirit of Fermat, is a deterministic method by Lehman. http://goo.gl/pT4fJ2012-06-20

1 Answers 1

1

Yes. It is improvement. But I ask myself why Fermat sieve method is not used in similar fashion?

341 mod 10 = 1 , perfect squares for mod 10 are 0,1,4,5,6,9 So number 341 is a diferrence of two squares, where they give us result of last Digit = 1 . So 341 is perfect square of number with last digit 1 minus perfect square with last digit 0, or perfect square number with last 6 minus perfect square with last Digit 5. For 341 the result is 441-100

So with bigger numbers we can we can reduce possibilities significantly with different modes and also with digit sum...

Next paper should be mentioned in wikipedia in for Fermat factorisation method . http://arxiv.org/abs/math/0202269

  • 1
    Well I try to involve someone in a more positive manner. Actively. You are not one of them. And secondly i think that this gives some new informations to others. At least they read it. And for that Thank you.2012-02-09