## Re: [PrimeNumbers] Cubic, mod p

Expand Messages
• ... For a cubic with 3 roots, you will split A with 75% probability. Essentially, for your chosen a, you split the roots X_i into two groups: those for which
Message 1 of 11 , Nov 28, 2002
Phil Carmody wrote:
> I'd have thought that if there were 3 roots, then the final step should
> split A with a reasonable probability, and therefore that it shouldn't be
> considered too pessimal a case.

For a cubic with 3 roots, you will split A with 75% probability. Essentially,
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 quadratic
> case, so it might still be worth looking for other techniques.
> Marcel's Morain lead is still on the table for example.

In general, one would compute gcd(X^p-X,P(X)) not by "brute force"
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.
Your message has been successfully submitted and would be delivered to recipients shortly.