mersenneforum.org A new Fermat Factorization improvement?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2011-06-12, 19:29 #1 siegert81   Dec 2010 1128 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^2-n) if b=int(b) then if a=init then print n; " was factored in 1 step "; n; " = "; a+b; " * "; a-b else print n; " was factored in "; a-init+1; " steps "; n; " = "; a+b; " * "; a-b p=0 a=n end if next if p=1 then print n; " proven prime in "; a-init; " steps" next print 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^2-n) s=s+1 if int(b)=b then if s=1 then print m; " was factored in 1 step "; m; " = "; a+b; " * "; a-b; " / "; n/m else print m; " was factored in "; s; " steps "; m; " = "; a+b; " * "; a-b; " / "; 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
 2011-06-12, 19:34 #2 siegert81   Dec 2010 2×37 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.
2011-06-12, 19:58   #3
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

11,369 Posts

Quote:
 Originally Posted by siegert81 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.
Look up "RS Lehman factoring" in Google to find a systematic method of choosing multipliers.

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

 2011-06-12, 23:31 #4 siegert81   Dec 2010 2×37 Posts Alright. Do you happen to know what year he discovered this?
2011-06-13, 00:20   #5
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22·5·373 Posts

Quote:
 Originally Posted by siegert81 Alright. Do you happen to know what year he discovered this?
Early 80's. The technique improves difference-of-squares 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

 2011-06-13, 02:58 #6 alpertron     Aug 2002 Buenos Aires, Argentina 22·3·112 Posts You can read the original Lehman's paper (1974) from here: http://www.ams.org/journals/mcom/197...63-2/home.html

 Similar Threads Thread Thread Starter Forum Replies Last Post 0palash0 YAFU 1 2017-09-14 16:55 bsquared Software 15 2010-09-28 19:00 ET_ Factoring 14 2010-07-10 09:40 ET_ Factoring 15 2008-03-12 21:24 Kevin Software 1 2002-08-26 07:57

All times are UTC. The time now is 23:40.

Mon Jun 27 23:40:58 UTC 2022 up 74 days, 21:42, 1 user, load averages: 0.91, 1.06, 1.21

Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

โ  ยฑ โ รท ร ยท โ โ โฐ โ โ โ โ โ โค โฅ โฆ โง โจ โฉ โบ โป โผ โฝ โ โ โ โ ยฒ ยณ ยฐ
โ  โ ยฐ โ ~ โ โ โซ
โก โ โ โ โ โช โซ โโ โโ โ โ โ โ โง โจ โฉ โช โจ โ โ ๐ ๐ ๐ โฒ โณ
โ โ โ โฆ โฃ โฉ โช โ โ โ โ โ โ โ โ โ โ โ โ โ โ โค โ โ โ โต โถ โท โธ ๐
ยฌ โจ โง โ โ โ โ โ โ โ โ โ โด โต โค โฅ โข โจ โซค โฃ โฆ โฏ โฎ โฐ โฑ
โซ โฌ โญ โฎ โฏ โฐ โ โ ฮด โ โฑ โ โ
๐ข๐ผ ๐ฃ๐ฝ ๐ค๐พ ๐ฅ๐ฟ ๐ฆ๐๐ ๐ง๐ ๐จ๐ ๐ฉ๐๐ ๐ช๐ ๐ซ๐ ๐ฌ๐ ๐ญ๐ ๐ฎ๐ ๐ฏ๐ ๐ฐ๐ ๐ฑ๐ ๐ฒ๐ ๐ด๐๐ ๐ต๐ ๐ถ๐ ๐ท๐๐ ๐ธ๐ ๐น๐ ๐บ๐