/Primality-tests

Trial division, Fermat, Miller-Rabin, Solovay–Strassen and Lucas primality tests

Primary LanguagePython

Primality tests

Trial division

  • trial_division.py
  • The simplest primality test improved by trying to divide only by numbers of format 6k ± 1 less than √n.
  • Inefficient for large numbers.

Fermat primality test

  • fermat.py
  • The simplest probabilistic primality test
  • Takes number of loops as a second argument.

Miller–Rabin primality test

  • miller_rabin.py
  • Probabilistic test
  • Takes number of loops as a second argument.

Solovay–Strassen primality test

  • solovay_strassen.py
  • needs utils/jacobi.py to work
  • Probabilistic test
  • Takes number of loops as a second argument.

Lucas primality test

  • lucas.py
  • needs SymPy to work pip install sympy
  • Probabilistic test
  • Takes number of loops as a second argument.