{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:33:09Z","timestamp":1750307589174,"version":"3.41.0"},"reference-count":10,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2010,4,1]],"date-time":"2010-04-01T00:00:00Z","timestamp":1270080000000},"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":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2010,4]]},"abstract":"\n On\n w<\/jats:italic>\n -bit processors which are much faster at multiplying two\n w<\/jats:italic>\n -bit integers than at dividing 2\n w<\/jats:italic>\n -bit integers by\n w<\/jats:italic>\n -bit integers, reductions of large integers by moduli\n M<\/jats:italic>\n smaller than 2\n \n w<\/jats:italic>\n -1\n <\/jats:sup>\n are often implemented suboptimally, leading applications to take excessive processing time.\n <\/jats:p>\n \n We present a modular reduction algorithm implementing division by a modulus through multiplication by a reciprocal of that modulus, a well-known method for moduli larger than 2\n \n w<\/jats:italic>\n -1\n <\/jats:sup>\n . We show that application of this method to smaller moduli makes it possible to express certain modular sums and differences without having to compensate for word overflows.\n <\/jats:p>\n \n By embedding the algorithm in a loop and applying a few transformations to the loop, we obtain an algorithm for reduction of large integers by moduli up to 2\n \n w<\/jats:italic>\n -1\n <\/jats:sup>\n . Implementations of this algorithm can run considerably faster than implementations of similar algorithms that allow for moduli up to 2\n \n w<\/jats:italic>\n <\/jats:sup>\n . This is substantiated by measurements on processors with relatively fast multiplication instructions.\n <\/jats:p>\n It is notoriously hard to specify efficient mathematical algorithms on the level of abstract machine instructions in an error-free manner. In order to eliminate the chance of errors as much as possible, we have created formal correctness proofs of our algorithms, checked by a mechanized proof assistant.<\/jats:p>","DOI":"10.1145\/1731022.1731026","type":"journal-article","created":{"date-parts":[[2010,5,6]],"date-time":"2010-05-06T17:41:18Z","timestamp":1273167678000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Efficient and formally proven reduction of large integers by small moduli"],"prefix":"10.1145","volume":"37","author":[{"given":"Luc","family":"Rutten","sequence":"first","affiliation":[{"name":"IBM, Delft, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marko","family":"Van Eekelen","sequence":"additional","affiliation":[{"name":"Radboud University Nijmegen and Open University of the Netherlands, Nijmegen, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,4,23]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the Crypto'86","volume":"263","author":"Barrett P.","year":"1987"},{"volume":"773","volume-title":"Proceedings of the Crypto'93","author":"Bosselaers A.","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Bratley P. Fox B. and Schrage L. 1987. A Guide to Simulation 2nd ed. Springer-Verlag New York NY. Bratley P. Fox B. and Schrage L. 1987. A Guide to Simulation 2nd ed. Springer-Verlag New York NY.","DOI":"10.1007\/978-1-4419-8724-2"},{"volume-title":"Proceedings of the Symposium on Automatic Demonstration","series-title":"Lecture Notes in Mathematics","author":"de Bruijn N. G.","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/773473.178249"},{"key":"e_1_2_1_6_1","unstructured":"Knuth D. 1998. The Art of Computer Programming 3d Ed. Vol. 2\u2014Seminumerical Algorithms. Addison Wesley Longman Reading MA. Knuth D. 1998. The Art of Computer Programming 3d Ed. Vol. 2\u2014Seminumerical Algorithms. Addison Wesley Longman Reading MA."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.82.0136"},{"edition":"2","volume-title":"Python in a Nutshell","author":"Martelli A.","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/362848.362860"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/648071.748514"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1731022.1731026","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1731022.1731026","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:41:27Z","timestamp":1750250487000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1731022.1731026"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,4]]},"references-count":10,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,4]]}},"alternative-id":["10.1145\/1731022.1731026"],"URL":"https:\/\/doi.org\/10.1145\/1731022.1731026","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"type":"print","value":"0098-3500"},{"type":"electronic","value":"1557-7295"}],"subject":[],"published":{"date-parts":[[2010,4]]},"assertion":[{"value":"2008-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-04-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}