mersenneforum.org who can factor this 128 digits number?
 Register FAQ Search Today's Posts Mark Forums Read

 2010-05-25, 12:12 #1 aaa120   Oct 2008 24 Posts who can factor this 128 digits number? my friend let me to factor it ,but it is difficult for me to factor it, who can help me to factor it ? 67265468438158925156029310985265926133792339483088426060945720579389614045244727695101069671293650665794246539609007915477818493
2010-05-25, 12:14   #2
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by aaa120 my friend let me to factor it ,but it is difficult for me to factor it, who can help me to factor it ? 67265468438158925156029310985265926133792339483088426060945720579389614045244727695101069671293650665794246539609007915477818493
You might want to reveal the source of the number.
You might also reveal the reason for wanting to factor it.

If you want others to help, you need to provide a reason for them
to spend their time and resources.

 2010-05-25, 12:19 #3 3.14159     May 2010 Prime hunting commission. 24·3·5·7 Posts "my friend let me to factor it ,but it is difficult for me to factor it, who can help me to factor it ? 67265468438158925156029310985265926133792339483088426060945720579389614045244727695101069671293650665794246539609007915477818493" Hmm. At least it wasn't a result of jabbing the number pad repeatedly, as it isn't at all repetitive. The
 2010-05-25, 12:23 #4 aaa120   Oct 2008 24 Posts I know that msieve can factor it ,but my computer is too poor to factor it
2010-05-25, 13:00   #5
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts

Quote:
 Originally Posted by aaa120 I know that msieve can factor it ,but my computer is too poor to factor it
You shouldn't just use msieve for a number this size, since that'd be quite inefficient. 128 digits isn't too hard with GNFS, even with modest resources. As a rough estimate, if your computer has 1GB of RAM you should be able to do it and finish it yourself with a couple CPU weeks of work. If not, you can still do the majority of the work yourself, and then give the data to someone else to do the finishing steps (which take a lot of memory). It will probably take a couple days to a couple weeks, depending on how fast your system is. Use this guide:
http://gilchrist.ca/jeff/factoring/n...ers_guide.html
It might be worthwhile to first do some ECM, if you're not sure that the factors are all larger than about 50 digits. An easy way to do this is with aliqueit, which can also start factmsieve.py once it's done ECMing. Aliqueit is available here, and the tools you need along with it can be downloaded here.

If you expect anyone to help you with the work of factoring this number, first tell us why we should care about this number. It may have some value of curiosity to you and your friend, but if that's all it is, you may have trouble getting help with the NFS sieving.

Last fiddled with by Mini-Geek on 2010-05-25 at 13:07

 2010-08-16, 09:29 #6 Greenbank     Jul 2005 2·193 Posts OK, factored (I was bored and needed to soak test a new blade server for a week; if it wasn't behind a firewall I would have given it some Homogenous Cunningham numbers to do...) p64 x p65 Looks RSA-ish, given the similarly sized factors and also as both P+1 and P-1 factoring wouldn't have been worthwhile spending time on (the appropriate B2 would have been way too big, the p-1 of the p65 is 2^5 * p28 * p35 for example). So, to get the factors we all need you to answer the questions asked above about why this particular number and why it is important that it is factored. Last fiddled with by Greenbank on 2010-08-16 at 09:31
 2010-08-16, 11:26 #7 jasonp Tribal Bullet     Oct 2004 DD116 Posts It's unusual to get a even split like that, so my guess is that it's an RSA key. The small size suggests it's a 'final exam' for somebody's crackme. For those who don't know, these are mini challenges that the reverse engineers give to each other to show off how much they know.
 2010-08-24, 08:57 #8 Greenbank     Jul 2005 2×193 Posts Still waiting for a response to the questions in order to post the factors. Don't anyone else waste time factoring this number as it has already been done. It raises an interesting theoretical question though, is there any way that I can prove that I've factored the number without revealing enough information to give away the factors? I'm guessing not.
 2010-08-24, 09:00 #9 10metreh     Nov 2008 2×33×43 Posts aaa120 hasn't been on the forum since 24 June.
2010-08-24, 10:02   #10
Wacky

Jun 2003
The Texas Hill Country

32·112 Posts

Quote:
 Originally Posted by Greenbank It raises an interesting theoretical question though, is there any way that I can prove that I've factored the number without revealing enough information to give away the factors? I'm guessing not.
I think that you can.

Assume that it is used to construct an RSA key. Since only you (and others who know the factors) can construct the private key, use that private key to "sign" a sample message.

If you post the public key, the message, and the signature, then anyone can verify the signature and, by extension, infer that you know the factors.

2010-08-24, 10:17   #11
warut

Dec 2009

10110012 Posts

Quote:
 Originally Posted by Greenbank It raises an interesting theoretical question though, is there any way that I can prove that I've factored the number without revealing enough information to give away the factors? I'm guessing not.
See here for a simple scheme to show that you know the factorization. Then show me your c.

Last fiddled with by warut on 2010-08-24 at 10:26

 Similar Threads Thread Thread Starter Forum Replies Last Post Raman Cunningham Tables 12 2013-06-17 21:21 Raman Cunningham Tables 43 2010-11-14 09:03 sinide Factoring 12 2010-11-09 01:05 lazy Miscellaneous Math 0 2007-06-22 12:14 Unregistered Math 11 2004-11-30 22:53

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

Sun May 9 10:52:45 UTC 2021 up 31 days, 5:33, 0 users, load averages: 1.65, 2.15, 2.52