Is factorization a hard problem? There is plenty of empirical evidence that it is so. Take the following 309-digit number that is known as RSA-1024, an example of an RSA number.

*RSA-1024*13506641086599522334960321627880596993888147560566

70275244851438515265106048595338339402871505719094

41798207282164471551373680419703964191743046496589

27425623934102086438320211037295872576235850964311

05640735015081875106765946292055636855294752135008

52879416377328533906109750544334999811150056977236

890927563

RSA-1024, a 1024-bit number, is a product of two prime numbers and . No one has been able to factor this number, despite the advances in factoring algorithms and computing technology in recent decades. RSA-1024 is part of the RSA Factoring Challenge that was created in 1991. Even though the challenge was withdrawn in 2007, it is believed that people are still taking up the challenge to factor this and other unfactored RSA numbers. In fact, the successful factoring of RSA-1024 or similarly sized numbers would have huge security implication for the RSA algorithm. The RSA cryptosystem is built on the difficulty (if not the impossibility) of factoring large numbers such as RSA-1024.

Yet it is very easy to demonstrate that RSA-1024 is not a prime number. The fact that it is composite can be settled by performing one modular exponentiation. Denote RSA-1024 by . We compute .

We find that where is the following 309-digit number.

12093909443203361586765059535295699686754009846358

89512389028083675567339322020593385334853414711666

28419681241072885123739040710771394053528488357104

98409193003137847878952260296151232848795137981274

06300472693925500331497519103479951096634123177725

21248297950196643140069546889855131459759160570963

857373851

Obviously is not 1. This fact is enough to prove that the modulus is not a prime number. This is because the number lacks a property possessed by all prime numbers. According to Fermat’s little theorem, if were prime, then that for all integers that are relatively prime to . In particular, if were prime, then we would have , the opposite of our result.

The modular exponentiation discussed here can be performed using the fast powering algorithm, which runs in polynomial time. In the fast powering algorithm, the binary expansion of the exponent is used to convert the modular exponentiation into a series of squarings and multiplications. If the exponent is a -bit number, then it takes squarings and at most multiplications. For RSA-1024, it takes 1023 squarings and at most 1023 multiplications (in this instance exactly 507 multiplications). This calculation, implemented in a modern computer, can be done in seconds.

The above calculation is a vivid demonstration that factoring is hard while detecting the primality or compositeness of a number is a much simpler problem.

The minimum RSA key length prior to the end of 2013 is 1024. After 2013, The minimum RSA key length is 2048. In fact, the largest RSA number is RSA-2048 (has 2048 bits and 617 decimal digits), which is expected to stay unfactored for years to come barring dramatic advances in factoring algorithms or computing capabilities.

___________________________________________________________________

**Exercise**

Using a software package that can handle modular exponentiation involving large numbers, it is easy to check for “prime versus composite” status of a large number. Find a number whose prime factorization is not known. Either use known numbers such as RSA numbers or randomly generate a large number. Then calculate the modular exponentiation for several values of (it is a good practice to start with ). If the answer is not congruent to 1 for one value of , then we know is composite. If the exponentiation is all congruent to 1 for the several values of , then is a likely a prime number.

___________________________________________________________________