# Polynomial System Solving

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={\bf F}_{q}$. The algorithm has several applications, including algebraic attacks on multivariate polynomial cryptosystems defined over finite fields (including the important case of ${\bf F}_{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 $q^e$ 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.

## `Variety(I): RngMPol -> [ ModTupFldElt ]`

```magma
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.

## `VarietySize(I): RngMPol -> RngIntElt`

```magma
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$.