# Fermat Primality Test

A probabilistic primality test implementation in Elixir based on Fermat's Little Theorem.

## Overview

This library provides an efficient implementation of the Fermat primality test, a probabilistic algorithm for determining whether a given number is likely to be prime. The test is based on Fermat's Little Theorem and uses modular exponentiation for optimal performance.

## Mathematical Foundation

Fermat's Little Theorem states that if $p$ is a prime number and $a$ is any integer not divisible by $p$, then:

$$a^{p-1} \equiv 1 \pmod{p}$$

The test works by checking this congruence for multiple random bases. If any base fails the test, the number is definitely composite. If all bases pass, the number is probably prime.

## Features

- **Probabilistic Testing**: Uses 100 random bases for high accuracy
- **Efficient Implementation**: $O(k \log n)$ time complexity where $k = 100$
- **Mathematical Rigor**: Based on well-established number theory
- **Comprehensive Documentation**: Full API documentation with examples
- **Quality Assurance**: Includes static analysis, type checking, and spell checking

## Installation

Add `fermat_primality_test` to your list of dependencies in `mix.exs`:

```elixir
def deps do
  [
    {:fermat_primality_test, "~> 0.1"}
  ]
end
```

Then install dependencies:

```bash
mix deps.get
```

## Usage

### Basic Usage

```elixir
# Test if a number is prime
FermatPrimalityTest.of(17)  # Returns true
FermatPrimalityTest.of(100) # Returns false
FermatPrimalityTest.of(1)   # Returns false
FermatPrimalityTest.of(2)   # Returns true
```

### Modular Exponentiation

```elixir
# Calculate modular exponentiation
FermatPrimalityTest.mod_pow(10, 2, 3)  # Returns 1
FermatPrimalityTest.mod_pow(7, 3, 5)   # Returns 3
FermatPrimalityTest.mod_pow(2, 10, 1000) # Returns 24
```

## Algorithm Details

### Fermat Primality Test

For a given number $n$:

1. **Edge Cases**: 
   - If $n = 1$, return `false` (1 is not prime)
   - If $n = 2$, return `true` (2 is prime)

2. **Main Test** (for $n > 2$):
   - Generate 100 random bases $a$ where $1 < a < n$
   - For each base, check if $\gcd(a, n) = 1$ (coprime)
   - If coprime, compute $a^{n-1} \bmod n$
   - If the result is not 1, $n$ is definitely composite
   - If all 100 tests pass, $n$ is probably prime

### Modular Exponentiation

The library uses the square-and-multiply algorithm for efficient modular exponentiation:

- **Time Complexity**: $O(\log exp)$
- **Space Complexity**: $O(1)$
- **Algorithm**: Binary exponentiation with modular arithmetic

## Accuracy

- **True Positives**: All prime numbers will pass the test
- **False Positives**: Some composite numbers (pseudoprimes) may pass the test
- **False Negatives**: None (if the test says composite, it's definitely composite)

The probability of a false positive decreases with the number of bases tested. With 100 random bases, the probability is extremely low for most practical purposes.

## Performance

- **Time Complexity**: $O(k \log n)$ where $k = 100$ (number of bases)
- **Space Complexity**: $O(1)$ - constant space usage
- **Optimizations**: Efficient modular exponentiation and GCD calculations

## Limitations

- **Probabilistic**: This is not a deterministic test
- **Pseudoprimes**: Some composite numbers may pass the test
- **Large Numbers**: Performance may degrade for very large numbers
- **Cryptographic Use**: For cryptographic applications, consider deterministic tests like AKS

## License

Copyright (c) 2025 University of Kitakyushu

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at [http://www.apache.org/licenses/LICENSE-2.0](http://www.apache.org/licenses/LICENSE-2.0)

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.

## References

- [Fermat's Little Theorem](https://en.wikipedia.org/wiki/Fermat%27s_little_theorem)
- [Modular Exponentiation](https://en.wikipedia.org/wiki/Modular_exponentiation)
- [Probabilistic Primality Testing](https://en.wikipedia.org/wiki/Primality_test#Probabilistic_tests)
- [Carmichael Numbers](https://en.wikipedia.org/wiki/Carmichael_number)

## Changelog

See [CHANGELOG.md](CHANGELOG.md) for a list of changes and version history.