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

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

**Follow-Ups**:**Re: [isabelle] Computing divisors***From:*Manuel Eberl

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

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

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

- Previous by Date: Re: [isabelle] Computing divisors
- Next by Date: Re: [isabelle] Computing divisors
- Previous by Thread: Re: [isabelle] Computing divisors
- Next by Thread: Re: [isabelle] Computing divisors
- 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