{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T16:10:02Z","timestamp":1750003802111,"version":"3.41.0"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,2,22]],"date-time":"2017-02-22T00:00:00Z","timestamp":1487721600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee","doi-asserted-by":"publisher","award":["111913","123612"],"award-info":[{"award-number":["111913","123612"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001692","name":"Croucher Foundation","doi-asserted-by":"publisher","award":["9500015"],"award-info":[{"award-number":["9500015"]}],"id":[{"id":"10.13039\/501100001692","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptogr Eng"],"published-print":{"date-parts":[[2018,9]]},"DOI":"10.1007\/s13389-017-0151-z","type":"journal-article","created":{"date-parts":[[2017,2,22]],"date-time":"2017-02-22T08:57:01Z","timestamp":1487753821000},"page":"211-226","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Spectral arithmetic in Montgomery modular multiplication"],"prefix":"10.1007","volume":"8","author":[{"given":"Wangchen","family":"Dai","sequence":"first","affiliation":[]},{"given":"Ray C. C.","family":"Cheung","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,2,22]]},"reference":[{"issue":"1","key":"151_CR1","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1109\/TC.2015.2417553","volume":"65","author":"DD Chen","year":"2016","unstructured":"Chen, D.D., Yao, G.X., Cheung, R.C.C., Pao, D., Ko\u00e7, \u00c7.K.: Parameter space for the architecture of FFT-based Montgomery modular multiplication. IEEE Trans. Comput. 65(1), 147\u2013160 (2016)","journal-title":"IEEE Trans. Comput."},{"key":"151_CR2","doi-asserted-by":"crossref","unstructured":"P\u00f6ppelmann, T., G\u00fcneysu, T.: Towards efficient arithmetic for lattice-based cryptography on reconfigurable hardware. In: International Conference on Cryptology and Information Security in Latin America. Springer, pp. 139\u2013158 (2012)","DOI":"10.1007\/978-3-642-33481-8_8"},{"key":"151_CR3","doi-asserted-by":"crossref","unstructured":"Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, pp. 1\u201323 (2010)","DOI":"10.1007\/978-3-642-13190-5_1"},{"key":"151_CR4","doi-asserted-by":"crossref","unstructured":"G\u00fcneysu, T., Lyubashevsky, V., P\u00f6ppelmann, T.: Practical lattice-based cryptography: a signature scheme for embedded systems. In: International Workshop on Cryptographic Hardware and Embedded Systems. Springer, pp. 530\u2013547 (2012)","DOI":"10.1007\/978-3-642-33027-8_31"},{"key":"151_CR5","doi-asserted-by":"crossref","unstructured":"Cao, X., Moore, C., ONeill, M., Hanley, N., OSullivan, E.: High-speed fully homomorphic encryption over the integers. In: International Conference on Financial Cryptography and Data Security. Springer, pp. 169\u2013180 (2014)","DOI":"10.1007\/978-3-662-44774-1_14"},{"key":"151_CR6","doi-asserted-by":"crossref","unstructured":"Van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully homomorphic encryption over the integers. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, pp. 24\u201343 (2010)","DOI":"10.1007\/978-3-642-13190-5_2"},{"issue":"170","key":"151_CR7","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1090\/S0025-5718-1985-0777282-X","volume":"44","author":"PL Montgomery","year":"1985","unstructured":"Montgomery, P.L.: Modular multiplication without trial division. Math. Comput. 44(170), 519\u2013521 (1985)","journal-title":"Math. Comput."},{"key":"151_CR8","doi-asserted-by":"crossref","unstructured":"Barrett, P.: Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor. In: Conference on the Theory and Application of Cryptographic Techniques. Springer, pp. 311\u2013323 (1986)","DOI":"10.1007\/3-540-47721-7_24"},{"issue":"2","key":"151_CR9","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1145\/359340.359342","volume":"21","author":"RL Rivest","year":"1978","unstructured":"Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120\u2013126 (1978)","journal-title":"Commun. ACM"},{"key":"151_CR10","unstructured":"Rivest, R.L.: A description of a single-chip implementation of the RSA Cipher. Lambda, vol. 1, no. Fourth Quarter, pp. 14\u201318 (1980)"},{"key":"151_CR11","doi-asserted-by":"crossref","unstructured":"Barker, E., Barker, W., Burr, W., Polk, W., Smid, M., Gallagher, P.D., et al.: NIST special publication 800-57 recommendation for key management\u2014part 1: general (2012)","DOI":"10.6028\/NIST.SP.800-57p1r3"},{"key":"151_CR12","unstructured":"Knuth, D.E.: Fundamental algorithms: the art of computer programming (1973)"},{"key":"151_CR13","unstructured":"Karatsuba, A., Ofman, Y.: Multiplication of multidigit numbers on automata. In: Soviet Physics Doklady, vol. 7, p. 595 (1963)"},{"key":"151_CR14","doi-asserted-by":"crossref","unstructured":"Cook, S.A., Aanderaa, S.O.: On the minimum computation time of functions. Transactions of the American Mathematical Society, pp. 291\u2013314 (1969)","DOI":"10.1090\/S0002-9947-1969-0249212-8"},{"issue":"3\u20134","key":"151_CR15","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/BF02242355","volume":"7","author":"A Sch\u00f6nhage","year":"1971","unstructured":"Sch\u00f6nhage, A., Strassen, V.: Schnelle multiplikation gro\u00dfer zahlen. Computing 7(3\u20134), 281\u2013292 (1971)","journal-title":"Computing"},{"issue":"3","key":"151_CR16","doi-asserted-by":"crossref","first-page":"979","DOI":"10.1137\/070711761","volume":"39","author":"M F\u00fcrer","year":"2009","unstructured":"F\u00fcrer, M.: Faster integer multiplication. SIAM J. Comput. 39(3), 979\u20131005 (2009)","journal-title":"SIAM J. Comput."},{"key":"151_CR17","doi-asserted-by":"crossref","unstructured":"Harvey, D., Van Der Hoeven, J., Lecerf, G.: Even faster integer multiplication. J. Complex. 36(10), 1\u201330 (2016)","DOI":"10.1016\/j.jco.2016.03.001"},{"key":"151_CR18","unstructured":"Covanov, S., Thom\u00e9, E.: Fast arithmetic for faster integer multiplication (2015). ArXiv preprint arXiv:1502.02800"},{"issue":"21","key":"151_CR19","doi-asserted-by":"crossref","first-page":"1831","DOI":"10.1049\/el:19991230","volume":"35","author":"CD Walter","year":"1999","unstructured":"Walter, C.D.: Montgomery exponentiation needs no final subtractions. Electron. Lett. 35(21), 1831\u20131832 (1999)","journal-title":"Electron. Lett."},{"issue":"246","key":"151_CR20","doi-asserted-by":"crossref","first-page":"899","DOI":"10.1090\/S0025-5718-03-01543-6","volume":"73","author":"P McLaughlin Jr","year":"2004","unstructured":"McLaughlin Jr., P.: New frameworks for Montgomery modular multiplication method. Math. Comput. 73(246), 899\u2013906 (2004)","journal-title":"Math. Comput."},{"key":"151_CR21","doi-asserted-by":"crossref","unstructured":"Phatak, D.S., Goff, T.: Fast modular reduction for large wordlengths via one linear and one cyclic convolution. In: Computer Arithmetic, 2005. ARITH-17 2005. 17th IEEE Symposium on. IEEE, pp. 179\u2013186 (2005)","DOI":"10.1109\/ARITH.2005.21"},{"key":"151_CR22","doi-asserted-by":"crossref","unstructured":"Saldaml\u0131, G., Ko\u00e7, \u00c7.K.: Spectral modular exponentiation. In: Computer Arithmetic, 2007. ARITH\u201907. 18th IEEE Symposium on. IEEE, pp. 123\u2013132 (2007)","DOI":"10.1109\/ARITH.2007.34"},{"key":"151_CR23","doi-asserted-by":"crossref","unstructured":"David, J.P., Kalach, K., Tittley, N.: Hardware complexity of modular multiplication and exponentiation. IEEE Trans. Comput. 56(10), 1308\u20131319 (2007)","DOI":"10.1109\/TC.2007.1084"},{"key":"151_CR24","doi-asserted-by":"crossref","unstructured":"Dai, W., Chen, D., Cheung, R.C.C., Ko\u00e7, \u00c7.K.: Area-time efficient architecture of FFT-based Montgomery multiplication. IEEE Trans. Comput. 66(3), 375\u2013388 (2017)","DOI":"10.1109\/TC.2016.2601334"},{"key":"151_CR25","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-81897-4","volume-title":"Fast Fourier transform and convolution algorithms","author":"HJ Nussbaumer","year":"1982","unstructured":"Nussbaumer, H.J.: Fast Fourier transform and convolution algorithms. Springer, Berlin (1982)"},{"issue":"114","key":"151_CR26","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1090\/S0025-5718-1971-0301966-0","volume":"25","author":"JM Pollard","year":"1971","unstructured":"Pollard, J.M.: The fast Fourier transform in a finite field. Math. Comput. 25(114), 365\u2013374 (1971)","journal-title":"Math. Comput."},{"issue":"90","key":"151_CR27","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1090\/S0025-5718-1965-0178586-1","volume":"19","author":"JW Cooley","year":"1965","unstructured":"Cooley, J.W., Tukey, J.W.: An algorithm for the machine calculation of complex Fourier series. Math. Comput. 19(90), 297\u2013301 (1965)","journal-title":"Math. Comput."},{"issue":"205","key":"151_CR28","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1090\/S0025-5718-1994-1185244-1","volume":"62","author":"R Crandall","year":"1994","unstructured":"Crandall, R., Fagin, B.: Discrete weighted transforms and large-integer arithmetic. Math. Comput. 62(205), 305\u2013324 (1994)","journal-title":"Math. Comput."},{"key":"151_CR29","unstructured":"Bernstein, D.J.: Multidigit multiplication for mathematicians. Adv. Appl. Math. 1\u201319 (2001)"},{"key":"151_CR30","unstructured":"Granlund, T.: The GMP development team: the GNU multiple precision arithmetic library 6.1.0 edn. (2015)"},{"key":"151_CR31","unstructured":"Saldaml\u0131, G.: Spectral Modular Arithmetic. PhD Thesis (2005)"},{"issue":"3","key":"151_CR32","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1109\/40.502403","volume":"16","author":"\u00c7K Ko\u00e7","year":"1996","unstructured":"Ko\u00e7, \u00c7.K., Acar, T., Kaliski, B.S.: Analyzing and comparing Montgomery multiplication algorithms. IEEE Micro 16(3), 26\u201333 (1996)","journal-title":"IEEE Micro"},{"key":"151_CR33","unstructured":"Smart, N., Babbage, S., Catalano, D., Cid, C., Weger, B.D., Dunkelman, O., Ward, M.: ECRYPT II yearly report on algorithms and keysizes (2011\u20132012). European Network of Excellence in Cryptology (ECRYPT II), Sept (2012)"},{"key":"151_CR34","doi-asserted-by":"crossref","unstructured":"Zimmermann, R.: Efficient VLSI implementation of modulo ( $$2^n\\pm 1$$ 2 n \u00b1 1 ) addition and multiplication. In: Computer Arithmetic, 1999. Proceedings. 14th IEEE Symposium on. IEEE, pp. 158\u2013167 (1999)","DOI":"10.1109\/ARITH.1999.762841"},{"issue":"7","key":"151_CR35","doi-asserted-by":"crossref","first-page":"923","DOI":"10.1109\/TC.2010.247","volume":"60","author":"M Huang","year":"2011","unstructured":"Huang, M., Gaj, K., El-Ghazawi, T.: New hardware architectures for Montgomery modular multiplication algorithm. IEEE Trans. Comput. 60(7), 923\u2013936 (2011)","journal-title":"IEEE Trans. Comput."},{"key":"151_CR36","unstructured":"Giorgi, P., Imbert, L., Izard, T.: Parallel modular multiplication on multi-core processors. In: Computer Arithmetic (ARITH), 2013 21st IEEE Symposium on. IEEE, pp. 135\u2013142 (2013)"},{"issue":"4","key":"151_CR37","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0165-1684(84)90059-8","volume":"6","author":"M Vetterli","year":"1984","unstructured":"Vetterli, M., Nussbaumer, H.J., et al.: Simple FFT and DCT algorithms with reduced number of operations. Signal Process. 6(4), 267\u2013278 (1984)","journal-title":"Signal Process."},{"issue":"4","key":"151_CR38","doi-asserted-by":"crossref","first-page":"750","DOI":"10.1109\/TASSP.1984.1164395","volume":"32","author":"JB Martens","year":"1984","unstructured":"Martens, J.B.: Recursive cyclotomic factorization new algorithm for calculating the discrete fourier transform. IEEE Trans. Acoust Speech Signal Process. 32(4), 750\u2013761 (1984)","journal-title":"IEEE Trans. Acoust Speech Signal Process."},{"issue":"1","key":"151_CR39","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1049\/el:19840012","volume":"20","author":"P Duhamel","year":"1984","unstructured":"Duhamel, P., Hollmann, H.: Split-radix FFT algorithm. Electron. Lett. 20(1), 14\u201316 (1984)","journal-title":"Electron. Lett."},{"key":"151_CR40","volume-title":"Generalized Mersenne Numbers","author":"JA Solinas","year":"1999","unstructured":"Solinas, J.A.: Generalized Mersenne Numbers. Citeseer, Bielefeld (1999)"},{"issue":"03","key":"151_CR41","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1142\/S0129626411000266","volume":"21","author":"N Emmart","year":"2011","unstructured":"Emmart, N., Weems, C.C.: High precision integer multiplication with a gpu using strassen\u2019s algorithm with multiple FFT sizes. Parallel Process. Lett. 21(03), 359\u2013375 (2011)","journal-title":"Parallel Process. Lett."},{"key":"151_CR42","unstructured":"Wang, W., Huang, X.: A novel fast modular multiplier architecture for 8192-bit RSA cryposystem. In: High Performance Extreme Computing Conference (HPEC), 2013 IEEE. IEEE, pp. 1\u20135 (2013)"},{"key":"151_CR43","unstructured":"Kumar, V., Selvakumar, D., Sobha, P.: Area and frequency optimized 1024 point radix-2 FFT processor on FPGA. In: VLSI Systems, Architecture, Technology and Applications (VLSI-SATA), 2015 International Conference on. IEEE, pp. 1\u20136 (2015)"},{"issue":"6","key":"151_CR44","first-page":"1509","volume":"64","author":"Y Dor\u00f6z","year":"2015","unstructured":"Dor\u00f6z, Y., \u00d6zt\u00fcrk, E., Sunar, B.: Accelerating fully homomorphic encryption in hardware. IEEE Trans. Comput. 64(6), 1509\u20131521 (2015)","journal-title":"IEEE Trans. Comput."},{"key":"151_CR45","doi-asserted-by":"crossref","unstructured":"P\u00f6ppelmann, T., Naehrig, M., Putnam, A., Macias, A.: Accelerating homomorphic evaluation on reconfigurable hardware. In: International Workshop on Cryptographic Hardware and Embedded Systems. Springer, pp. 143\u2013163 (2015)","DOI":"10.1007\/978-3-662-48324-4_8"},{"key":"151_CR46","unstructured":"Cao, X., Moore, C., Neill, M.O., Sullivan, E.O., Hanley, N.: Optimised multiplication architectures for accelerating fully homomorphic encryption"}],"container-title":["Journal of Cryptographic Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s13389-017-0151-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s13389-017-0151-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s13389-017-0151-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T15:34:43Z","timestamp":1750001683000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s13389-017-0151-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,2,22]]},"references-count":46,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,9]]}},"alternative-id":["151"],"URL":"https:\/\/doi.org\/10.1007\/s13389-017-0151-z","relation":{},"ISSN":["2190-8508","2190-8516"],"issn-type":[{"type":"print","value":"2190-8508"},{"type":"electronic","value":"2190-8516"}],"subject":[],"published":{"date-parts":[[2017,2,22]]}}}