From: gandlf (gandlfgmail.com)
Date: Thu Nov 15 2007 - 14:46:44 CST

• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

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

• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]