Jeroen Demeyer on Mon, 23 Mar 2009 12:28:55 +0100

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

factor_add_primes logic

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

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.

What do you think?