<<< Date Index >>>     <<< Thread Index >>>

Re: Breaking RSA: Totient indirect factorization



> 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".