A C implementation for computing Dixon resultants and solving polynomial systems over finite fields and ℚ.
FLINT (recommended version: 3.4.0) — Core arithmetic library for modular and polynomial computations.
PML (optional) — Accelerates prime field polynomial matrix operations when available.
DixonRes is free software distributed under the GNU General Public License, version 2.0 or later (GPLv2+).
All modes use the same binary ./dixon. 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
./dixon "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):
./dixon "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
./dixon --solve "polynomials" field_size ./dixon --solve-verbose "polynomials" field_size
Example
./dixon --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:
./dixon --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
./dixon --comp "polynomials" "eliminate_vars" field_size ./dixon -c "polynomials" "eliminate_vars" field_size
Example
./dixon --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 ./dixon --comp --omega 2.373 "polynomials" "eliminate_vars" field_size # Short form ./dixon -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
./dixon --field-equation "polynomials" "eliminate_vars" field_size ./dixon --field-equation -r "[d1,d2,...,dn]" field_size
Example
./dixon --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
./dixon --random "[d1,d2,...,dn]" field_size ./dixon -r "[d]*n" field_size ./dixon -r --solve "[d1,...,dn]" field_size ./dixon -r --comp "[d]*n" field_size
Examples
./dixon --random "[3,3,2]" 257 ./dixon -r "[3]*3" 0 ./dixon -r --solve "[2]*3" 257 ./dixon -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
./dixon "x + y^2 + t, x*y + t*y + 1" "x" 2^8
Custom polynomial (e.g., the AES field polynomial for GF(28)):
./dixon --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
./dixon --ideal "ideal_generators" "polynomials" "eliminate_vars" field_size ./dixon --ideal input_file
Example
./dixon \ --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.
./dixon example.dat ./dixon --solve system.dat ./dixon --comp system.dat ./dixon --ideal ideal.dat ./dixon --field-equation system.dat
257 # line 1: field size x+y+z # line 2+: polynomials (one per line or comma-separated) x*y+y*z+z*x x*y*z+1 x,y # last line: variables to eliminate
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.
DixonRes 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.
./dixon --solve "..." 257 ./dixon --solve "..." 65537 ./dixon --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 ./dixon "..." "x" 2^8 # Custom polynomial ./dixon --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. DixonRes reconstructs exact rational results from modular images.
./dixon "x^2+y^2+z^2-1, x^2+y^2-2*z^2, x+y+z" "x,y" 0 ./dixon --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 DixonRes
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 DixonRes repository
and in the v0.1.1 source archive. The DixonRes binary must be built and accessible before use.
Load the interface once per session and set the path to the dixon binary:
load("dixon_sage_interface.sage") set_dixon_path("./dixon") # set once; all subsequent calls use this path
set_dixon_path() sets a module-level default, so you never need to pass
dixon_path= explicitly unless you want to override it for a single call.
The current value can be read back with get_dixon_path().
Compute the Dixon resultant, eliminating the specified variables.
DixonResultant(F, elim_vars, field_size=None, dixon_path=None, finput="/tmp/dixon_in.dat", debug=False, timeout=600)
| Parameter | Description |
|---|---|
F | List of Sage polynomials and/or plain strings |
elim_vars | Variables to eliminate (Sage vars or strings) |
field_size | Prime, prime power, (p,k) tuple, GF(...) object, or 0 for ℚ. Inferred automatically from F[0].base_ring() if None. |
dixon_path | Path to binary; falls back to set_dixon_path() default if None |
debug | Print detailed diagnostics including input/output file contents |
timeout | Abort after this many seconds (default 600) |
Returns: resultant as a raw string, or None on failure.
# Basic resultant — field inferred from polynomial ring 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]) print(res)
Solve a polynomial system and enumerate all solutions.
DixonSolve(F, field_size=None, dixon_path=None, finput="/tmp/dixon_solve_in.dat", debug=False, timeout=600)
Returns:
list of dict — one {var_name: value_str} dict per solution[] — system has no solutions"infinite" — positive-dimensional (infinitely many solutions)None — failureR.<x, y, z> = GF(257)[] F = [x + y + z - 3, x*y + y*z + z*x - 3, x*y*z - 1] sols = DixonSolve(F) for s in sols: print(s)
Run complexity analysis without performing any polynomial arithmetic.
DixonComplexity(F, elim_vars, field_size=None, omega=None, dixon_path=None, finput="/tmp/dixon_comp_in.dat", debug=False, timeout=120)
Returns: a dict with keys complexity_log2, omega, bezout_bound, matrix_size, degrees, or None on failure.
info = DixonComplexity(F, [x, y]) print(info) # {'complexity_log2': 7.93, 'omega': 2.3, 'bezout_bound': 8, # 'matrix_size': 5, 'degrees': [1, 2, 3]}
Dixon resultant with triangular ideal reduction.
DixonIdeal(F, ideal_gens, elim_vars, field_size=None, dixon_path=None, debug=False, timeout=600)
ideal_gens is a list of strings of the form "a^3=2*b+1"
or equivalent Sage expressions. Returns the resultant string or None.
All functions accept field_size in any of these forms.
When field_size=None and F contains at least one Sage polynomial,
the base ring is inferred automatically.
| Value | Meaning |
|---|---|
None | Inferred from F[0].base_ring() |
257 or "257" | GF(257) |
(2, 8) | GF(28) |
"2^8" | GF(28) |
GF(257) | GF(257) object passed directly |
0 | Rational field ℚ |
load("dixon_sage_interface.sage") set_dixon_path("./dixon") 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]) sols = DixonSolve(F) info = DixonComplexity(F, [x, y]) print(res) print(sols) print(info)
The output of DixonResultant is a plain string and can be passed directly
as an element of F in a subsequent call. This enables variable-by-variable
elimination over large systems.
load("dixon_sage_interface.sage") set_dixon_path("./dixon") R.<x, y, z> = GF(17)[] f1 = x + y + z f2 = x*y + y*z + z*x + 1 f3 = y*z - 1 f4 = z - 2 res1 = DixonResultant([f1, f2], [x]) res2 = DixonResultant([res1, f3], [y]) res3 = DixonResultant([res2, f4], [z]) print("res1 =", res1) print("res2 =", res2) print("res3 =", res3)
Pass debug=True to any function to print the input file, command, and raw output for diagnosis:
res = DixonResultant(F, [x, y], debug=True)
| Function | Description |
|---|---|
set_dixon_path(path) | Set the default path to the dixon binary |
get_dixon_path() | Return the currently configured default path |
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 |
DixonRes 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, DixonRes will detect and use it automatically at configure time for prime field systems.
git clone https://github.com/DixonRes/DixonRes cd DixonRes ./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:
./dixon --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.