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+).
All modes use the same binary ./drsolve. Command-line runs write
timestamped solution_YYYYMMDD_HHMMSS.dat or
comp_YYYYMMDD_HHMMSS.dat; file input writes
example_solution.dat or example_comp.dat.
Eliminates variables from a polynomial system and returns the resultant in the remaining variables.
Syntax
./drsolve "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.
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 .dat 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 --solve "polynomials" field_size ./drsolve --solve-verbose "polynomials" field_size
Example
./drsolve --solve "x^2 + y^2 + z^2 - 6, x + y + z - 4, x*y*z - x - 1" 257
--solve prints a concise summary with candidate sets and verified solutions.
--solve-verbose keeps the full elimination and back-substitution log.
Variables are auto-detected from the input expressions.
Use --silent to suppress console output while still writing the solution file:
./drsolve --silent --solve "..." 257
field_size=0 and for very large prime fallback fields beyond the nmod limit.Estimates the difficulty of a Dixon resultant computation without performing any polynomial arithmetic. The tool parses the input, then reports:
log₂(d · Sω), where S is the matrix size and ω is the matrix-multiplication exponentSyntax
./drsolve --comp "polynomials" "eliminate_vars" field_size ./drsolve -c "polynomials" "eliminate_vars" 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
Sample console output
=== Complexity Analysis === Equations: 3 | Variables: 3 | Eliminate: 2 All vars : x, y, z Degrees : [2, 2, 2] Bezout bound : 8 Dixon matrix size : 5 Resultant deg est : 8 (Bezout bound) Complexity (log2) : 7.9254 (omega=2.3) Report saved to : comp_20260319_192716.dat ===========================
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
--silent, --comp, and --omega can be combined freely.
| Input method | Output file |
|---|---|
| Command-line arguments | comp_YYYYMMDD_HHMMSS.dat |
File input example.dat | example_comp.dat |
The report file contains all of the above fields plus the omega value used.
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-eqution for compatibility.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 --solve "[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 --solve "[2]*3" 257 ./drsolve -r --comp --omega 2.373 "[4]*4" 257
x0, x1, … and write the same solution/complexity files as manual input.--comp, but not with --solve.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 --solve "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 input_file
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 .dat file instead of inline arguments for scripted or batch use.
./drsolve example.dat ./drsolve --solve system.dat ./drsolve --comp system.dat ./drsolve --ideal ideal.dat ./drsolve --field-equation system.dat
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.dat |
|---|---|---|
| Dixon / Solver | solution_YYYYMMDD_HHMMSS.dat | example_solution.dat |
| Complexity | comp_YYYYMMDD_HHMMSS.dat | example_comp.dat |
--ideal and --field-equation also use the solution filename pattern.
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 --solve "..." 257 ./drsolve --solve "..." 65537 ./drsolve --solve "..." 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.--solve, --comp, --random, --ideal, and --field-equation are not available there 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 --solve "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
--comp only. --solve, --ideal, and --field-equation are not implemented over ℚ 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 |
| ℚ | 0 | Basic Dixon resultant and --comp |
dixon_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.
dixon_sage_interface.sage is included in the DRsolve repository.
The DRsolve binary must be built and accessible before use.
load("dixon_sage_interface.sage") set_dixon_path("./drsolve") # set once per session
| Function | Description | Returns |
|---|---|---|
DixonResultant(F, elim_vars, ...) |
Compute the Dixon resultant, 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 |
All functions accept optional debug=True (prints diagnostics) and timeout (seconds). The field_size argument accepts an integer, "p^k" string, GF(...) object, or 0 for ℚ.
load("dixon_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 = DixonResultant(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 DixonResultant 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 = DixonResultant([x+y+z, x*y+y*z+z*x+1], [x]) res2 = DixonResultant([res1, y*z-1], [y]) res3 = DixonResultant([res2, z-2], [z]) print(res3)
| Function | Description |
|---|---|
set_dixon_path(path) / get_dixon_path() | Set / get the default path to the dixon 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 |
DRsolve requires FLINT 3.4.0 or later. PML is optional but recommended for prime field performance.
Get FLINT 3.4.0 or newer from github.com/flintlib/flint and follow its build instructions for your platform.
Get PML from github.com/vneiger/pml. If present, DRsolve will detect and use it automatically at configure time for prime field systems.
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 --solve "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 | ≥ 3.4.0 | github.com/flintlib/flint |
| PML | No | latest | 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.
Bug fixes & compilation improvements only. No performance or functional changes.
CRYPTO 2026 paper submission version. Includes a FLINT-based C implementation of Dixon resultants and a finite-field polynomial system solver, with CLI/file input and automatic solution outputs.