{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:46:58Z","timestamp":1750308418861,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":40,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,7,4]],"date-time":"2022-07-04T00:00:00Z","timestamp":1656892800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,7,4]]},"DOI":"10.1145\/3476446.3536191","type":"proceedings-article","created":{"date-parts":[[2022,7,5]],"date-time":"2022-07-05T13:16:01Z","timestamp":1657026961000},"page":"207-215","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Random Primes without Primality Testing"],"prefix":"10.1145","author":[{"given":"Pascal","family":"Giorgi","sequence":"first","affiliation":[{"name":"LIRMM, Univ. Montpellier, CNRS, Montpellier, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bruno","family":"Grenet","sequence":"additional","affiliation":[{"name":"LIRMM, Univ. Montpellier, CNRS, Montpellier, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Armelle","family":"Perret du Cray","sequence":"additional","affiliation":[{"name":"LIRMM, Univ. Montpellier, CNRS, Montpellier, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel S.","family":"Roche","sequence":"additional","affiliation":[{"name":"United States Naval Academy, Annapolis, MD, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,7,5]]},"reference":[{"key":"e_1_3_2_1_2_1","first-page":"11","article-title":"Faster sparse multivariate polynomial interpolation of straight-line programs. Journal of Symbolic Computation, 2015","author":"Arnold Andrew","year":"2015","unstructured":"Andrew Arnold , Mark Giesbrecht , and Daniel S. Roche . Faster sparse multivariate polynomial interpolation of straight-line programs. Journal of Symbolic Computation, 2015 . ISSN 0747--7171. 10.1016\/j.jsc. 2015 . 11 .005. Andrew Arnold, Mark Giesbrecht, and Daniel S. Roche. Faster sparse multivariate polynomial interpolation of straight-line programs. Journal of Symbolic Computation, 2015. ISSN 0747--7171. 10.1016\/j.jsc.2015.11.005.","journal-title":"ISSN 0747--7171. 10.1016\/j.jsc."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62241"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1967.tb03174.x"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90013-9"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1981-0606517-5"},{"key":"e_1_3_2_1_7_1","first-page":"149","volume-title":"Transgressive Computing 2006: A conference in honor of Jean Della Dora","author":"Dahan Xavier","year":"2006","unstructured":"Xavier Dahan , Marc Moreno Maza, \u00c9ric Schost, and Yuzhen Xie. On the complexity of the d5 principle . In Transgressive Computing 2006: A conference in honor of Jean Della Dora , pages 149 -- 168 , 2006 . Xavier Dahan, Marc Moreno Maza, \u00c9ric Schost, and Yuzhen Xie. On the complexity of the d5 principle. In Transgressive Computing 2006: A conference in honor of Jean Della Dora, pages 149--168, 2006."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-15984-3_279"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2010.06.012"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1987.1057299"},{"issue":"2","key":"e_1_3_2_1_11_1","first-page":"119","article-title":"Rational Puiseux expansions","volume":"70","author":"Duval Dominique","year":"1989","unstructured":"Dominique Duval . Rational Puiseux expansions . Compositio Mathematica , 70 ( 2 ): 119 -- 154 , 1989 . Dominique Duval. Rational Puiseux expansions. Compositio Mathematica, 70 (2): 119--154, 1989.","journal-title":"Compositio Mathematica"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1017\/S096012950000044X"},{"key":"e_1_3_2_1_13_1","first-page":"27","article-title":"Garg and \u00c9ric Schost. Interpolation of polynomials given by straight-line programs","volume":"410","author":"Sanchit","year":"2009","unstructured":"Sanchit Garg and \u00c9ric Schost. Interpolation of polynomials given by straight-line programs . Theoretical Computer Science , 410 ( 27 -- 29 ): 2659--2662, 2009 . ISSN 0304--3975. 10.1016\/j.tcs.2009.03.030. Sanchit Garg and \u00c9ric Schost. Interpolation of polynomials given by straight-line programs. Theoretical Computer Science, 410 (27--29): 2659--2662, 2009. ISSN 0304--3975. 10.1016\/j.tcs.2009.03.030.","journal-title":"Theoretical Computer Science"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139856065"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608647"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.07.012"},{"key":"e_1_3_2_1_17_1","volume-title":"February","author":"der Hoeven Joris Hoevenvan","year":"2015","unstructured":"nd Lecerf(2015)]HL15 Joris Hoevenvan der Hoeven and Gr\u00e9goire Lecerf . Sparse polynomial interpolation in practice. ACM Commun. Comput. Algebra, 48 (3\/4): 187--191 , February 2015 . 10.1145\/2733693.2733721. nd Lecerf(2015)]HL15Joris Hoevenvan der Hoeven and Gr\u00e9goire Lecerf. Sparse polynomial interpolation in practice. ACM Commun. Comput. Algebra, 48 (3\/4): 187--191, February 2015. 10.1145\/2733693.2733721."},{"key":"e_1_3_2_1_18_1","volume-title":"Directed evaluation. Journal of Complexity, 60","author":"der Hoeven Joris Hoevenvan","year":"2020","unstructured":"nd Lecerf(2020)]HL20 Joris Hoevenvan der Hoeven and Gr\u00e9goire Lecerf . Directed evaluation. Journal of Complexity, 60 , 2020 . 10.1016\/j.jco.2020.101498. nd Lecerf(2020)]HL20Joris Hoevenvan der Hoeven and Gr\u00e9goire Lecerf. Directed evaluation. Journal of Complexity, 60, 2020. 10.1016\/j.jco.2020.101498."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3326229.3326250"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1837210.1837233"},{"key":"e_1_3_2_1_21_1","first-page":"340","volume-title":"Efficient generation of prime numbers. In cC etin K","author":"Joye Marc","year":"2000","unstructured":"Marc Joye , Pascal Paillier , and Serge Vaudenay . Efficient generation of prime numbers. In cC etin K . Kocc and Christof Paar, editors, Cryptographic Hardware and Embedded Systems -- CHES 2000 , pages 340 -- 354 , Berlin, Heidelberg, 2000. Springer Berlin Heidelberg . Marc Joye, Pascal Paillier, and Serge Vaudenay. Efficient generation of prime numbers. In cC etin K. Kocc and Christof Paar, editors, Cryptographic Hardware and Embedded Systems -- CHES 2000, pages 340--354, Berlin, Heidelberg, 2000. Springer Berlin Heidelberg."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(85)80029-8"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1837210.1837213"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(03)00088-9"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80015-6"},{"key":"e_1_3_2_1_26_1","first-page":"467","volume-title":"Proc. ISSAC","author":"Kaltofen Erich","year":"1988","unstructured":"Erich Kaltofen and Lakshman Yagati . Improved sparse multivariate polynomial interpolation algorithms. In P. Gianni, editor , Proc. ISSAC , pages 467 -- 474 , 1988 . 10.1007\/3--540--51084--2_44. Erich Kaltofen and Lakshman Yagati. Improved sparse multivariate polynomial interpolation algorithms. In P. Gianni, editor, Proc. ISSAC, pages 467--474, 1988. 10.1007\/3--540--51084--2_44."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/96877.96912"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.312.0249"},{"key":"e_1_3_2_1_29_1","volume-title":"Grundz\u00fcge einer arithmetischen theorie der algebraischen gr\u00f6ssen. Journal f\u00fcr die reine und angewandte Mathematik, 92: 1--122","author":"Kronecker Leopold","year":"1882","unstructured":"Leopold Kronecker . Grundz\u00fcge einer arithmetischen theorie der algebraischen gr\u00f6ssen. Journal f\u00fcr die reine und angewandte Mathematik, 92: 1--122 , 1882 . Leopold Kronecker. Grundz\u00fcge einer arithmetischen theorie der algebraischen gr\u00f6ssen. Journal f\u00fcr die reine und angewandte Mathematik, 92: 1--122, 1882."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(91)90113-B"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/bf00202269"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60114-7_28"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/800125.804045"},{"key":"e_1_3_2_1_34_1","volume-title":"\u00c9 ric Schost, and Gilles Villard. Faster modular composition. CoRR, abs\/2110.08354","author":"Neiger Vincent","year":"2021","unstructured":"Vincent Neiger , Bruno Salvy , \u00c9 ric Schost, and Gilles Villard. Faster modular composition. CoRR, abs\/2110.08354 , 2021 . URL https:\/\/arxiv.org\/abs\/2110.08354. Vincent Neiger, Bruno Salvy, \u00c9 ric Schost, and Gilles Villard. Faster modular composition. CoRR, abs\/2110.08354, 2021. URL https:\/\/arxiv.org\/abs\/2110.08354."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1145768.1145812"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01933667"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5802\/ahl.97"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289520"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814549"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24847-7_31"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.2307\/3620251"}],"event":{"name":"ISSAC '22: International Symposium on Symbolic and Algebraic Computation","sponsor":["SIGSAM ACM Special Interest Group on Symbolic and Algebraic Manipulation"],"location":"Villeneuve-d'Ascq France","acronym":"ISSAC '22"},"container-title":["Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3476446.3536191","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3476446.3536191","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:20Z","timestamp":1750268960000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3476446.3536191"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,4]]},"references-count":40,"alternative-id":["10.1145\/3476446.3536191","10.1145\/3476446"],"URL":"https:\/\/doi.org\/10.1145\/3476446.3536191","relation":{},"subject":[],"published":{"date-parts":[[2022,7,4]]},"assertion":[{"value":"2022-07-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}