Bill Allombert on Mon, 23 Mar 2009 23:59:16 +0100

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: factor_add_primes logic

On Mon, Mar 23, 2009 at 03:08:43PM +0100, Jeroen Demeyer wrote:
> Bill Allombert wrote:
>> On Mon, Mar 23, 2009 at 11:59:36AM +0100, Jeroen Demeyer wrote:
>>> 1) Continuing an interrupted (CTRL-C) factorization. Current 
>>> behaviour  works.
>>> 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.
>>> 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 ?
> Of course this can be done but then what is the point of  
> factor_add_primes?  The current factor_add_primes supports

The point of factor_add_primes as you described, scenarii 1 and 2.

> scenarios 1 and 2 that I wrote above but not 3.  Since it looks easy to  
> also support scenario 3, I think it should be done.

Before adding an extra interface to PARI/GP I would like to understand
what is the use-case that is not handled by addprimes.

The interface of factor_add_primes is far from perfect as it stands, 
and I would like to see use-cases to improve it rather than add another
interface with potentially other issues with use-cases.