[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / raw/concept/kbhprimes.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "PRIMES" source: https://www.jemoka.com/posts/kbhprimes/ --- “very prime has a succinct certificate” \begin{equation} \text{PRIMES} : \qty {A \mid A\text{ is prime}} \end{equation} The certificate? \begin{equation} A \text{ prime} \Leftrightarrow \exists 1 < b < 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\)