|
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.
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|