Re: [isabelle] Computing divisors



On 10/18/2013 11:22 PM, Manuel Eberl wrote:
> I should probably add that I am, of course, perfectly aware that there
> is no known algorithm for integer factorisation in polynomial time,
> which, if I am not mistaken, implies that there is also no known
> algorithm for computing the divisors of an integer in polynomial time;
> by "efficient", I therefore mean, as it were, "not unnecessarily
> inefficient". I am not looking for anything overly fancy such as number
> field sieves, just something slightly better than trial division with
> all integers from 1 to n.

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.

Cheers,
Ognjen




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