fermats-little-theorem.md

← Return to Index

Fermat's Little Theorem

• If p is a prime, then for any integer 1 < a < p, a^p-1-1 is an integer multiple of p
  • a^p-1-1 mod p = 0
• This, we can guarantee that N is composite if a^N-1-1 mod N ≠ 0
• However, if it = 0, we cannot guarantee that N is prime

Pseudocode

repeat k times:
	a = any random number between 2 and N-1
		if a^(N-1) mod N != 0:
			return False
return Maybe