mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2019-02-12, 19:05   #1
Titteris
 
Feb 2019

23 Posts
Default 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.
Titteris is offline   Reply With Quote
Old 2019-02-12, 19:50   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

586210 Posts
Default

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.)
CRGreathouse is offline   Reply With Quote
Old 2019-02-12, 21:42   #3
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

100011011000002 Posts
Default

Looks like a key.
No factors up to ~45 digits, just like Charles said.
Batalov is offline   Reply With Quote
Old 2019-02-12, 23:34   #4
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

4,211 Posts
Default

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.
VBCurtis is offline   Reply With Quote
Old 2019-02-13, 01:18   #5
Titteris
 
Feb 2019

23 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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.
Titteris is offline   Reply With Quote
Old 2019-02-13, 02:35   #6
RichD
 
RichD's Avatar
 
Sep 2008
Kansas

BA416 Posts
Default

AWS. You are probably looking at a pair of p-eighty-sixers.
RichD is offline   Reply With Quote
Old 2019-02-13, 03:21   #7
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

4,211 Posts
Default

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.
VBCurtis is offline   Reply With Quote
Old 2019-02-13, 03:34   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·3·977 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
To do a 172-digit GNFS job in 30 hours will require roughly 300 CPU cores in a cluster.
That's not bad at all!

Quote:
Originally Posted by Titteris View Post
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.)
CRGreathouse is offline   Reply With Quote
Old 2019-02-13, 13:28   #9
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

22·881 Posts
Default

If you are a student at Imperial College London, you should have started your homework earlier.
jasonp is offline   Reply With Quote
Old 2019-02-13, 16:39   #10
pinhodecarlos
 
pinhodecarlos's Avatar
 
"Carlos Pinho"
Oct 2011
Milton Keynes, UK

5×919 Posts
Default

Quote:
Originally Posted by jasonp View Post
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.
pinhodecarlos is offline   Reply With Quote
Old 2019-02-13, 18:46   #11
Titteris
 
Feb 2019

23 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
Titteris is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factoring a 160 digit RSA key swistak Factoring 6 2010-11-17 23:49
Factoring 463 digit script kiddie Miscellaneous Math 125 2010-09-03 12:45
Need a quick factoring for 21-digit number jasong Factoring 5 2007-11-19 17:49
Factoring a 617-digit number? Shakaru Factoring 2 2005-02-23 19:22
10,000,000 digit number Unregistered Software 3 2004-03-03 19:20

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

Tue Jul 7 10:47:53 UTC 2020 up 104 days, 8:20, 1 user, load averages: 2.86, 2.67, 2.49

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.