Binary univariate polynomial algebra
This repo is highly inspired from https://gist.github.com/mildsunrise/e21ae2b1649532813f2594932f9e9371, and https://github.com/uranix/factormod
Installation
On your project's directory, run the following command:
Usage
Polynomial creation
You can create a BinaryPolynomial
from BigUint
, where the least significant bit is the lowest degree coefficient.
use BigUint;
use BinaryPolynomial;
let polynomial = from; // or 0b1101u32
assert_eq!;
You can also create a BinaryPolynomial
from a Vec<bool>
, where the first element is the highest degree coefficient.
use BinaryPolynomial;
let polynomial = from;
assert_eq!;
Or from a &str
:
use BinaryPolynomial;
let polynomial = try_from.unwrap;
assert_eq!;
Finally, you can create the null or unitary BinaryPolynomial:
use BinaryPolynomial;
use One;
use Zero;
let polynomial = zero;
assert_eq!;
let polynomial = one;
assert_eq!;
Non-zero polynomial
Some functions require a NonZeroBinaryPolynomial
argument, you can create it from a BinaryPolynomial
:
use BinaryPolynomial;
use NonZeroBinaryPolynomial;
use Zero;
let zero_polynomial = zero;
let try_non_zero_polynomial = new;
assert!;
let non_zero_polynomial = from;
let non_zero_polynomial = new.unwrap;
assert!;
Example
Polynomial inversion modulo a non-zero polynomial:
use BinaryPolynomial;
use NonZeroBinaryPolynomial;
let polynomial = new.unwrap;
let modulo = new.unwrap;
let inverse = polynomial.inv_mod;
assert!; // Inverse exists
assert_eq!;
Operators
You can use the following operators:
Operator | operand 1 | operand 2 | Description |
---|---|---|---|
+ |
BinaryPolynomial |
BinaryPolynomial |
Polynomial addition(equivalent to XOR) |
* |
BinaryPolynomial |
BinaryPolynomial |
Polynomial multiplication(without modulo, use mul_mod for modular multiplication) |
* |
NonZeroBinaryPolynomial |
NonZeroBinaryPolynomial |
Polynomial multiplication(without modulo, use mul_mod for modular multiplication) |
% |
BinaryPolynomial |
NonZeroBinaryPolynomial |
Polynomial modulo |
/ |
BinaryPolynomial |
NonZeroBinaryPolynomial |
Polynomial division(returns quotient) |
pow |
BinaryPolynomial |
usize |
Polynomial exponentiation(without modulo, use pow_mod for modular exponentiation) |
Available operations
div_mod(BinaryPolynomial, modulo: NonZeroBinaryPolynomial)
Returns quotient and modulo
mul_mod(BinaryPolynomial, BinaryPolynomial, modulo: NonZeroBinaryPolynomial)
Multiplication modulo
pow_mod(BinaryPolynomial, BinaryPolynomial, modulo: NonZeroBinaryPolynomial)
Exponentiation modulo
congruent_mod(BinaryPolynomial, BinaryPolynomial, modulo: NonZeroBinaryPolynomial)
Check if polynomials are congruent modulo
derivative(BinaryPolynomial)
Returns polynomial derivative
coprime(NonZeroBinaryPolynomial, NonZeroBinaryPolynomial)
Check if two polynomials are coprime
gcd(NonZeroBinaryPolynomial, NonZeroBinaryPolynomial)
Returns greatest common divisor of two polynomials
egcd(NonZeroBinaryPolynomial, NonZeroBinaryPolynomial)
Returns extended greatest common divisor of two polynomials
inv_mod(NonZeroBinaryPolynomial, modulo: NonZeroBinaryPolynomial)
Returns modular inverse of a polynomial
is_irreducible(NonZeroBinaryPolynomial)
Check if polynomial is irreducible using Rabin's irreducibility test
is_primitive(NonZeroBinaryPolynomial)
Check if polynomial is primitive
irreducible_factors(NonZeroBinaryPolynomial)
Compute irreducible factors of polynomial using Berlekamp's algorithm
square_free_irreducible_factors(NonZeroBinaryPolynomial)
Compute irreducible factors of square free polynomial
is_square_free(NonZeroBinaryPolynomial)
Check if polynomial is square free