Is factoring really a hard problem?

Here is a very interesting blog post on this question.

I’ve often wondered how and why factoring was chosen as a standard for public key cryptography. There are the obvious reasons, ease of implementation etc. but given that there is no hardness proof it seems risky to standardize on it.

One possible explanation is that it is not really hard at all, and the expertise and machinery required to factor the usual sizes of numbers used in standard encryption schemes is readily available to some, but for some reason this capability is thought to be out of reach for most everyone else. This could be in the form of different algorithms with better scaling, but somehow I doubt it. This would be too hard to keep secret. I think it’s more likely that some types of special hardware implementations vastly reduce prefactors in algorithms similar to those publicly known. This would  make factoring feasible for moderate sized products of primes if you had the resources to develop such special purpose hardware.

In other words, when you want to really do something properly, the scaling of the algorithm is of course important, but speeding everything up by a factor of a million can make the difference between “forget it” and “easy”.

Advertisements

2 Responses to “Is factoring really a hard problem?”

  1. mahfoud belhadj Says:

    in my humble opinion, factoring is hard only because we probably are not thinking about it the right way. I believe most of the complexity of factoring has been added by us. I never believed that in the ” factoring is hard ” assumption. I will probably say more about factoring in few days.

  2. Chester Says:

    I is Engrish teacha. Factorin’ is nothin’ I’se wanna reads ’bout.

    Ya’ll gots ta rites sompin new, Gordie…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: