ProveP

ProveP

Prove that a given number $p$ is prime

Putative prime $p$:

Primality proof from factors of $p-1$

For each prime power $q^k$ in the factored portion $s$ of $p-1$, ProveP finds a witness showing that every prime factor of $p$ is $1$ modulo $q^k$.

1. 1Factor $p-1$ and rigorously identify its prime factors.
2. 2For each $q$, find $a$ such that $a^{p-1}\equiv1\pmod p$ and $\gcd(a^{(p-1)/q}-1,p)=1$.
3. 3Multiply the certified prime powers into $s$.
4. 4Once $s>\sqrt p$, conclude that $p$ is prime.