Thursday, June 12, 2008

Examples for the algorithm

I got a lot of trouble making people understand this idea. So let me start with the simplest example that should make people understand my idea. So let us understand the problem.

The problem is i will give a number say 221 and you should tell me that it has 13 and 17 as factors.

So lets go by conventional method and see how it works.
Step1: find the square root of the number and truncate the decimal places. i get 14.
Step2: start looping from 2 till that number in step 1 which is 14.
Step3: Check if the number is prime.(note checking if a number is prime involves another loop).
Step4: if yes divide 221 by that number and see if it is divisible.
Step5: if no proceed with step 3 through 4.

By these process we get 13 as a factor. The result of division would give us 17. Wow we made it.

But at what cost of time? so a minimum of 12 steps (2 through 13) is needed to arrive at the result excluding the primality check at step 3.

Lets start with the new method and find out the results.

Step1: find the square root of the number(14.86) and check if the decimal part is zero.
Step2: The decimal value is not zero. So trucate the decimal part and assign the found value (14) to x.
Step3: Add 1 to the value x (i.e. x= 14+1 = 15).
Step4:Find the output of Square root of (15*15-221) = 2 and remainder part is zero
Step5: The remainder of square root is zero. so we have our solutions. x=15 and we found a value 2
Step6: The results are 15+2 and 15-2 which is 13 and 17.

So we have taken just 1 loop. to find the results. Even if we take each step as an operation i find the answer in just 6 operations.

This shows that we can find the factors of RSA with atleast 10 times faster than conventional method.

Do let us know if you find this interesting. This is an idea for the people. So i am planning to put it under GPLV3.

2 comments:

Thripthy said...

Yes it is a very easy method and is easily understandable. What I think is anyone would be able to grap this method of finding the factors. Superb! Applause!!

Knight Telekinetic said...

Cool! Did you see the GSM algorithm used to encrypt most mobile phone calls has been cracked.