Loading ...
Sorry, an error occurred while loading the content.
 

Re: [PrimeNumbers] Cubic, mod p

Expand Messages
  • Jack Brennen
    ... 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.