A fully parallel distributed algorithm has been developed for V2.28 for the solving of a multivariate polynomial system over a moderately small finite field K=GF(q). The algorithm has several applications, including algebraic attacks on multivariate polynomial cryptosystems defined over finite fields (including the important case of GF(2), and also some types of computations in the arithmetic geometry of schemes over finite fields, where the point counting on schemes often arises.
The algorithm is an extension of the existing algorithm to compute the variety of an ideal: it is given a small integer parameter e and works by evaluating the input polynomials at the last e variables to all possible constants in K (so there are qe cases enumerated) and then computing the variety of each simplified ideal and combining all the results.
As usual, one first uses SetNthreads and optionally StartWorkers to select the number of cores/workers. Then the algorithm itself is called by creating an ideal I of a multivariate polynomial ring over a small finite field K and then by calling one of the following functions.
Eval: RngIntElt Default:
Assuming the parameter Eval is set to a small positive integer e, return the variety of I using the algorithm where e variables are set to all elements of the base finite field K.Note that a Gröbner basis (GB) for I typically should not be first created (explicitly or implicitly), since that may be extremely expensive to compute in hard examples, and the main point of the evaluation-based algorithm is to avoid the computation of the GB of the original ideal with all variables.
Eval: RngIntElt Default:
Assuming the parameter Eval is set to a small positive integer e, return the size of the variety of I using the algorithm where e variables are set to all elements of the base finite field K.