PDA

View Full Version : C++ Challenge!

MindTheGap
10-19-2007, 02:32 AM
This is a really fun problem. My teacher assigned it to us last week and the first person that got it correct got an iTunes gift card.

Somebody already won, so I thought I'd post the problem here to see if you guys can get it!

The number below is a composite. It is the product of two prime numbers. Just like 21 is equal to 7 times 3, the number below is equal to the product of two primes.

1,435,334,297,627,885,237,510,222,145,546,396,275,688,036,595,057,651,576,302,853

Your job is to find the two primes that when multiplied, the result is the above number.

ralph l mayo
10-19-2007, 08:38 AM
Someone got it? Did they use a quantum computer? I was under the impression that prime factorization for numbers that large was computationally infeasible. Unless I'm missing something about this particular number, which is a likely scenario.

awsomejoe23
10-21-2007, 12:22 AM
I'm sure they could have a simple algorithm that utilized some sort of numerical pattern in in the product of prime numbers.
For example, just now thinking about it
9 * x
first_digit =
x - 1

second_digit =
the difference between (x and 9) +1
Or at least I think so, just came up with that, :)
My point being you could reverse that, as well as any formula for multiplying 2 prime numbers.

Joe

EDIT: looked around real quick, and I found this
"all prime numbers can be written as (6n+1) or (6n-1)."
You could do
(6n +or- 1) * (6x +or-1) = 1,435,334,297,627,885,237,510,222,145,546,396,275,688,036,595,057,651,576,302,853
then use foil, to get it down, then use simple substitution, or elimination to find the answer. (but that would take too long, I would look for some sort of patterns)

oracleguy
10-21-2007, 10:22 AM
To find a value of n that met that equation would require a lot of processing power.

I am also curious how this student figured it out.

10-21-2007, 04:39 PM
It's possible that the student used the theory, k-almost-prime in order to make it at least slightly more computably feasible.

There are a couple theories out there on how to get a prime number in a shorter time rather then worrying getting it exactly. A quick google search turned up two for me

Almost Prime (http://en.wikipedia.org/wiki/Almost_prime)
Eratosthenes (http://www.math.utah.edu/~alfeld/Eratosthenes.html) <-- that one doesn't seem feasible tho..

Interesting Applet (http://www.cryptographic.co.uk/factorise.html)

Inigoesdr
10-21-2007, 05:44 PM
Or the student didn't find it, and the OP wants that gift card. :D

marek_mar
10-21-2007, 08:32 PM
Someone got it? Did they use a quantum computer? I was under the impression that prime factorization for numbers that large was computationally infeasible. Unless I'm missing something about this particular number, which is a likely scenario.
That number is not really that big. It's "only" 200 bits. The smallest number to factorize in the RSA factoring challenge had 330 bits and was factorized in 1991.

marek_mar
10-21-2007, 09:25 PM
Actually I've already found them. It took my Core 2 Duo 5 minutes:
1159604909814835281776480024219 * 1237778734359686514332712408287 = 1435334297627885237510222145546396275688036595057651576302853
Though I didn't write the thing that actually did it.

ralph l mayo
10-21-2007, 11:09 PM
That number is not really that big. It's "only" 200 bits. The smallest number to factorize in the RSA factoring challenge had 330 bits and was factorized in 1991.

Ah yeah, you're right. It certainly *looks* that big, though :]