Cyclic

A simple, complete, and dependency-free modular arithmetic library.

lib.rs:

Simple library for generic cyclic groups, rings of integers, and prime fields. Rather than providing single operations like modular exponentiation or modular division, Cyclic provides type-safe ring-valued integers that work the way you expect.

Because of its reliance on const generics and compile-time computing for primality checking, Cyclic currently only builds with the nightly toolchain.

Examples

Using Cyclic is easy: the crate provides a macro, res!, that takes an unsigned integer and produces its residue class.

use cyclic::res;
const N: u32 = 7;

let r = res![3; N];
assert_eq!(r.0, 3);

let s = res![11; N];
assert_eq!(s.0, 4);

assert_eq!(r + s, res![0; N]);
assert_eq!(r - s, res![6; N]);
assert_eq!(r * s, res![5; N]);
assert_eq!(r / s, res![6; N]);

assert_eq!(res![2; 3].pow(1_000_000), res![1; 3])

The following code, on the other hand, will fail to compile:

use cyclic::res;
let r = res![1; 6] + res![4; 12];

Attempted division in a ring of composite order will panic:

use cyclic::res;
let r = res![2; 4] / res![3; 4];

The primality of the modulus is checked at compile time, so this incurs no runtime cost.

Crate Feature Flags

• composite_order_division: enabling this feature suppresses panics when dividing in a ring that is not of prime order. It becomes the programmer's responsibility to remember that only elements relatively prime to the modulus have well-defined inverses.

Crate Status

This crate is brand-new, and although it is "feature-complete" in a narrow sense, there are still things to be done.

• The crate currently only builds on nightly.
• Currently, the Modular type is generic over the modulus, but not the integer type, which is constrained to be u32. This is the major remaining omission, that I'll be correcting soon.
• The crate should support no_std.

There are a number of other improvements I would like to make to this crate:

• Montgomery multiplication for large products

• Compile-time error for attempted division in a composite-order ring. I consider this change pretty important, but it's waiting on some const generic features that don't exist yet.

• Possible feature flags for different algorithms.