November 14th, 2011, 11:17 AM
Factorization of 512 bit and 1024 bit numbers
Hi, everyone. (sorry for my grammatic, I know english not well)
I am studying in MIPT, so i have been given a task in cryptography. I need to factorize 2 numbers - one 512 bit and one 1024 bit and i have about a day for till deadline.
I tried at first MSIEVE, but it need about several weeks to factorize 512 bit number.. Last night i tried to check modulo my number to prime numbers - from sqrt(my_number) and go on..
This attempt failed too - it will take too much time.
Can You help me with any ideas to meet the deadline..
Thanks a lot.
November 14th, 2011, 03:06 PM
Usually I don't reply, when people ask for help with schoolwork -- but this is an unusual assignment.
If the numbers are like RSA moduli, with two randomly chosen factors of nearly equal magnitude, then factoring them in a few days is a practical impossibility. If you know that these are "RSA-type" numbers, the correct answer would be to spend a few hours researching factoring techniques and their cost -- as well as factoring records (largest numbers factored so far), and to explain why the numbers you were given cannot be factored in any short period of time.
If these aren't RSA-type numbers, then perhaps you were given more information about their structure. Do you know how many factors they have? If they are composite, do you have any information concerning the size of the factors? Are you sure they are not prime? Were they created using some formula or algorithm?
There are tests that can tell you (in a reasonable time) whether a large integer is prime.
If a large composite has only one large factor, then you can factor it using trial division.
There may be an efficient factoring algorithm for specially constructed numbers (for example, composite Fermat numbers).
Last edited by mah$us; November 15th, 2011 at 11:47 AM.