Primality certificate

1975年にVaughan PrattはPRIMESがNPに、また従ってNP ∩ co-NPに属することを示した（Primality certificateを参照）。 Solovay-StrassenとMiller-RabinによるアルゴリズムによりPRIMESはco-RPに属するこ