20190212, 19:05  #1 
Feb 2019
23 Posts 
Factoring a 172digit 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 
20190212, 19:50  #2 
Aug 2006
3×1,993 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.) 
20190212, 21:42  #3 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
17·563 Posts 
Looks like a key.
No factors up to ~45 digits, just like Charles said. 
20190212, 23:34  #4 
"Curtis"
Feb 2005
Riverside, CA
3·1,667 Posts 
CADONFS 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 172digit 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 4core desktop to factor the number. 
20190213, 01:18  #5  
Feb 2019
23 Posts 
Quote:


20190213, 02:35  #6 
Sep 2008
Kansas
2^{3}·431 Posts 
AWS. You are probably looking at a pair of peightysixers.

20190213, 03:21  #7 
"Curtis"
Feb 2005
Riverside, CA
1389_{16} 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 infinibandconnected 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 AWSsize 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 1418 core machine in maybe 2024 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 6core i7 desktop has factored a C156 with GNFS in 170 hours = 1000 corehours. GNFS effort doubles every 55.5 digits, so a C172 is 3 doublings harder than a C156: 1000 corehours x 8 = 8000 corehours = 2000 quadcorehours = 80 to 85 quadcoredays, 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. 
20190213, 03:34  #8  
Aug 2006
3×1,993 Posts 
Quote:
Quote:
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.) 

20190213, 13:28  #9 
Tribal Bullet
Oct 2004
3×1,181 Posts 
If you are a student at Imperial College London, you should have started your homework earlier.

20190213, 16:39  #10 
"Carlos Pinho"
Oct 2011
Milton Keynes, UK
3·1,657 Posts 

20190213, 18:46  #11  
Feb 2019
23 Posts 
Quote:
Last fiddled with by Titteris on 20190213 at 18:47 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Factoring a 160 digit RSA key  swistak  Factoring  6  20101117 23:49 
Factoring 463 digit  script kiddie  Miscellaneous Math  125  20100903 12:45 
Need a quick factoring for 21digit number  jasong  Factoring  5  20071119 17:49 
Factoring a 617digit number?  Shakaru  Factoring  2  20050223 19:22 
10,000,000 digit number  Unregistered  Software  3  20040303 19:20 