A C implementation for computing Dixon resultants and solving polynomial systems over finite fields and ℚ.
FLINT (recommended version: 3.5.0) — Core arithmetic library for modular and polynomial computations.
PML (built in) — Accelerates prime field polynomial matrix operations when available.
DRSolve is free software distributed under the GNU General Public License, version 2.0 or later (GPLv2+).
Eliminates variables from a polynomial system and returns the resultant in the remaining variables.
Syntax
./drsolve "polynomials" "eliminate_vars" field_size ./drsolve -o output.dr "polynomials" "eliminate_vars" field_size
field_size may be a prime such as 257, an extension field such as 2^8,
a custom extension field such as "2^8: t^8+t^4+t^3+t+1", or 0 for ℚ.
The number of eliminated variables must equal the number of equations minus one.
--dixon, --macaulay, and --subres are available.
For convenience, 2 equations with 1 elimination variable auto-enable --subres, while standard 3/4-equation Dixon cases auto-enable the fast recursive Dixon construction unless a method is selected explicitly.
Example — eliminate x and y from a 3-polynomial system over GF(257):
./drsolve "x+y+z, x*y+y*z+z*x, x*y*z+1" "x,y" 257
Output: the resultant polynomial in z, written to a solution .dr file. This is also the mode used for very large prime fields beyond the nmod limit.
Solves a well-determined system of n equations in n unknowns and enumerates all solutions over the given field.
Syntax
./drsolve "polynomials" field_size ./drsolve -s "polynomials" field_size ./drsolve -v 2 -s "polynomials" field_size
Example
./drsolve -s "x^2 + y^2 + z^2 - 6, x + y + z - 4, x*y*z - x - 1" 257
-s is the short form of solver mode, while plain ./drsolve "polynomials" field_size
also auto-enters solver mode. -v 0 is silent, -v 1 is the default output level,
-v 2 keeps the full elimination/debug log, and -v 3 also dumps small intermediate matrices. Variables are auto-detected from the input expressions.
Use -v 0 to suppress console output while still writing the solution file:
./drsolve -v 0 -s "..." 257
--solve, --solve-verbose, and --silent are still accepted for compatibility. For field_size=0, you can also use --solve-rational-only to keep only exact rational solutions.Estimates the difficulty of a Dixon resultant computation without performing any polynomial arithmetic. The tool parses the input, then reports:
Syntax
./drsolve --comp "polynomials" "eliminate_vars" field_size ./drsolve -c "polynomials" "eliminate_vars" field_size ./drsolve -r -c "[d]*n" field_size ./drsolve -c -r "[d]*n" field_size
Example
./drsolve --comp "x^3+y^3+z^3, x^2*y+y^2*z+z^2*x, x+y+z-1" "x,y" 257
./drsolve -c -r "[4]*4" 257
Sample console output
=== Complexity Analysis === --- Step 1/2 --- Step 1/2 direct multivariate cofactor expansion (naive, log2): ... Step 1/2 Kronecker + HNF (log2): ... Step 1/2 recursive block Dixon construction (Zhao/Qin surrogate, log2): ... Best Step 1/2 estimate: ... --- Step 4 --- Step 4 HNF (log2, omega=2.81): ... Step 4 ordinary dense interpolation (log2): ... Best Step 4 estimate: ... --- Overall --- Overall complexity = max(step1/2, step4) (log2): ... ===========================
The complexity formula uses a matrix-multiplication exponent ω (default: 2.3).
Set a custom value with --omega (or -w):
# Theoretical bound ω ≈ 2.373 ./drsolve --comp --omega 2.373 "polynomials" "eliminate_vars" field_size # Short form ./drsolve -c -w 2.0 "polynomials" "eliminate_vars" field_size
-v, --comp, --omega, and -o can be combined freely.
-r -c or -r --comp to estimate a generated system without computing its resultant.
--comp, -v 0 prints only the final overall complexity, -v 1 prints the per-step / per-method summary, -v 2 adds formulas and parameter values, and -v 3 adds extra detail.
| Input method | Output file |
|---|---|
| Command-line arguments | comp_YYYYMMDD_HHMMSS.dr |
File input example.dr | example_comp.dr |
The report file contains all of the above fields plus the omega value used.
DRsolve currently supports prime fields, extension fields, and ℚ. Arithmetic uses FLINT throughout, with optional PML acceleration for suitable prime-field computations.
Specify a prime field as a plain integer such as 257. For primes within the standard nmod backend, all finite-field modes are available.
./drsolve -s "..." 257 ./drsolve -s "..." 65537 ./drsolve -s "..." 4294967311
When the optional PML library is installed and detected at configure time, polynomial matrix operations are automatically accelerated for well-determined prime field systems.
nmod limit, the current release still computes Dixon resultants by reconstructing over ℚ and then reducing modulo the target prime.nmod limit, solver mode is available, but --comp, --random, --ideal, and --field-equation are not available yet.Specify an extension field as p^k. The generator is t by default, and FLINT's built-in irreducible polynomial is used unless a custom one is provided.
# FLINT default polynomial ./drsolve "..." "x" 2^8 # Custom polynomial ./drsolve -s "x^2+t*y, x*y+t^2" "2^8: t^8 + t^4 + t^3 + t + 1"
nmod limit are not supported in the current release.Use field_size=0 to work over the rationals. DRsolve reconstructs exact rational results from modular images.
./drsolve "x^2+y^2+z^2-1, x^2+y^2-2*z^2, x+y+z" "x,y" 0 ./drsolve --comp "x^3+y^3+z^3, x^2*y+y^2*z+z^2*x, x+y+z-1" "x,y" 0 ./drsolve -s "x^2+y^2-5, x-y-1" 0
--comp, and solver mode are supported. --ideal and --field-equation are not implemented there yet.| Field type | Example argument | Current status |
|---|---|---|
Prime field within nmod range | 257 | All main modes available |
| Very large prime field | 340282366920938463463374607431768211507 | Basic Dixon resultant only |
| GF(28) | 2^8 | FLINT default irreducible polynomial |
| GF(28) with AES polynomial | "2^8: t^8+t^4+t^3+t+1" | Custom polynomial supported |
| GF(35) | 3^5 | Extension field with FLINT default polynomial |
| Q | 0 | Basic Dixon resultant, --comp, and solver mode |
After each multiplication, reduces x^q -> x for every variable. This can be useful for finite-field systems where field equations should be enforced throughout the computation.
Syntax
./drsolve --field-equation "polynomials" "eliminate_vars" field_size ./drsolve --field-equation -r "[d1,d2,...,dn]" field_size
Example
./drsolve --field-equation "x0*x2+x1, x0*x1*x2+x2+1, x1*x2+x0+1" "x0,x1" 2
field_size=0 or for the current large-prime fallback mode.Generates a random polynomial system from a degree list, then runs the selected computation mode on the generated system.
Syntax
./drsolve --random "[d1,d2,...,dn]" field_size ./drsolve -r "[d]*n" field_size ./drsolve -r -n 4 --density 0.5 "[d]*3" field_size ./drsolve -r -s "[d1,...,dn]" field_size ./drsolve -r --comp "[d]*n" field_size
Examples
./drsolve --random "[3,3,2]" 257 ./drsolve -r "[3]*3" 0 ./drsolve -r -n 4 --density 0.5 "[3]*3" 257 ./drsolve -r --seed 12345 "[3]*3" 257 ./drsolve -r -s "[2]*3" 257 ./drsolve -r --comp --omega 2.373 "[4]*4" 257
x0, x1, … and write the same solution/complexity files as manual input.--seed <num> makes random generation reproducible across runs. This is useful for benchmarks, bug reports, and paper examples.Specify the field as p^k. The generator variable is t by default, and the current CLI prints the irreducible polynomial chosen by FLINT unless a custom polynomial is provided.
Default polynomial
./drsolve "x + y^2 + t, x*y + t*y + 1" "x" 2^8
Custom polynomial (e.g., the AES field polynomial for GF(28)):
./drsolve -s "x^2 + t*y, x*y + t^2" "2^8: t^8 + t^4 + t^3 + t + 1"
| Field | Argument |
|---|---|
| GF(28) default | 2^8 |
| GF(28) AES polynomial | "2^8: t^8+t^4+t^3+t+1" |
| GF(35) default | 3^5 |
| GF(35) custom | "3^5: t^5+2*t+1" |
Reduces the polynomial system modulo a triangular ideal before computing the Dixon resultant. Useful for structured systems such as those arising from block cipher analysis.
Syntax
./drsolve --ideal "ideal_generators" "polynomials" "eliminate_vars" field_size ./drsolve --ideal -f input.dr ./drsolve --ideal -f input.dr -o output.dr
Example
./drsolve \ --ideal \ "a2^3=2*a1+1, a3^3=a1*a2+3" \ "a1^2+a2^2+a3^2-10, a3^3-a1*a2-3" \ "a3" \ 257
= are parsed as ideal generators and the remaining non-empty lines are parsed as system polynomials.field_size=0 or for the current large-prime fallback mode.Pass a .dr file instead of inline arguments for scripted or batch use. The input file may be given directly or with -f; use -o to choose the output file.
./drsolve example.dr ./drsolve -f example.dr ./drsolve -s -f system.dr -o output.dr ./drsolve --comp -f system.dr ./drsolve --ideal -f ideal.dr ./drsolve --field-equation -f system.dr
x,y # line 1: variables to eliminate 257 # line 2: field size x*y+y*z+z*x x*y*z+1 x+y+z # last 3+: polynomials (one per line or comma-separated)
257 # line 1: field size x^2 + y^2 + z^2 - 6 # line 2+: n equations in n variables x + y + z - 4 x*y*z - x - 1
257 # line 1: field size a2^3=2*a1+1 # lines 2..n-1 with '=' are ideal generators a3^3=a1*a2+3 a1^2+a2^2+a3^2-10 # lines 2..n-1 without '=' are system polynomials a3^3-a1*a2-3 a3 # last line: variables to eliminate
| Mode | Command-line input | File input example.dr |
|---|---|---|
| Dixon / Solver | solution_YYYYMMDD_HHMMSS.dr | example_solution.dr |
| Complexity | comp_YYYYMMDD_HHMMSS.dr | example_comp.dr |
--ideal and --field-equation also use the solution filename pattern. If -o is given, that filename is used instead.
drsolve_sage_interface.sage is a thin wrapper that lets you call DRsolve
directly from a SageMath session. Polynomials are passed as native Sage objects;
the interface handles serialisation, subprocess invocation, and output parsing automatically.
drsolve_sage_interface.sage is included in the DRsolve repository.
The DRsolve binary must be built and accessible before use.
load("drsolve_sage_interface.sage") set_dixon_path("./drsolve") # set once per session
| Function | Description | Returns |
|---|---|---|
DixonRes(F, elim_vars, ...)DixonResultant(F, elim_vars, ...) |
Compute the resultant while eliminating the specified variables. field_size is inferred from the polynomial ring if not given. |
Resultant as a string, or None |
DixonSolve(F, ...) |
Solve a polynomial system and enumerate all solutions. | List of {var: value} dicts; [] if none; "infinite" if positive-dimensional |
DixonComplexity(F, elim_vars, ...) |
Estimate complexity without running any polynomial arithmetic. | Dict with complexity_log2, bezout_bound, matrix_size, etc. |
DixonIdeal(F, ideal_gens, elim_vars, ...) |
Dixon resultant with triangular ideal reduction. ideal_gens is a list of strings like "a^3=2*b+1". |
Resultant as a string, or None |
set_dixon_path(path)get_dixon_path() |
Set or query the default path to the drsolve executable. |
Path string or None |
The helper writers ToDixon(...), ToDixonSolver(...), and ToDixonIdeal(...) are also available when you want to generate input files without running the binary.
| Option | Meaning |
|---|---|
field_size | Integer prime, extension-field string such as "2^8" or "2^8: t^8+t^4+t^3+t+1", Sage GF(...) object, or 0 for ℚ. If omitted, inferred from the Sage polynomial ring when possible. |
verbosity=0..3 | Pass -v to drsolve. If omitted, the interface leaves the CLI default unchanged. |
time=True | Pass --time. |
threads=n | Pass --threads n. |
method, step1, step4 | Select the determinant / recursive Dixon strategy. |
resultant_method | One of "dixon", "macaulay", or "subres". |
field_equation=True | Enable field-equation reduction. |
fast_ksy, fast_ksy_col | Control the method-5 KSY precondition options. |
rational_root_scan | Solver-only option: "auto", "off", or "force". |
rational_only=True | Solver-only option for exact rational solutions over field_size=0. |
debug=True | Print wrapper-level diagnostics such as the command line and output-file parsing status. |
live_output=True | Stream drsolve stdout/stderr directly to the Sage terminal while the subprocess runs. |
timeout | Abort the subprocess after the given number of seconds. |
load("drsolve_sage_interface.sage") set_dixon_path("./drsolve") R.<x, y, z> = GF(257)[] F = [x + y + z - 3, x*y + y*z + z*x - 3, x*y*z - 1] res = DixonRes(F, [x, y]) # eliminate x, y sols = DixonSolve(F) # enumerate all solutions info = DixonComplexity(F, [x, y]) # complexity estimate print(res, sols, info)
The output of DixonRes is a plain string and can be fed directly into the next call, enabling variable-by-variable elimination over large systems.
R.<x, y, z> = GF(17)[] res1 = DixonRes([x+y+z, x*y+y*z+z*x+1], [x]) res2 = DixonRes([res1, y*z-1], [y]) res3 = DixonRes([res2, z-2], [z]) print(res3)
R.<x, y, z> = GF(257)[] F = [x + y + z - 3, x*y + y*z + z*x - 3, x*y*z - 1] res_macaulay = DixonRes(F, [x, y], resultant_method="macaulay", verbosity=2) res_fast = DixonRes(F, [x, y], method=5, fast_ksy=True, fast_ksy_col=0, time=True) sols = DixonSolve(F, verbosity=3, live_output=True) print(res_macaulay) print(res_fast) print(sols)
R.<x0, x1, x2> = GF(257)[] F = [x0^2 + x1^2 + x2^2 - 10, x2^3 - x0*x1 - 3] I = ["x1^3=2*x0+1", "x2^3=x0*x1+3"] res = DixonIdeal(F, I, [x2], verbosity=2, time=True) print(res)
K.<z8> = GF(2^8, modulus=x^8 + x^4 + x^3 + x + 1) R.<x, y> = PolynomialRing(K, 2) F = [x^2 + z8*y + 1, x*y + z8^2] res = DixonRes(F, [y], field_size=K) sols = DixonSolve(F, field_size=K) RQ.<u, v> = QQ[] G = [u^2 - 1, v - u] rat = DixonSolve(G, field_size=0, rational_only=True) print(res) print(sols) print(rat)
| Function | Description |
|---|---|
set_dixon_path(path) / get_dixon_path() | Set / get the default path to the drsolve binary |
ToDixon(F, elim_vars, field_size, finput) | Write a Dixon/complexity input file without running the binary |
ToDixonSolver(F, field_size, finput) | Write a solver input file without running the binary |
ToDixonIdeal(F, ideal_gens, elim_vars, field_size, finput) | Write an ideal-reduction input file without running the binary |
DRsolve is built on FLINT and ships with the PML code it uses. FLINT 3.5.0 is the recommended version.
Install FLINT first. The upstream repository is github.com/flintlib/flint; the current recommended version is 3.5.0.
git clone https://github.com/flintlib/flint.git cd flint ./bootstrap.sh ./configure make make install
The PML code used by DRsolve is already built into the source tree. You do not need to clone or install a separate PML package just to build DRsolve.
git clone https://github.com/drsolve/drsolve cd drsolve ./configure make make check # optional make install # optional
For additional build options:
./configure --help make help
Run a quick test to confirm the build is working:
./drsolve -s "x + y - 3, x*y - 2" 257
Expected: solutions [x=1, y=2] and [x=2, y=1] over GF(257).
| Component | Required | Version | Link |
|---|---|---|---|
| FLINT | Yes | recommended 3.5.0 | github.com/flintlib/flint |
| PML | Built in | bundled with DRsolve | github.com/vneiger/pml |
| C compiler | Yes | C11 or later | gcc / clang |
Pre-built source archives for each release. Build instructions are on the Install page.
Asiacrypt 2026 paper submission version.
CRYPTO 2026 paper submission version.
A C implementation of Dixon resultants for solving polynomial systems over finite fields, built on FLINT. Provides command-line and file-based input with automated solution output.