mersenneforum.org Factoring a 172-digit number.
 Register FAQ Search Today's Posts Mark Forums Read

 2019-02-12, 19:05 #1 Titteris   Feb 2019 23 Posts Factoring a 172-digit number. Hi, I need to a factorize a 172 digit number, but I have close to none programming experience. I'm fairly certain I'm going to need to use General Number Field Sieve, but everything seems very complicated. I want to do it on python and I've heard of factmsieve.py. I know there was a guide made but it is missing now. Also, I'd need to run the code for 30 hrs tops. So I guess my question is if it is even doable and how do I approach this problem in beginner's eyes? (From what I've heard the number is pretty difficult to factor). P.S. I saw a guide on the forum, but it seems pretty outdated, that's why I'm writing here. _______________________________ Code: 4575134632231276322296167719963713360020693916717864302242897684603372926658749007190672847530044445893159494009270273633439851578271094033177607285358363041896722563514969 Any help would be greatly appreciated. Thanks.
 2019-02-12, 19:50 #2 CRGreathouse     Aug 2006 32×5×7×19 Posts It's 172 digits, 571 bits. No obvious SNFS special forms. No tiny factors for ECM to latch onto. With sufficient effort GNFS could crack this number. More experienced members could give an idea of the effort required. For a general ballpark, think a small cluster of computers computing for weeks or months. (More than you could do on one machine, but not something you'd need a distributed project for.)
 2019-02-12, 21:42 #3 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2·3·1,571 Posts Looks like a key. No factors up to ~45 digits, just like Charles said.
 2019-02-12, 23:34 #4 VBCurtis     "Curtis" Feb 2005 Riverside, CA 10010101010112 Posts CADO-NFS can do the job, and takes no programming; all you need to be able to do is install the package on a linux box. Google it, the software package is free. To do a 172-digit GNFS job in 30 hours will require roughly 300 CPU cores in a cluster. Good luck! You're looking at 3 months (give or take a couple weeks) of 24/7 computation on a typical modern 4-core desktop to factor the number.
2019-02-13, 01:18   #5
Titteris

Feb 2019

23 Posts

Quote:
 Originally Posted by VBCurtis CADO-NFS can do the job, and takes no programming; all you need to be able to do is install the package on a linux box. Google it, the software package is free. To do a 172-digit GNFS job in 30 hours will require roughly 300 CPU cores in a cluster. Good luck! You're looking at 3 months (give or take a couple weeks) of 24/7 computation on a typical modern 4-core desktop to factor the number.
Is there any chance you know of somebody that would be able to provide such services? I’m talking about the 300 CPU cores and doing it on a linux boxes. I appreciate your help, thanks a lot.

 2019-02-13, 02:35 #6 RichD     Sep 2008 Kansas 1100111111012 Posts AWS. You are probably looking at a pair of p-eighty-sixers.
 2019-02-13, 03:21 #7 VBCurtis     "Curtis" Feb 2005 Riverside, CA 34·59 Posts The matrix must be solved on a single machine if using the standard CADO install (I don't know how it could be split onto infiniband-connected clusters, though the documentation indicates it is possible). A C172 could produce a matrix of size ~10M x 10M, which can be solved on a single AWS-size machine (say, 16 cores) in 24 hours or less. If you could clone a linux image onto a *lot* of AWS instances, you could in principle perform the sieving step on ~1200 cores in 7 hours, followed by the matrix on a single 14-18 core machine in maybe 20-24 hours. I don't do cloud computing, so I've no advice on actually doing so. CADO is designed to have one machine as the server, with any client machines connecting over IP to ask for work and submit relations data. It took me no more than one evening to figure out how to tell clients to fetch and submit work, but I never figured out the SSH magic to have the server command clients on its own. Here's how I got my time estimates: My 6-core i7 desktop has factored a C156 with GNFS in 170 hours = 1000 core-hours. GNFS effort doubles every 5-5.5 digits, so a C172 is 3 doublings harder than a C156: 1000 core-hours x 8 = 8000 core-hours = 2000 quad-core-hours = 80 to 85 quad-core-days, or 30 hours for 266 cores. Only the matrix step is restricted to a single machine; the rest can be split over as many machines as you have access to and patience for.
2019-02-13, 03:34   #8
CRGreathouse

Aug 2006

176116 Posts

Quote:
 Originally Posted by VBCurtis To do a 172-digit GNFS job in 30 hours will require roughly 300 CPU cores in a cluster.

Quote:
 Originally Posted by Titteris Is there any chance you know of somebody that would be able to provide such services? I’m talking about the 300 CPU cores and doing it on a linux boxes. I appreciate your help, thanks a lot.
There are a number of people here with the expertise, but I don't know if they're available for hire. But honestly, their time might well be more expensive than the time for the machines themselves (say, $200 on AWS). There's a Factoring as a Service project which might help, but I don't know how practical it is at the moment. (I'd love to hear.)  2019-02-13, 13:28 #9 jasonp Tribal Bullet Oct 2004 33×131 Posts If you are a student at Imperial College London, you should have started your homework earlier. 2019-02-13, 16:39 #10 pinhodecarlos "Carlos Pinho" Oct 2011 Milton Keynes, UK 2×23×107 Posts Quote:  Originally Posted by jasonp If you are a student at Imperial College London, you should have started your homework earlier. And if so I can meet him there. I’m in Waterloo but can easily commute. 2019-02-13, 18:46 #11 Titteris Feb 2019 2310 Posts Quote:  Originally Posted by CRGreathouse That's not bad at all! There are a number of people here with the expertise, but I don't know if they're available for hire. But honestly, their time might well be more expensive than the time for the machines themselves (say,$200 on AWS). There's a Factoring as a Service project which might help, but I don't know how practical it is at the moment. (I'd love to hear.)
I tried doing the factoring as a service thingy but it turns out Windows isn't supported. Are there any alternatives for this? Why is linux better in this case?

Last fiddled with by Titteris on 2019-02-13 at 18:47

 Similar Threads Thread Thread Starter Forum Replies Last Post swistak Factoring 6 2010-11-17 23:49 script kiddie Miscellaneous Math 125 2010-09-03 12:45 jasong Factoring 5 2007-11-19 17:49 Shakaru Factoring 2 2005-02-23 19:22 Unregistered Software 3 2004-03-03 19:20

All times are UTC. The time now is 19:10.

Tue May 11 19:10:00 UTC 2021 up 33 days, 13:50, 1 user, load averages: 2.39, 2.19, 2.18