Need a program to factor large (50 digit) numbers

[byosys]

Looking for a simple program that will factor pretty large numbers (50 digits). As a last day joke, my math teacher threw up a string of numbers and said whoever prime factored it first got some extra credit. Needless to say, I want that extra credit.

Thanks.

 

[Heisenberg]

Sure, let me fire up my quantum computer and I'll get back to you.

 

[dullard]

Like this?

 

[mugs]

You could easily write such a program, no idea how long it would take to run though.

 

[notfred]

If any of us could do this, we'd be working for the NSA as the world's foremost encryption experts.

 

[byosys]

Originally posted by: mugs
You could easily write such a program, no idea how long it would take to run though.

I know, but I really doubt Java would be a good langauge to use and my programming skills are poor at best, so it would be inefficient as hell not even factroing in the fact that its Java.

 

[byosys]

Oh and the above link chokes on the number that he gave us...apparently its larger than the 50 digits I quoted above. I just kinda estimated and was wrong.

 

[drinkmorejava]

meh, I could write one in JAVA in maybe 5 min, however, unless it factor by 2 or 3 a lot, it'll take a damn long time. If you really need it, i might bother to work on it.

 

[DBL]

Originally posted by: byosys
Oh and the above link chokes on the number that he gave us...apparently its larger than the 50 digits I quoted above. I just kinda estimated and was wrong.

You realize there is no easy way to do this? If there were, encryption as we know it, would cease to exist.

 

[byosys]

Any guesses as to how long a "damn long time" is? If its months/years, it won't be worth it cause I will have graduated. If it's days or so, I may brush up on my JAVA skills and learn how to output the factors to a text file (never got around to learning that).

 

[drinkmorejava]

bloody hell, you're starting to convince me to do it, what's the number

 

[DBL]

Originally posted by: byosys
Any guesses as to how long a "damn long time" is? If its months/years, it won't be worth it cause I will have graduated. If it's days or so, I may brush up on my JAVA skills and learn how to output the factors to a text file (never got around to learning that).

Prime Factorization

When the numbers are very large, no efficient algorithm is known; a recent effort which factored a 200 digit number (RSA-200) took eighteen months and used over half a century of computer time

 

[byosys]

74037563479561712828046796097429573142593188889231289084936232638972765 034028266276891996419625117843995894330502127585370118968098286733173273 108930900552505116877063299072396380786710086096962537934650563796359


I hope I typed that in right...word tells me its 200+ digits, so I guess my estimate of 50 was off by just a little bit. If you do write the app, would you mind emailing it along with the source to byosys@gmail.com? I want to see how different your code is from mine.

Edit: notice I added spaces for formatting issues, so a straight copy/paste won't work.

 

[AStar617]

Originally posted by: Heisenberg
Sure, let me fire up my quantum computer and I'll get back to you.

Apparently nobody appreciates this but me. :beer:

 

[Heisenberg]

Originally posted by: AStar617

Originally posted by: Heisenberg
Sure, let me fire up my quantum computer and I'll get back to you.

Apparently nobody appreciates this but me. :beer:

Guess not.

OP, if you haven't figured it out by now, your teacher is playing a joke on you. Prime factoring a 200 digit number is extremely time consuming.

 

[chuckywang]

Originally posted by: byosys
Looking for a simple program that will factor pretty large numbers (50 digits). As a last day joke, my math teacher threw up a string of numbers and said whoever prime factored it first got some extra credit. Needless to say, I want that extra credit.

Thanks.

Good luck:

n is about 10^50, you need to check about 10^25 numbers

Assuming your program checks 1 number every nanosecond, it would take you 10^16 seconds to check all the numbers = about 300 million years.


Your teacher is obviously joking with the class. The extra credit will never be handed out.

 

[byosys]

I realized it was joke and that he didn't actually think anyone could/would do it, but it would be really cool to show up tomorrow/before we graduate with answer in hand, demanding my extra credit.

 

[chuckywang]

Originally posted by: Heisenberg

Originally posted by: AStar617

Originally posted by: Heisenberg
Sure, let me fire up my quantum computer and I'll get back to you.

Apparently nobody appreciates this but me. :beer:

Guess not.

OP, if you haven't figured it out by now, your teacher is playing a joke on you. Prime factoring a 200 digit number is extremely time consuming.

If by extremely time consuming you mean impossible, then yes.

 

[imported_LoKe]

Tell him to do it first.

 

[MattCo]

Originally posted by: byosys
74037563479561712828046796097429573142593188889231289084936232638972765 034028266276891996419625117843995894330502127585370118968098286733173273 108930900552505116877063299072396380786710086096962537934650563796359


I hope I typed that in right...word tells me its 200+ digits, so I guess my estimate of 50 was off by just a little bit. If you do write the app, would you mind emailing it along with the source to byosys@gmail.com? I want to see how different your code is from mine.

Edit: notice I added spaces for formatting issues, so a straight copy/paste won't work.

It will probably be ALOT different considering you haven't wrote any yet.

 

[Heisenberg]

Originally posted by: chuckywang

Originally posted by: Heisenberg

Originally posted by: AStar617

Originally posted by: Heisenberg
Sure, let me fire up my quantum computer and I'll get back to you.

Apparently nobody appreciates this but me. :beer:

Guess not.

OP, if you haven't figured it out by now, your teacher is playing a joke on you. Prime factoring a 200 digit number is extremely time consuming.

If by extremely time consuming you mean impossible, then yes.

Well, impossible is a very hard word. With enough computing power and time, it could be done. But yeah, from any kind of practical point of view, you're better off flapping your arms and trying to fly to get that extra credit.

 

[TuxDave]

Originally posted by: MattCo

Originally posted by: byosys
74037563479561712828046796097429573142593188889231289084936232638972765 034028266276891996419625117843995894330502127585370118968098286733173273 108930900552505116877063299072396380786710086096962537934650563796359


I hope I typed that in right...word tells me its 200+ digits, so I guess my estimate of 50 was off by just a little bit. If you do write the app, would you mind emailing it along with the source to byosys@gmail.com? I want to see how different your code is from mine.

Edit: notice I added spaces for formatting issues, so a straight copy/paste won't work.

It will probably be ALOT different considering you haven't wrote any yet.

lol.. I was about to say the same thing

 

[tfinch2]

Why don't you write the code to factor it, then explain why it isn't possible. Your teacher will be impressed by your e-peen and you might get extra credit.

 

[chuckywang]

If we could factor 200 digit numbers efficiently, the entire RSA enryption scheme is rendered useless. No RSA means no online security means no online shopping/no online banking, etc.

 

[byosys]

True, but my basic program would simply (in shorthand):

take input number and devide by 2,3,5...all the odd numbers
if (number) % (count variable) ==0
{number = number/(count)
store count in an array }

repeat until count == number
print array

Efficient? Hell no, but thats about the extent of my programming skills. If an efficient app will take a long time, imagine how long mine will take....

Edit: I guess I would take the first 10,000 or so primes and put them in an array and just devide the number by thoes to save wasted iterations...no point in dividing by 9, 15, etc since it wasn't evenly divisiable by 3.