Re: factor_add_primes logic

[Bill Allombert <Bill.Allombert@math.u-bordeaux1.fr>]

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.