A new Fermat Factorization improvement?

siegert81 · 2011-06-12, 19:29

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 · 2011-06-12, 19:34

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.

xilman · 2011-06-12, 19:58

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

siegert81 · 2011-06-12, 23:31

Alright. Do you happen to know what year he discovered this?

R.D. Silverman · 2011-06-13, 00:20

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

alpertron · 2011-06-13, 02:58

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

2011-06-12, 19:29	#1
siegert81 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^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.0379548493sqr(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=n3 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

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

2011-06-12, 19:34	#2
siegert81 Dec 2010 112₈ 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, 23:31	#4
siegert81 Dec 2010 2·37 Posts	Alright. Do you happen to know what year he discovered this?

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