Re: [isabelle] Computing divisors



On 10/19/2013 09:15 AM, Manuel Eberl wrote:
> Yes, indeed, I think so, too. Although I do not know the latest
> developments in number field sieve algorithms; they might have become
> better at handling small integers in the mean time. However, I was not
> looking for an efficient factorisation algorithm, but for a more
> efficient algorithm for the divisors of n than trial division for
> /every/ natural number ≤ n. And that is, indeed, possible.

I'm not sure I follow. Yes, there are asymptotically faster algorithms
than trial division, but that you knew already. I merely said that is
nothing more efficient than trial division (with odd numbers <= sqrt(n))
for factoring a single relatively small number. With "small number"
being I guess anything not used for crypto. I'm not a cryptographer
though, so I could be wrong, but I'm not even sure if you're disagreeing
with me or not.

> The Haskell arithmoi package, for instance, first computes the prime
> factorisation using a combination of some kind of trial division for
> small factors and then a number field sieve and then uses that to
> generate the divisors, and since the authors of the arithmoi package
> generally seem to know their stuff, I would assume that this is indeed
> the most efficient way to do it.

I looked at the code briefly, and yes, the authors seem to know crypto
much better than I do. However, judging by their comments they don't
implement any number field sieves, they use elliptic curve
factorization. Which, according to my crypto course lecture notes,
"performs well for numbers with a medium-sized smallest factor (20-60
digits)".

> So I think that at some point, I will probably implement this in
> Isabelle – minus the number field sieve, of course – and until then, I
> will stick with the naïve approach.

Another option is continued fractions factorization, which are
relatively simple IIRC, and beat trial division asymptotically. But I
think it all really depends on what your application is.

Cheers,
Ognjen






This archive was generated by a fusion of Pipermail (Mailman edition) and MHonArc.