20110612, 19:29  #1 
Dec 2010
2·37 Posts 
A new Fermat Factorization improvement?
I apologize if I'm wrong, but I believe I discovered a new way to speed up Fermat factorization. Basically, it's just like normal Fermat factorization, except that once enough values have been tested to know that the ratio of the largest possible factors is greater than the square root of three, the program adds a factor of three to the number being factored. I have implemented the program in "Just BASIC", and it creates the exact same results, but in far fewer steps. Below is my code for both normal Fermat factorization and the much faster version. Below the code are the results.
mainwin 140 100 for n=3000001 to 3000049 step 2 p=1 init=sqr(n) if int(init)<>init then init=int(init)+1 for a=init to (n+9)/6 b=sqr(a^2n) if b=int(b) then if a=init then print n; " was factored in 1 step "; n; " = "; a+b; " * "; ab else print n; " was factored in "; ainit+1; " steps "; n; " = "; a+b; " * "; ab p=0 a=n end if next if p=1 then print n; " proven prime in "; ainit; " steps" next for m=3000001 to 3000049 step 2 p=1 'Until N is factored, p=1. mr=0 'The maximum ratio of N/9 has not yet been exceeded. s=0 n=m [LBL] init=sqr(n) if int(init)<>init then init=int(init)+1 final=int(1.0379548493*sqr(n)) 'When a=final, it's time to add another factor of three. for a=init to final b=sqr(a^2n) s=s+1 if int(b)=b then if s=1 then print m; " was factored in 1 step "; m; " = "; a+b; " * "; ab; " / "; n/m else print m; " was factored in "; s; " steps "; m; " = "; a+b; " * "; ab; " / "; n/m p=0 a=final end if next if sqr(3)*n/m>m/9 then mr=1 'The maximum ratio has been exceeded. If p=1, then N is prime. n=n*3 if p=1 and mr=0 then goto [LBL] if p=1 and mr=1 then print m; " proven prime in "; s; " steps" next 3000001 was factored in 453 steps 3000001 = 3517 * 853 3000003 was factored in 3370 steps 3000003 = 9901 * 303 3000005 was factored in 47 steps 3000005 = 2185 * 1373 3000007 was factored in 4 steps 3000007 = 1853 * 1619 3000009 was factored in 498271 steps 3000009 = 1000003 * 3 3000011 was factored in 3638 steps 3000011 = 10453 * 287 3000013 was factored in 595 steps 3000013 = 3881 * 773 3000015 was factored in 24 steps 3000015 = 2045 * 1467 3000017 proven prime in 498272 steps 3000019 was factored in 106 steps 3000019 = 2453 * 1223 3000021 was factored in 15553 steps 3000021 = 34483 * 87 3000023 was factored in 113660 steps 3000023 = 230771 * 13 3000025 was factored in 15 steps 3000025 = 1975 * 1519 3000027 was factored in 414 steps 3000027 = 3413 * 879 3000029 proven prime in 498274 steps 3000031 was factored in 9784 steps 3000031 = 22901 * 131 3000033 was factored in 164941 steps 3000033 = 333337 * 9 3000035 was factored in 2090 steps 3000035 = 7229 * 415 3000037 was factored in 6217 steps 3000037 = 15707 * 191 3000039 was factored in 148 steps 3000039 = 2611 * 1149 3000041 was factored in 233 steps 3000041 = 2893 * 1037 3000043 was factored in 77226 steps 3000043 = 157897 * 19 3000045 was factored in 98277 steps 3000045 = 200003 * 15 3000047 proven prime in 498277 steps 3000049 was factored in 113661 steps 3000049 = 230773 * 13 3000001 was factored in 103 steps 3000001 = 3517 * 2559 / 3 3000003 was factored in 416 steps 3000003 = 9901 * 8181 / 27 3000005 was factored in 47 steps 3000005 = 2185 * 1373 / 1 3000007 was factored in 4 steps 3000007 = 1853 * 1619 / 1 3000009 was factored in 99870 steps 3000009 = 1594323 * 1000003 / 531441 3000011 was factored in 476 steps 3000011 = 10453 * 7749 / 27 3000013 was factored in 165 steps 3000013 = 3881 * 2319 / 3 3000015 was factored in 24 steps 3000015 = 2045 * 1467 / 1 3000017 proven prime in 113298 steps 3000019 was factored in 126 steps 3000019 = 3669 * 2453 / 3 3000021 was factored in 2120 steps 3000021 = 34483 * 21141 / 243 3000023 was factored in 12831 steps 3000023 = 255879 * 230771 / 19683 3000025 was factored in 15 steps 3000025 = 1975 * 1519 / 1 3000027 was factored in 90 steps 3000027 = 3413 * 2637 / 3 3000029 proven prime in 113297 steps 3000031 was factored in 1675 steps 3000031 = 31833 * 22901 / 243 3000033 was factored in 33228 steps 3000033 = 531441 * 333337 / 59049 3000035 was factored in 592 steps 3000035 = 11205 * 7229 / 27 3000037 was factored in 717 steps 3000037 = 15707 * 15471 / 81 3000039 was factored in 84 steps 3000039 = 3357 * 2681 / 3 3000041 was factored in 67 steps 3000041 = 3111 * 2893 / 3 3000043 was factored in 8162 steps 3000043 = 157897 * 124659 / 6561 3000045 was factored in 17129 steps 3000045 = 295245 * 200003 / 19683 3000047 proven prime in 113302 steps 3000049 was factored in 12833 steps 3000049 = 255879 * 230773 / 19683 
20110612, 19:34  #2 
Dec 2010
112_{8} Posts 
Unfortunately, this method of factoring isn't useful, because it's still very slow compared to the most powerful factoring methods. Still, I've never seen this approach in anything I've read about Fermat factorization. I've seen multipliers used, but not in a systematic fashion like this in which knowledge of the ratio of the largest possible factors is put to use. My hope is that I did in fact discover something new and that maybe it could be applicable to other methods, or maybe somebody will at least find it interesting. Alternatively, if this method isn't new, I would really appreciate knowing who created this method and when.

20110612, 19:58  #3  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2^{2}·37·71 Posts 
Quote:
FWIW, I went through exactly the same process of discovery as you and it wasn't until a few years later that I discovered that Lehman had got there before me. I suspect that dozens of others had also beaten me to it. Paul 

20110612, 23:31  #4 
Dec 2010
2·37 Posts 
Alright. Do you happen to know what year he discovered this?

20110613, 00:20  #5 
Nov 2003
2^{2}×5×373 Posts 
Early 80's. The technique improves differenceofsquares from
O(sqrt(N)) to O(cuberoot(N)). It (tries to) represent k*N as the difference of squares as k runs through a Farey sequence. It is useless as an actual technique because modern methods are much faster 
20110613, 02:58  #6 
Aug 2002
Buenos Aires, Argentina
3^{2}·149 Posts 
You can read the original Lehman's paper (1974) from here: http://www.ams.org/journals/mcom/197...632/home.html

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Issue with fermat factorization  0palash0  YAFU  1  20170914 16:55 
performance improvement with assembly  bsquared  Software  15  20100928 19:00 
Fermat factorization subforum poll  ET_  Factoring  14  20100710 09:40 
Fermat numbers factorization  ET_  Factoring  15  20080312 21:24 
Possible idea for improvement  Kevin  Software  1  20020826 07:57 