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:
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.
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.
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
Modulartype 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
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.