Need a program to factor large (50 digit) numbers

[AStar617]

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.

Not impossible. Read this, and this if you are interested in how problems like this can be solved (when the technology fully gets there, soon enough).

 

[byosys]

Oh btw I found this site:

http://www.alpertron.com.ar/ECM.HTM

which seems to use your home computer for factor the number using some method I've never seen before...can anyone explain the Elliptic Curve Method?

 

[mugs]

I think your only hope is if the number he gave you is prime.

 

[mugs]

Originally posted by: 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.

I was just going to suggest your edit. First google search result gave me a website with the ~450 million prime numbers between 0 and 10 billion. I'm thinking you might need some bigger numbers than that though. But maybe not. If your prof got that number by multiplying a bunch of prime numbers together, he probably didn't use any primes higher than 10 billion.

 

[ArJuN]

How much would you pay me if I solved this?

EDIT: ****** it, it's not even even!

 

[notfred]

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.

Actually, I have a feeling that most of the people who posted comments about encryption appreciated it, too.

 

[AStar617]

Originally posted by: ArJuN
How much would you pay me if I solved this?

EDIT: ****** it, it's not even even!

Uh... Odd numbers have factors too...

 

[drinkmorejava]

wow, um 212 digits, how do you get 50 out of that. Sorry to dissapoint you, but I'm not going to waste time making the program handle a number than big. A normal double value only goes to 2^64 (-1 i think) which is like 18446744073709551615. Def not 212 digits.

 

[JayHu]

Originally posted by: mugs
I think your only hope is if the number he gave you is prime.

Which you can now test for in polynomial time, thanks to indian mathematicians.

however, I think that he probably gave you a public rsa key or something like that.. maybe it's his key, so your chances of factoring it... pretty much 0.

 

[CraKaJaX]

You took the time to write that number down in class? F that.

 

[Koing]

Originally posted by: notfred

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.

Actually, I have a feeling that most of the people who posted comments about encryption appreciated it, too.

I appreciated it :thumbsup:

Koing

 

[Koing]

Originally posted by: 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

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.

LOL

Your F0CKED. NO ONE will get the dam number.

50digits Vs 200+ is A HUGE difference.

Koing

 

[CycloWizard]

Just write down that number and one. If it's prime (my guess), then you get the extra credit with no work. If not, oh well - you weren't getting it anyway.

 

[sciencewhiz]

Your teacher may give you extra credit. I'll give you $10,000.

 

[byosys]

The (number) and 1 trick won't work because it is composite according to the site I linked to earlier. I have to run out for a bit, but I'll check back later, though at this point I'm pretty much giving up on getting that extra credit.

 

[drinkmorejava]

Ok, I wrote a java factoring program, it's amazingly inefficient but w/e. If you want to mess around with it be my guest, but there's no way it'll do a number that long

you can find the source at www.randomdeviance.com/java/Factor

there's a Keyboard class package (cs1) in there that you'll need to compile, otherwise I threw the compiled classes in there too.

 

[mundane]

Originally posted by: drinkmorejava
Ok, I wrote a java factoring program, it's amazingly inefficient but w/e. If you want to mess around with it be my guest, but there's no way it'll do a number that long

you can find the source at www.randomdeviance.com/java/Factor

there's a Keyboard class package (cs1) in there that you'll need to compile it, otherwise I threw the compiled classes in there too.

You might want to look into the java.math.BigInteger class. It handles arbitary-sized integer values. The primitive double will eventually choke on larger values, while the BigInteger class will gladly manipulate them as long as you have enough memory.

 

[drinkmorejava]

cool, I might do that later and add a dynamic base case and incrementor for the loop...and then set it up for a week on an A XP 2800.

 

[Kyteland]

I have a c++ program chugging away seeing if it's divisible by any of the first 15 million primes. It'll take about an hour to run.

Your only hope of factoring this is that your teacher multiplied a bunch of <9 digit primes together and not two large prime numbers.

Edit: I'm through the first 5 million and no prime factors fo far.
Edit: Up to 13 million. I would give up and say it isn't going to happen.

 

[Jeff7]

RSA-704

The professor had better give you $30K if you can factor that.

According to that site, factoring the 193-digit RSA-640 number took "approximately 30 2.2GHz-Opteron-CPU years according to the submitters, over five months of calendar time."

 

[byosys]

drinkmorejava: is there a reason you stored the factors in a string rather than an array? I always figure that it made sense to leave numbers as ints/doubles so you can go back and use them as such should you choose to do so later and can print them just as easily as printing a string. All in all, pretty much exactly what I would have written (I've given up trying to find it) but assuming I had the time, I would have put the first x number of primes into an array and just modded the number by them.

Off topic question: for the last part of the program: the else {i++}, wouldn't it be faster to delete that and change the for loop to read for (int i=2; i<=(newnumber/3); i=i+2)? You essentially absorb the else command when you increment the loop...

Final question: what do you mean by adding a dynamic base case? I a. don't know what you mean and b. can't see anything to really gain unless it somehow involves multithreading...

 

[ActuaryTm]

Took a screenshot of my solution running.

Mother and Whistler should have you an answer shortly.

 

[drinkmorejava]

Yes, an array would have been better if I wanted to go back later; however, I'm not sure what for. The only thing I'm coming up with is maybe to sort it, but if we're talking about lots of numbers, there's no reason to add something with an O(n^2) inefficiency. Yes, an array with the first x primes would be more efficient, I even have a program I made a while back that will compute them...or one could just d/l them...of course, if I actually stored them, that's several megabytes worth of stuff in the source that I wouldn't feel like uploading.

LOL, I didn't even realize that I was doing two i++ in there, now that I think about it logically, it actually makes sense to increment by two too, but because I don't have an i++ in the if, it kind of messes it up. Then again, if I really wanted I could just make the loop a massive recursive function; point being, never ask me to program anything for you...which you didn't.

by a dynamic base case (base case is the term used in recursive functions for what will cause it to be satisfied)* I mean it would terminate the loop iteration sooner depending on what number it's checking, but if you use a list of primes anyway it wouldn't do anything. Like if we have the number 100, I could check every value up to 33, but this condition of this would be satisfied by 3, same with checking ever number up to 50 which would be satisfied by 2. In this case it would stop at 2, divide the number and repeat using 50 as the new value, but for something that is a prime number, it would make no sense to keep going that high when we'd be sure there would be no solution.

*ie: if you had

int i=0;
increase(int x)
{
if x>0
{i++; increase(x);}
}

it would loop around forever because the base case being x>0, will never not be true until it got to (x^31)-1 whence it would crash due to the int being to large; or to really elaborate, it would prob turn into a negative number, weird how that seems to happen, in which case the method would do nothing

AND THIS PEOPLE, IS WHY WE NEED A SEPARATE PROGRAMMING GATEGORY

 

[drinkmorejava]

Originally posted by: ActuaryTm
Took a screenshot of my solution running.

Mother and Whistler should have you an answer shortly.

lol, what is that, it looks like a debug dump or something.

 

[Kyteland]

That number doesn't have the first 15 million primes as a factor.

Unless you typed it in wrong.....