Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have sat for about 8 hours doing trial and error and I have tried all combinations of different prime numbers but I am totally stuck..

I know that prime power decomposition is suppose to be prime number to the power of integers and their product gives you the original number... but I am asked to break this number down into its prime power decomposition.

412023436986659543855531365332575948179811699844327982845455626433876445565248426198098870423161841879261420247188869492560931776375033421130982397485150944909106910269861031862704114880866970564902903653658867433731720813104105190864254793282601391257624033946373269391

i have tried trial division which miserably failed after 1000, and now I am trying to divide the number into the largest prime number I can find and take the quotient I get and try to factor that into the largest prime number it can fit and so on until i have it all factored....is this even possible?

There is some browser problem I am having where comment button on stack isnt working.

This is one of the 8 assignment questions I have been assigned. I have finished all others and this I cant do from past 8 hours...

Should I write down all the prime numbers that are smaller than this number /2? and then try to break this up into those?

share|improve this question
8  
Are you serious?! –  Salech Alhasov Mar 4 '12 at 4:20
3  
What does "sqrt divisions" mean? If this is an assignment, what techniques have you been discussing? If it is not an assignment, then why are you trying to factor this? –  Arturo Magidin Mar 4 '12 at 4:23
2  
Which begs the question, yet again: what factoring techniques have you discussed in your class? Obviously you are supposed to be trying to use them. P.S. If you were really going to do trial division, you only have to go up to $\sqrt{n}$, not up to $n/2$. –  Arturo Magidin Mar 4 '12 at 4:44
7  
As it turns out, this number is actually RSA-896. There was a \$75,000 prize offered for factoring it, and nobody has ever factored it successfully. Abandon all hope. –  Tanner Swett Mar 4 '12 at 4:52
3  
@Raynor: There are about $10^{23}$ different prime numbers with 25 digits alone. That's about a million times the number of seconds there have been since the big bang. And given that Tanner has identified the number as RSA-896, the factors are more likely to have about 130 digits than 25. The number of 130-digit primes is so much larger than the estimated number of atoms in the observable universe that it isn't even funny. Do yourself a favor and let it go. This question is obviously not meant to be solved as an exercise. –  Henning Makholm Mar 4 '12 at 5:20
show 10 more comments

1 Answer

up vote 10 down vote accepted

We shall put the question to rest. The number

412023436986659543855531365332575948179811699844327982 845455626433876445565248426198098870423161841879261420 247188869492560931776375033421130982397485150944909106 910269861031862704114880866970564902903653658867433731 720813104105190864254793282601391257624033946373269391

is called RSA-896; it is a large semiprime (the product of two distinct primes, neither too small).

There was a 75k$ bounty on it at one point. It has not been factored so far. There is absolutely no reason to believe someone can factor this with their own ability and a common PC and only sane amounts of time, short of strange and mystical number-theoretic methods beyond all present-day knowledge delivered from the distant future. You've been punked, smile for the camera!

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.