Identifikační kód |
RIV/67985840:_____/23:00573360 |
Název v anglickém jazyce |
Certifying giant nonprimes |
Druh |
D - Stať ve sborníku |
Jazyk |
eng - angličtina |
Vědní obor |
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8) |
Rok uplatnění |
2023 |
Kód důvěrnosti údajů |
S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
Počet výskytů výsledku |
2 |
Počet tvůrců celkem |
4 |
Počet domácích tvůrců |
1 |
Výčet všech uvedených jednotlivých tvůrců |
Pavel Hubáček (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 3306846, orcid: 0000-0002-6850-6222, scopusid: 55860823400, researcherid: Q-5154-2016) C. Hoffmann (státní příslušnost: AT - Rakouská republika) C. Kamath (státní příslušnost: IL - Stát Izrael) K. Pietrzak (státní příslušnost: AT - Rakouská republika) |
Popis výsledku v anglickém jazyce |
GIMPS and PrimeGrid are large-scale distributed projects dedicated to searching giant prime numbers, usually of special forms like Mersenne and Proth primes. 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.nIn 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. |
Klíčová slova oddělená středníkem |
chromium compounds;distributed projects;exponentiations |
Stránka www, na které se nachází výsledek |
- |
DOI výsledku |
10.1007/978-3-031-31368-4_19 |
Odkaz na údaje z výzkumu |
- |