mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2007-09-17, 18:08   #1
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

131308 Posts
Default factoring programs

what is the best factoring program to use for different ranges of digits
say:
1-50
51 to 70
71 to 90
91 to 100
101 to 130
130 to 150
150+
it is probably simpler that this but i just want several different programs
i am particularly interested in finding a program that will factor a 160 digit number in maybe 30ish hours
i need windows binarys really unless they are easy to compile
henryzz is offline   Reply With Quote
Old 2007-09-17, 18:32   #2
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2·5·7·47 Posts
Default

Quote:
Originally Posted by henryzz View Post
...
i am particularly interested in finding a program that will factor a 160 digit number in maybe 30ish hours
Good luck with that, unless the number has special form or contains smallish factors (in which case you could try SNFS or ECM, see below).

Otherwise, see http://www.loria.fr/~zimmerma/records/rsa160

Granted, this was 4 years ago, but the algorithm used has not changed, and neither has the hardware much.

QS, (the Quadratic Sieve) is best for general numbers with number of digits N > 20 and < 100. Msieve is your best option there. There is no 'plug n' play' program for anything bigger, that I know of.

You should spend some time here: http://en.wikipedia.org/wiki/Integer_factorization
bsquared is offline   Reply With Quote
Old 2007-09-18, 06:34   #3
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

23·5·11·13 Posts
Default

from what i have heard ggnfs should be faster than QS
i know that msieve's ggnfs is supposed to be slower than its qs but that is for other reasons
is there a ggnfs program that is working as fast as the ggnfs algorithm should
the number is a factor of M1470 it have been reduced as much as it can be with ECM
would it be faster to start again on M1470 with snfs
also could u point out to me a snfs program
thanks
henryzz is offline   Reply With Quote
Old 2007-09-18, 20:51   #4
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

DC916 Posts
Default

Quote:
Originally Posted by henryzz View Post
from what i have heard ggnfs should be faster than QS
i know that msieve's ggnfs is supposed to be slower than its qs but that is for other reasons
is there a ggnfs program that is working as fast as the ggnfs algorithm should
the number is a factor of M1470 it have been reduced as much as it can be with ECM
would it be faster to start again on M1470 with snfs
also could u point out to me a snfs program
Your questions indicate that you don't know enough to attempt such a big factorization. You should only use SNFS if this 160-digit factor of M1470 is a few digits smaller than some other number that generates a good SNFS polynomial. Otherwise it's a general number and hence easier (though by no means easy) to factor via the general number field sieve.

The GGNFS package is your only practical choice for large GNFS jobs. It can handle both SNFS and GNFS problems. Go to the sourceforge page, download and install it, and try out some smaller jobs (i.e. RSA100) while you do some more background reading. If more ECM is not going to help, then nothing else will work.
jasonp is offline   Reply With Quote
Old 2007-09-18, 22:20   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2·32·569 Posts
Default

Quote:
Originally Posted by jasonp View Post
Your questions indicate that you don't know enough to attempt such a big factorization. You should only use SNFS if this 160-digit factor of M1470 ...
The questions certainly indicate insufficient knowledge.

M1470 = 2^1470-1 = (2^735+1)(2^735-1)

Each of those two factors have themselves been factored completely as part of the work of the Cunningham project. There is absolutely no point in factoring them again except, perhaps, as a learning exercise. Even in the latter case there are enough unfactored numbers of comparable difficulty and of interest to at least one other person that re-factoring M1470 is of questionable utility.


Paul
xilman is offline   Reply With Quote
Old 2007-09-19, 13:38   #6
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

2×661 Posts
Default

As I told you in another thread, you should have used my factoring applet in order to find the factorization of 2^1470 - 1:

32665 824620 457402 195434 633605 443740 257550 045736 442160 628806 611546 120572 696033 233966 359012 654595 979733 069567 388664 407206 139801 581335 691697 666580 825036 395993 873374 496107 296177 432394 402764 349675 687529 782004 971186 285327 519716 941701 567289 776745 614889 041189 723697 073526 161103 983641 763554 076064 188135 517654 549958 476754 101195 985309 251236 506489 109949 465205 140536 348059 366804 345787 541934 500497 452294 145254 373550 578070 204266 401827 739721 665519 024733 159423 = 3 ^ 2 x 7 ^ 3 x 11 x 31 x 43 x 71 x 127 x 151 x 211 x 281 x 331 x 337 x 491 x 1471 x 5419 x 5881 x 29191 x 41161 x 86171 x 106681 x 122921 x 152041 x 664441 x 748819 x 1 564921 x 4 163041 x 20147 473081 x 2 340389 488711 x 4 363953 127297 x 4 432676 798593 x 27653 710336 343911 x 15 162868 758218 274451 x 26 032885 845392 093851 x 2 741672 362528 725535 068727 x 50647 282035 796125 885000 330641 x 252359 902034 571016 856214 298851 708529 738525 821631 x 631 430922 992211 190033 830999 202698 905758 039480 236241 x 23 618256 244840 618857 212522 155851 714598 259422 753496 906641 681177 748710 460515 038403 366198 473773 770441
alpertron is offline   Reply With Quote
Old 2007-09-19, 13:47   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by henryzz View Post
from what i have heard ggnfs should be faster than QS
i know that msieve's ggnfs is supposed to be slower than its qs but that is for other reasons
is there a ggnfs program that is working as fast as the ggnfs algorithm should
the number is a factor of M1470 it have been reduced as much as it can be with ECM
would it be faster to start again on M1470 with snfs
also could u point out to me a snfs program
thanks
M1470 has already been fully factored.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Links to factoring programs smh Factoring 71 2019-02-21 22:33
Links to Factoring Programs rogue Factoring 32 2009-09-17 11:40
Would like to learn the math behind the factoring programs. jasong Factoring 18 2006-06-11 01:37
looking for Fermat factoring programs ixfd64 Factoring 1 2005-09-08 12:13
any good GNFS factoring programs? ixfd64 Factoring 1 2004-04-27 09:41

All times are UTC. The time now is 20:50.

Fri Sep 18 20:50:28 UTC 2020 up 8 days, 18:01, 1 user, load averages: 1.75, 1.73, 1.74

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