3
$\begingroup$

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?

  • 1
    Factoring is hard; what techniques do you have at your disposal, besides trial division? I assume you checked the easy divisibliity cases (by $3$, by $11$, or even all primes up to a certain bound?) You don't need to find the full expression in one go, just start finding factors, divide them out, and work on the quotient as you go.2012-03-04
  • 8
    Are you **serious**?!2012-03-04
  • 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?2012-03-04
  • 0
    For the love of God, don't try to factor that by hand. I'm using this to try to factor it: http://www.alpertron.com.ar/ECM.HTM According to that, the smallest prime factor most likely has between 20 and 25 digits; you *will not* find it by guessing randomly.2012-03-04
  • 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$.2012-03-04
  • 0
    I believe many people like me simply put [this face](http://i0.kym-cdn.com/entries/icons/original/000/005/545/OpoQQ.jpg) when seeing that number.2012-03-04
  • 0
    @WillJagy He's an alien and he is testing us.2012-03-04
  • 7
    As it turns out, this number is actually [RSA-896](http://en.wikipedia.org/wiki/RSA_numbers#RSA-270). There was a \$75,000 prize offered for factoring it, and nobody has ever factored it successfully. Abandon all hope.2012-03-04
  • 0
    I hope our teacher wasnt playing a prank on us by giving that for an assignment question....he cant seriosuly expect us to do this, even after 9 hours which is the longest ive spent on any question I am hopeless2012-03-04
  • 0
    I am sorry for even aksing this question, i did not know that there was no solution to this yet. Can someone please link me to a website that has massive prime numbers starting from small prime numbers and their prime factor decomposition?2012-03-04
  • 0
    Tanner LSwet if the prime number is less than 25 digits then if we take all prime number with less than 26 digits one of them must divide this number right? if so then we divide this huge number by that prime number and take the quotient we get and factor that out and2012-03-04
  • 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.2012-03-04
  • 1
    @Raynos your teacher probably wants you to have a first hand experience with hardness of factoring.2012-03-04
  • 0
    thank you guys for helping. I feel stupid spending all those hours trial erroring this..2012-03-04
  • 0
    Reading the first response to this question made my crack up so freaking hard. I think I am falling in love with you guys. By the way, will this ever be factored?2012-03-04

1 Answers 1

10

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!