Re: [PrimeNumbers] Cubic, mod p
- Phil Carmody wrote:
> I'd have thought that if there were 3 roots, then the final step shouldFor a cubic with 3 roots, you will split A with 75% probability. Essentially,
> split A with a reasonable probability, and therefore that it shouldn't be
> considered too pessimal a case.
for your chosen a, you split the roots X_i into two groups: those for which
(X_i+a) is a quadratic residue (mod p) and those for which it is not. The
chance that all 3 roots will fall on the same side of the fence would be 1/4.
> The original expmod/GCD looks quite expensive compared to the quadraticIn general, one would compute gcd(X^p-X,P(X)) not by "brute force"
> case, so it might still be worth looking for other techniques.
> Marcel's Morain lead is still on the table for example.
but by computing X^p modulo P(X) using a modular exponentiation algorithm.
Then subtract X and do the gcd. It's not terribly expensive in either
time or space; the space required is O(P(X)), and the time required using
a naive polynomial multiplication algorithm is O(log(p)*degree(P(X))^2).
In the cubic case, degree(P(X))^2 is quite manageable.