[][src]Crate cyclic

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.


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:

This example deliberately fails 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.