Paper 2023/238

Certifying Giant Nonprimes

Charlotte Hoffmann, ISTA
Pavel Hubáček, Czech Academy of Sciences and Charles University
Chethan Kamath, Tel Aviv University
Krzysztof Pietrzak, ISTA

GIMPS and PrimeGrid are large-scale distributed projects dedicated to searching giant prime numbers, usually of special forms like Mersenne and Proth. The numbers in the current search-space are millions of digits large and the participating volunteers need to run resource-consuming primality tests. Once a candidate prime $N$ has been found, the only way for another party to independently verify the primality of $N$ used to be by repeating the expensive primality test. To avoid the need for second recomputation of each primality test, these projects have recently adopted certifying mechanisms that enable efficient verification of performed tests. However, the mechanisms presently in place only detect benign errors and there is no guarantee against adversarial behavior: a malicious volunteer can mislead the project to reject a giant prime as being non-prime. In this paper, we propose a practical, cryptographically-sound mechanism for certifying the non-primality of Proth numbers. That is, a volunteer can -- parallel to running the primality test for $N$ -- generate an efficiently verifiable proof at a little extra cost certifying that $N$ is not prime. The interactive protocol has statistical soundness and can be made non-interactive using the Fiat-Shamir heuristic. Our approach is based on a cryptographic primitive called Proof of Exponentiation (PoE) which, for a group $\mathbb{G}$, certifies that a tuple $(x,y,T)\in\mathbb{G}^2\times\mathbb{N}$ satisfies $x^{2^T}=y$ (Pietrzak, ITCS 2019 and Wesolowski, J. Cryptol. 2020). In particular, we show how to adapt Pietrzak's PoE at a moderate additional cost to make it a cryptographically-sound certificate of non-primality.

Available format(s)
Publication info
Published by the IACR in PKC 2023
Primality testingProof of ExponentiationSNARG
Contact author(s)
charlotte hoffmann @ ist ac at
hubacek @ iuuk mff cuni cz
ckamath @ protonmail com
pietrzak @ ist ac at
2023-02-21: approved
2023-02-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Charlotte Hoffmann and Pavel Hubáček and Chethan Kamath and Krzysztof Pietrzak},
      title = {Certifying Giant Nonprimes},
      howpublished = {Cryptology ePrint Archive, Paper 2023/238},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.