---
title: "PRIMES"
type: concept
related: [Primes]
source: https://www.jemoka.com/posts/kbhprimes/
confidence: high
status: active
---

&ldquo;very prime has a succinct certificate&rdquo;
\begin{equation} \text{PRIMES} : \qty {A \mid A\text{ is prime}} \end{equation}
The certificate?
\begin{equation} A \text{ prime} \Leftrightarrow \exists 1 &lt; b &lt; A : B, B^{2}, \dots, B^{A*2} \not \cong \ \text{mod}\ A \end{equation}
So \(\text{PRIMES} \in \text{NP}\)
But actually PRIMES is in \(P\)
