What is it?

Algebraeon is a computational algebra system (CAS) written purely in Rust. It implements algorithms for working with matrices, polynomials, algebraic numbers, factorizations, etc. The focus is on exact algebraic computations over approximate numerical solutions. Algebraeon is in early stages of development and the API subject to change. Algebraeon uses Malachite under the hood for arbitrary sized integer and rational numbers.

There is a for informal discussions about Algebraeon. Contributions are welcome.

As a Rust Library

This is the repository for Algebraeon as a Rust library.

• User Guide
• Published to crates.io
• Documentation for the latest release

As a Python Library

Algebraeon can also be used as a Python library, though it is not fully featured in that case.

• GitHub
• User Guide

Examples

Factoring Integers

To factor large integers using Algebraeon

use algebraeon::structures::Natural;
use algebraeon::rings::structure::{MetaFactoringMonoid, UniqueFactorizationMonoidSignature};
use algebraeon::structures::ToStringSignature;
use std::str::FromStr;

let n = Natural::from_str("706000565581575429997696139445280900").unwrap();
let f = n.clone().factor();
println!(
    "{} = {}",
    n,
    Natural::structure_ref().factorizations().to_string(&f)
);
/*
Output:
    706000565581575429997696139445280900 = 2^2 × 5^2 × 6988699669998001 × 1010203040506070809
*/

Algebraeon implements Lenstra elliptic-curve factorization for quickly finding prime factors with around 20 digits.

Factoring Polynomials

Factor the polynomials $x^2 - 5x + 6$ and $x^{15} - 1$.

use algebraeon::rings::{parsing::parse_integer_polynomial, structure::MetaFactoringMonoid};

let f = parse_integer_polynomial("x^2 - 5*x + 6", "x").unwrap();
println!("{} = {}", f, f.factor());
/*
Output:
    λ^2-5λ+6 = 1 * (λ-2) * (λ-3)
*/

let f = parse_integer_polynomial("x^15 - 1", "x").unwrap();
println!("{} = {}", f, f.factor());
/*
Output:
    λ^15-1 = 1 * (λ-1) * (λ^2+λ+1) * (λ^4+λ^3+λ^2+λ+1) * (λ^8-λ^7+λ^5-λ^4+λ^3-λ+1)
*/

so

$$x^2 - 5x + 6 = (x-2)(x-3)$$ $$x^{15}-1 = (x-1)(x^2+x+1)(x^4+x^3+x^2+x+1)(x^8-x^7+x^5-x^4+x^3-x+1)$$

Linear Systems of Equations

Find the general solution to the linear system

$$a \begin{pmatrix}3 \\ 4 \\ 1\end{pmatrix} + b \begin{pmatrix}2 \\ 1 \\ 2\end{pmatrix} + c \begin{pmatrix}1 \\ 3 \\ -1\end{pmatrix} = \begin{pmatrix}5 \\ 5 \\ 3\end{pmatrix}$$

for integers $a$, $b$ and $c$.

use algebraeon::structures::Integer;
use algebraeon::rings::linear::finitely_free_module::RingToFinitelyFreeModuleSignature;
use algebraeon::rings::matrix::Matrix;
use algebraeon::structures::MetaType;

let m = Matrix::<Integer>::from_rows(vec![vec![3, 4, 1], vec![2, 1, 2], vec![1, 3, -1]]);
let y = vec![5.into(), 5.into(), 3.into()];
for x in Integer::structure()
    .free_module(3)
    .affine_subsets()
    .affine_basis(&m.row_solution_set(&y))
{
    println!("{:?}", x);
}
/*
Output:
    [Integer(0), Integer(2), Integer(1)]
    [Integer(1), Integer(1), Integer(0)]
*/

so two solutions are given by $(a, b, c) = (0, 2, 1)$ and $(a, b, c) = (1, 1, 0)$ and every solution is a linear combination of these two solutions; The general solution is given by all $(a, b, c)$ such that

$$\begin{pmatrix}a \\ b \\ c\end{pmatrix} = s\begin{pmatrix}0 \\ 2 \\ 1\end{pmatrix} + t\begin{pmatrix}1 \\ 1 \\ 0\end{pmatrix}$$

where $s$ and $t$ are integers such that $s + t = 1$.

Complex Root Isolation

Find all complex roots of the polynomial $$f(x) = x^5 + x^2 - x + 1$$

use algebraeon::rings::parsing::parse_integer_polynomial;

let f = parse_integer_polynomial("x^5 + x^2 - x + 1", "x").unwrap();
// Find the complex roots of f(x)
for root in f.all_complex_roots() {
    println!("root {} of degree {}", root, root.degree());
}

/*
Output:
    root ≈-1.328 of degree 3
    root ≈0.662-0.559i of degree 3
    root ≈0.662+0.559i of degree 3
    root -i of degree 2
    root i of degree 2
*/

Despite the output, the roots found are not numerical approximations. Rather, they are stored internally as exact algebraic numbers by using isolating boxes in the complex plane and isolating intervals on the real line.