### Thread: Factorization of 512 bit and 1024 bit numbers

1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2011
Posts
1
Rep Power
0

#### 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.
2. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2009
Posts
191
Rep Power
53
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 12:47 PM.