We have been given the challenge to check if a given number is a prime in the Rust programming language without using any of the built in arithmetic operations (+, -, *, /, %) for primitive numeric types (i.e. unsigned integers, signed integers, floating point types). We may assume that the number is known at compile time and can be represented by the pointer-sized unsigned integer type usize. We are allowed to apply functionality from the standard library applying arithmetic operations on primitive types under the hood, but we are not allowed to call these ourselves. The solution to this challenge privded in this post will be very slow and should never be used in the real world, the only purpose of this blog post is to show that it is possible and we get some training with iterators along the way.
Before we provide any code lets explain the mathematical idea behind our solution:
Some mathematics
The basics of prime numbers
We recall that a number is prime if it is not divisible with any number other than itself and one. In other words $p$ is prime if whenever we have $p = s \cdot u$ for two integers $s$ and $u$ then either $s = p$ or $u = p$ (and the other number is $1$). Furthermore if $m$ and $n$ are two integers and $p$ is a prime then if $p$ divides the product $m \cdot n$ then $p$ must necessarily divide either $m$ or $n$.
Congruence classes
Let $n$ be an integer. For two integers $a, b$ we say that $a$ is congruent to $b$ modulo $n$, denoted $ a \equiv b{\pmod {n}}$, if there is an integer $k$ such that $a - b = k \cdot n$. This forms an equivalence relation on the set of integers and we denote the set of equivalence classes by $\mathbb{Z}/n\mathbb{Z}$. We have a map from $\mathbb{Z}$ to $\mathbb{Z}/n\mathbb{Z}$ given by mapping an integer $a$ to its equivalence class which we denote by $\overline{a}$. Two integers $a,b$ map to the same equivalence class if and only if they have the same remainder when divided by $n$. There are exactly $n$ elements in the set $\mathbb{Z}/n\mathbb{Z}$ and these are exactly the images $\overline{0},\overline{1},…, \overline{n-1}$ (assuming that $n$ is positive) under the aforementioned map. One can define addition and multiplication on the set $\mathbb{Z}/n\mathbb{Z}$ given by $\begin{equation} \overline{a} + \overline{b} = \overline{a+b}\end{equation}$ and $\begin{equation}\overline{a} \cdot \overline{b} = \overline{ab}\end{equation}$ respectively.
This kind of arithmetic is called modular arithmetic. Notice that we have $\overline{n-1} + \overline{1} = \overline{0}$ so the arithmetic “wraps” around $n$ and we therefore call $n$ the modulus.
We can express what it means for a number $n$ to be prime in this language: $n$ is prime if and only if whenever $\overline{a} \cdot \overline{b} = \overline{0}$ in $\mathbb{Z}/n\mathbb{Z}$ then either $\overline{a} = \overline{0}$ or $\overline{b} = \overline{0}$. If we think a bit more about it, we actually have that $n$ is prime if and only if the product of the squares of all non-zero elements in $\mathbb{Z}/n\mathbb{Z}$ is different from zero: \(\begin{equation} \overline{1}^2 \cdot \overline{2}^2 \cdot \ldots \cdot \overline{n-1}^2 \neq \overline{0} \end{equation}\)
Our strategy: We define congruence classes and how to multiply them in Rust, then we check if their product is different from $\overline{0}$.
Let’s get started!
Modular arithmetic in Rust without the “%” operation
We start by introducing a struct for congruence classes as follows:
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
/// Type representing Z/MODULUS*Z
struct Congruence<const MODULUS: usize> {
representative: usize,
}
We use const generics to define these congruence classes. This has the advantage that these congruence classes depend on the modulus, hence it will be impossible to have a scenario where congruence classes with different moduluses are multiplied together. The drawback is that we need to know what the modulus is at compile time, but in our case we may assume this. Since this struct is essentially just a wrapper around a usize, we derive some of the underlying types properties such that we may copy and clone them, and check for equality. The latter requires a bit of care of course, but we will get back to that later.
Now let us also define the zero element $\overline{0}$ as an associated constant:
impl<const MODULUS: usize> Congruence<MODULUS> {
/// The additive identity
const ZERO: Self = Self {
representative: 0_usize,
};
}
Now we want a way to convert a usize into a Congruence, meaning we want to implement the From trait. Since we have derived the Eq trait we cannot simply map a usize r to Congruence<MODULUS>{representative : r} because then there will be congruent numbers mapping to non-equal values. Notice also that we are not allowed to use the the modulo operator $%$ so this will also not help. We solve this problem by using the cycle function that is implemented on all iterators in Rust:
use std::iter::Cycle;
use std::ops::Range;
/// Returns a cyclic iterator over 0,1,...,MODULUS -1
fn cycle<const MODULUS: usize>() -> Cycle<Range<usize>> {
(0..MODULUS).into_iter().cycle()
}
impl<const MODULUS: usize> From<usize> for Congruence<MODULUS> {
fn from(number: usize) -> Self {
Self {
representative: (cycle::<MODULUS>().skip(number).next().unwrap_or(0_usize)), // or only happens when MODULUS = 0
}
}
}
The cycle function gives us an iterator over $0,1, \ldots ,MODULUS -1 $ that starts again from $0$ after $MODULUS -1$ has been reached. if a usize $number$ is of the form $m \cdot MODULUS + r$ with $r < MODULUS$ then the code
cycle::<MODULUS>().skip(number).next()
gives us exactly $r$. Here I believe addition is being used under the hood, as the range (0..MODULUS) uses the unsafe Step trait implemented on usize to produce an iterator.
Now we define multiplication for the Congruence struct:
use std::ops::Mul;
impl<const MODULUS: usize> Mul for Congruence<MODULUS> {
type Output = Self;
fn mul(self, other: Self) -> Self::Output {
let zero = Congruence::<MODULUS>::ZERO;
if (self == zero) || (other == zero) {
return zero;
}
let representative = cycle::<MODULUS>()
.step_by(self.representative)
.step_by(other.representative)
.skip(1)
.next()
.unwrap();
Self { representative }
}
}
Every iterator in Rust implements the step_by function. It returns an iterator that starts at the same point, but steps by the given amount at each iteration. By chaining these together we can emulate multiplication, but since the obtained iterator starts at the same position we need to skip this first iteration.
The final ingredient is defining how an iterator with associated type Congruence can multiply all its elements together:
use std::iter::Product;
impl<const MODULUS: usize> Product for Congruence<MODULUS> {
fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
iter.reduce(|x, y| x * y)
.unwrap_or(Congruence::<MODULUS>::from(0_usize))
}
}
We use the reduce function which every iterator in Rust implements. It behaves like fold, but uses the first element as the initial value.
We can now finally construct our function that determines whether a constant MODULUS is a prime number:
/// Determine if the constant MODULUS is a prime number
fn is_prime<const MODULUS: usize>() -> bool {
// MODULUS is prime if and only if the product of the squares of all non-zero congruence classes is different from zero
let prod: Congruence<MODULUS> = (1..MODULUS)
.into_iter()
.map(|i| Congruence::<MODULUS>::from(i))
.map(|i| i * i)
.product();
Congruence::<MODULUS>::ZERO != prod
}
Let’s check that it works: We test with the Fibonacci prime “1597”.
fn main() {
const N: usize = 1597;
if is_prime::<N>() {
print!("{} is prime! \r\n", N);
} else {
print!("{} is not prime! \r\n", N);
}
}
Which yields:
$ cargo run --release
Finished release [optimized] target(s) in 0.00s
Running `target/release/iterator_modulo_blog_post`
1597 is prime!
It works! Notice however that it is indeed rather slow, especially if we don’t pass the release flag!
The code for this blog post can be found in this repository where I have also implemented addition, subtraction and some other operations for the Congruence struct. Furthermore I applied Rust’s great module system to structure the code nicely.