mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2011-06-12, 19:29   #1
siegert81
 
Dec 2010

1128 Posts
Default 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
siegert81 is offline   Reply With Quote
Old 2011-06-12, 19:34   #2
siegert81
 
Dec 2010

4A16 Posts
Default

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.
siegert81 is offline   Reply With Quote
Old 2011-06-12, 19:58   #3
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

24×13×53 Posts
Default

Quote:
Originally Posted by siegert81 View Post
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
xilman is offline   Reply With Quote
Old 2011-06-12, 23:31   #4
siegert81
 
Dec 2010

2·37 Posts
Default

Alright. Do you happen to know what year he discovered this?
siegert81 is offline   Reply With Quote
Old 2011-06-13, 00:20   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by siegert81 View Post
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
R.D. Silverman is offline   Reply With Quote
Old 2011-06-13, 02:58   #6
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

25518 Posts
Default

You can read the original Lehman's paper (1974) from here: http://www.ams.org/journals/mcom/197...63-2/home.html
alpertron is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Issue with fermat factorization 0palash0 YAFU 1 2017-09-14 16:55
performance improvement with assembly bsquared Software 15 2010-09-28 19:00
Fermat factorization subforum poll ET_ Factoring 14 2010-07-10 09:40
Fermat numbers factorization ET_ Factoring 15 2008-03-12 21:24
Possible idea for improvement Kevin Software 1 2002-08-26 07:57

All times are UTC. The time now is 15:27.


Tue Nov 30 15:27:37 UTC 2021 up 130 days, 9:56, 0 users, load averages: 1.86, 1.65, 1.54

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.