gandlf
17/11/07, 15:09
> So what is the expected running time of your algorithm? For example,
> how long it will take on average to factor a 1024-bit modulus?
I don't know because I have to know the average biggest totient
divisor of a 1024-bit modulus.
> >
> > - Repeat "a = a^n mod m" with n from 2 to m, saving all the results in
> > a table until a == 1 (Statement 4).
>
> Do I understand correctly that this step of your proposed algorithm
> can identify the private key corresponding to (e.g.) a 1024 bit public
> key, but only by doing on the order of Sum(2..2^1024) = ~ 2^1025
The algorithm ends when a == 1, and that happens when n is the biggest
modulus' totient divisor.
4) - If "a" contains by power all the totien's divisors then
"a^n mod m" will
always be "1".
> how long it will take on average to factor a 1024-bit modulus?
I don't know because I have to know the average biggest totient
divisor of a 1024-bit modulus.
> >
> > - Repeat "a = a^n mod m" with n from 2 to m, saving all the results in
> > a table until a == 1 (Statement 4).
>
> Do I understand correctly that this step of your proposed algorithm
> can identify the private key corresponding to (e.g.) a 1024 bit public
> key, but only by doing on the order of Sum(2..2^1024) = ~ 2^1025
The algorithm ends when a == 1, and that happens when n is the biggest
modulus' totient divisor.
4) - If "a" contains by power all the totien's divisors then
"a^n mod m" will
always be "1".