Re: [isabelle] Computing divisors



On 19/10/13 10:38, Ognjen Maric wrote:
> 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.
Well my point is that I am not looking for an algorithm to factorise an
integer, but to compute all its divisors. Divisors, not factors! The
prime factors of 10 are 2 and 5, its (positive) divisors are 1, 2, 5,
and 10. Of course, the divisor problem can be reduced to the
factorisation problem, which is why factorisation would also help me.

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

Ah yes, indeed they do. But, anyway, my focus of attention, as I already
said, is not on the factorisation, but on the "divisors" function:
http://hackage.haskell.org/package/arithmoi-0.4.0.3/docs/Math-NumberTheory-Primes-Factorisation.html#v:divisors
That is what I want, and as you can see, they compute a prime
factorisation and then compute the set of divisors from that. Which is
what I am planning to do in Isabelle now at some point.

Cheers,
Manuel




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