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.

$\endgroup$
2
  • $\begingroup$ Well this is similar to the Fermat sieve method but with slight difference because it looks for digit sums not remainders and we know something about both numbers that are differentiated by the number N,whos factors are we looking for trans4mind.com/personal_development/mathematics/numberTheory/… $\endgroup$
    – Bojan Vasiljević
    Feb 9, 2012 at 1:31
  • $\begingroup$ 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. goo.gl/pT4fJ $\endgroup$
    – WimC
    Jun 20, 2012 at 5:02

1 Answer 1

Reset to default
1
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ So we have here a question asked by Bojan Vasiljević, with a comment by Bojan Vasiljević, and an answer by Bojan Vasiljević. If you want to talk to yourself, why not do it somewhere more private? $\endgroup$
    – David Loeffler
    Feb 9, 2012 at 10:57
  • 1
    $\begingroup$ 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. $\endgroup$
    – Bojan Vasiljević
    Feb 9, 2012 at 11:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .