[wplug] Factorization idea

[Vikram Sai Balaji]

Hi,
i am just a small math enthusiast. i have been trying to understand numbers
and their products and how factorization has evolved. This is my hobby for
the past 5 years and i have devised a small algorithm for factorization
(based on fermat's theorem). This method is faster for numbers whose factors
lie closer to  each other. Below is an example on how to compute the
factors. (Application of this algorithm: finding the factors of rsa public
key).

Note: This is not as fast as elliptic curve method. But just another way to
look at things.

Below is an example along with the algorithm
The problem here is we will given a number say 221 and we should tell that
13 and 17 are factors.

Conventional method uses the idea
"At least one factor (which will be always prime) will be less than the
square root of the number"

So lets go by conventional method and see how it works.
Step1: find the square root of the number and truncate the decimal places.
we 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.

My method lies on the principle
"square root of product of two numbers is nearer to the average of the
numbers"

Algorithm:

    1. First find the sqrt{K} and see if the decimal value is zero. Assign
the value whole number x by truncating the decimal.

    2. If the decimal value is Zero then the answer is the result else
proceed to step 3

    3. Add 1 to x and assign the value to x.

    4. Find the output sqrt{x^2-K}. Note. Perform square root and find
       remainder rather than the value after decimal pont. Assign the trunc
value of the result to "y".

    5. If the remainder in the previous step is zero stop the process else
go to step 3.

    6. The results are x+y and x-y.


Lets start with the my 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 we 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 for factors which have primes closer to each other.

The question here would be "how is this relevant to lug?"

All the ideas were implemented under the GNU/Linux machines and GNU/Linux
has given me freedom to think for the community and for the betterment of
it. Thanks FSF for opening my mind!!

Given below is the program written in octave.

*******This program is licensed under GPLV3**********

-----------Program--earthworm.m---author: Vikram Ulaganathan--------
K= 21437689
tic();
x=round(sqrt(K))+1
time1=toc();
y=0;
p=0;
flag=0;
dp=0;
sum = x*x
m=1;
i=x;


count=0;

disp('count,y');
disp(count);


y=round(sqrt(sum-K));
count=count+1;
sumy= y*y
j=y;
twox = 2*x;
while(i!=twox)
    d=sum-K;
    j= ceil(sqrt(d));
    sumy = j*j;
    if (d == sumy)
    disp('found the value');
    disp(i);
    disp(j);
    disp(sum);
    disp(sumy);
    disp(count);
    disp('a & b is');
    disp((i+j));
    disp((i-j));
    xv(m) = i;
    yv(m) = j;
    break;
    endif
    count=count+2;
xv(m)=i;
delta(m)=d-sumy;
yv(m)=j;
sum = sum + (2*i+1);
i=i+1;
m=m+1;
end
disp('Totalcount');
disp(count);

------------------------
Install octave.
store program
The first line in the code "K" is the number to be factorized. Replace the
number with RSA public key
from command prompt run the following command
"octave earthworm.m > output_results.txt"

you would get the results in the output_results.txt document.
The output would tell us about the answers and the count.
Note: the count in the loop is incremented by 2 just to assume that square
root of a number is a seperate operation.
----------------------------
Thanks
Vikram
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.wplug.org/pipermail/wplug/attachments/20080807/1f26ba9e/attachment.html