rust-miller-rabin's Introduction

🚀 Rust Miller-Rabin with bigInt capability

A complete Rust implementation of the Miller Rabin primality test algorithm. View on github: https://github.com/callum-fortune/rust-miller-rabin

Notes

The Miller Rabin algorithm, whilst incredibly accurate has been known to produce false positives in some cases. This is because the algorithm is officially classed as a probabilistic primality test. Proceed to use this project with that knowledge. Read more here...

https://core.ac.uk/download/pdf/197479038.pdf
The project is based heavily on this implementation...

https://github.com/jsanders/rust-rsa
I am yet to be made aware of the higher limit of this project, I have tested the code with prime numbers more than 300 characters in length and as little as one, without fail.
I created this project on my journey to implenting a basic Rust RSA implementation. This is a common use case for the Miller-Rabin test and there is a good chance that you are in the same process. Be warned that any implementations of your own that use this code are done at your own risk.

Usage

I have packaged this project as a Rust library however I have included a main.rs file to show the code in a working state. This can be found in the src folder or just ran with:
```
cargo build
cargo run
```

If you wish to use this as a library you can import and use it as follows:

use rust_miller_rabin::miller_rabin::miller_rabin

fn is_prime(number: BigInt) -> bool {
  println!("Checking prime");
  return miller_rabin(&number);
}

I have included tests for the project which will test small primes, large primes, small non-primes and large non-primes. Run these with:
```
cargo test
```

Recommend Projects