Re: [isabelle] Computing divisors



On 19/10/13 05:20, Ognjen Maric wrote:
> How large are your numbers? If the memory from my crypto courses serves
> me well, trial division (you can go just up to the square root of n) is
> still the most efficient option for reasonably small numbers, e.g. 32-bit.

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.

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.

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.

Thanks for the replies

Cheers
Manuel




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