• We’re currently investigating an issue related to the forum theme and styling that is impacting page layout and visual formatting. The problem has been identified, and we are actively working on a resolution. There is no impact to user data or functionality, this is strictly a front-end display issue. We’ll post an update once the fix has been deployed. Thanks for your patience while we get this sorted.

Need a program to factor large (50 digit) numbers

B

byosys

Senior member
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.
 
Originally posted by: mugs
You could easily write such a program, no idea how long it would take to run though.
Click to expand...

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.
 
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.
 
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.
 
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.
Click to expand...

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

 
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).
 
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).
Click to expand...
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
Click to expand...
 
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.
 
Originally posted by: AStar617
Originally posted by: Heisenberg
Sure, let me fire up my quantum computer and I'll get back to you. 😛
Click to expand...
Apparently nobody appreciates this but me. :beer:
Click to expand...
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.
 
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.
Click to expand...

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.
 
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.
 
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. 😛
Click to expand...
Apparently nobody appreciates this but me. :beer:
Click to expand...
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.
Click to expand...

If by extremely time consuming you mean impossible, then yes.
 
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.
Click to expand...

It will probably be ALOT different considering you haven't wrote any yet. 😛
 
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. 😛
Click to expand...
Apparently nobody appreciates this but me. :beer:
Click to expand...
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.
Click to expand...

If by extremely time consuming you mean impossible, then yes.
Click to expand...
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.
 
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.
Click to expand...

It will probably be ALOT different considering you haven't wrote any yet. 😛
Click to expand...

lol.. I was about to say the same thing
 
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.
 
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.
 
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.
 
You must log in or register to reply here.

TRENDING THREADS

Back
Top