Re: ISO prime factorization algorithm for n <= 10^10

"*** T. Winter" <***.Winter@xxxxxx> writes:

> In article <christian.bau-289074.16560228082005@xxxxxxxxxxxxxxxxxxxxxxxx> Christian Bau <christian.bau@xxxxxxxxxxxxxxxxxxxx> writes:
> > In article <desie1$j84$1@xxxxxxxxxxxxxxxxx>,
> > kj <socyl@xxxxxxxxxxxxxxxxx> wrote:
> ...
> > > I find plenty of details *if* the aim is to bust RSA, but nothing
> > > for 10-digit numbers or smaller.
> ...
> > HOWEVER I think that a really well written trial division algorithm
> > might still be fastest for that size of number.
>
> It is my opinion that for that kind of numbers trial division will be
> superior to any other method, unless it is *really* badly written.
> Even just a first check whether the number is even following by a
> trial division by odd numbers until sqrt(n) will be superior, and also
> will be better than using a list of primes. A long time ago I tested
> such on a CDC Cyber with 48 bit integers (about 15 digits).

I'm surprised Brent Rho doesn't begin to become competative at
about the size he's considering. It's a terribly simple inner
loop. However, TD for a short stretch is almost always the best
start, a thousand or so.

At 10^15, I'd probably want to abort Rho after a few thousand
and hit SQUFOF.

Phil
--
If a religion is defined to be a system of ideas that contains unprovable
statements, then Godel taught us that mathematics is not only a religion, it
is the only religion that can prove itself to be one. -- John Barrow
.

Quantcast