Jeroen Demeyer on Mon, 23 Mar 2009 16:09:26 +0100

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

Re: factor_add_primes logic

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 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.