Bill Allombert on Mon, 23 Mar 2009 14:45:32 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: factor_add_primes logic |
On Mon, Mar 23, 2009 at 11:59:36AM +0100, Jeroen Demeyer wrote: > Dear pari-dev, > > using default(factor_add_primes,1) causes factor() to add large prime > factors found in factorizations, but only if the number to be factored > (after trial division) is not prime. > > In my opinion, there should be an option to make factor() add ALL big > primes found in factorizations, even if I do factor(nextprime(2^100)). Well that is called addprimes(nextprime(2^100)). > This could be done with a new value for the default, say > default(factor_add_primes,2). > > To motivate this, I see the following uses for factor_add_primes: > 1) Continuing an interrupted (CTRL-C) factorization. Current behaviour > works. That imply that factor_add_primes add primes as soon as they are found, not at the end of the factorisation. This reduce the amount of information factor_add_primes can use to decide to record a prime, especially since the factoring algorithm is recursive. > 2) Repeatedly doing the same factorization during a computation: say I > need to compute znorder(Mod(a,n)) for several a's with n fixed and I am > too lazy/stupid to give the factorization of n as an argument. Also > here, current behaviour works. There are also situation where PARI does not provide a way to pass the factorisation as input. > 3) Doing different factorizations but where the same prime factors occur > multiple times. Say P is a point on an elliptic curve and I want to > factor the denominator of [n]P where n varies. Here the current > behaviour is not optimal, it would be better to add every large prime > factor of the factorizations (even if the number-to-be-factored was > prime). Why not call addprimes directly ? > I would like to add that for uses 1) and 2) it would actually suffice to > add all but the largest prime factors of factorizations: if n has k > different large prime factors, only add k-1 of them. This would also be > consistent with the current behaviour for "factoring" primes, where no > prime is added. This is essentially what should happens, but frequently factor_add_primes does not know if it is at the bottom of the recursion and whether the primes found is actually the last. Patch welcome. The current behaviour is rather heuristic and attempt to record a minimal number of primes to avoid the addprimes table to grow uselessly large, slowing down further factorisations. It is meant to be used when calling functions that performs factorisation internally, to recover the factors. Such functioin might do al lot of factorisation beside the one we are interested in and we have to protect ourself against addprimes getting too large. Cheers, Bill.