*To*: Ognjen Maric <ognjen.maric at gmail.com>, isabelle-users at cl.cam.ac.uk*Subject*: Re: [isabelle] Computing divisors*From*: Manuel Eberl <eberlm at in.tum.de>*Date*: Sat, 19 Oct 2013 10:48:30 +0200*In-reply-to*: <526244FE.2070209@gmail.com>*References*: <5261A6A0.3040604@in.tum.de> <5261FA8F.2010705@gmail.com> <526231AC.3050509@in.tum.de> <526244FE.2070209@gmail.com>*User-agent*: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.0

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

**References**:**[isabelle] Computing divisors***From:*Manuel Eberl

**Re: [isabelle] Computing divisors***From:*Ognjen Maric

**Re: [isabelle] Computing divisors***From:*Manuel Eberl

**Re: [isabelle] Computing divisors***From:*Ognjen Maric

- Previous by Date: Re: [isabelle] Computing divisors
- Next by Date: Re: [isabelle] Recursion through Types
- Previous by Thread: Re: [isabelle] Computing divisors
- Next by Thread: [isabelle] Session-Graph too large?
- Cl-isabelle-users October 2013 archives indexes sorted by: [ thread ] [ subject ] [ author ] [ date ]
- Cl-isabelle-users list archive Table of Contents
- More information about the Cl-isabelle-users mailing list