{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T18:19:25Z","timestamp":1776795565590,"version":"3.51.2"},"reference-count":30,"publisher":"American Mathematical Society (AMS)","issue":"281","license":[{"start":{"date-parts":[[2013,6,27]],"date-time":"2013-06-27T00:00:00Z","timestamp":1372291200000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>We propose new squaring formulae for cyclotomic subgroups of the multiplicative group of certain finite fields. Our formulae use a compressed representation of elements having the property that decompression can be performed at a very low cost. The squaring formulae lead to new exponentiation algorithms in cyclotomic subgroups which outperform the fastest previously-known exponentiation algorithms when the exponent has low Hamming weight. Our algorithms can be adapted to accelerate the final exponentiation step of pairing computations.<\/p>","DOI":"10.1090\/s0025-5718-2012-02625-1","type":"journal-article","created":{"date-parts":[[2012,6,27]],"date-time":"2012-06-27T15:12:35Z","timestamp":1340809955000},"page":"555-579","source":"Crossref","is-referenced-by-count":31,"title":["Squaring in cyclotomic subgroups"],"prefix":"10.1090","volume":"82","author":[{"given":"Koray","family":"Karabina","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2012,6,27]]},"reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"D. Aranha, K. Karabina, P. Longa, C. Gebotys, and J. L\u00f3pez, Faster explicit formulas for computing pairings over ordinary curves, Advances in Cryptology - Eurocrypt 2011, Lecture Notes in Computer Science 6632 (2011), 48\u201368.","DOI":"10.1007\/978-3-642-20465-4_5"},{"key":"2","isbn-type":"print","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/11693383_22","article-title":"Pairing-friendly elliptic curves of prime order","author":"Barreto, Paulo S. L. M.","year":"2006","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540331087"},{"key":"3","isbn-type":"print","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/978-3-642-13797-6_13","article-title":"Constructing tower extensions of finite fields for implementation of pairing-based cryptography","author":"Benger, Naomi","year":"2010","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642137969"},{"key":"4","doi-asserted-by":"crossref","unstructured":"J. Beuchat, J. D\u00edaz, S. Mitsunari, E. Okamoto, F. Rodr\u00edguez-Henr\u00edquez, and T. Teruya, High-speed software implementation of the optimal Ate pairing over Barreto-Naehrig curves, Pairing-Based Cryptography \u2013 Pairing 2010, Lecture Notes in Computer Science 6487 (2010), 21\u201339.","DOI":"10.1007\/978-3-642-17455-1_2"},{"key":"5","doi-asserted-by":"crossref","unstructured":"A. Brouwer, R. Pellikaan, and E. Verheul, Doing more with fewer bits, Advances in Cryptology \u2013 ASIACRYPT \u201999, Lecture Notes in Computer Science 1716 (1999), 321\u2013332.","DOI":"10.1007\/978-3-540-48000-6_26"},{"key":"6","doi-asserted-by":"crossref","unstructured":"J. Chung and M. Hasan, Asymmetric squaring formulae, 18th IEEE Symposium on Computer Arithmetic \u2013 ARITH 2007 (2007), 113\u2013122.","DOI":"10.1109\/ARITH.2007.11"},{"issue":"2","key":"7","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/s00145-009-9048-z","article-title":"A taxonomy of pairing-friendly elliptic curves","volume":"23","author":"Freeman, David","year":"2010","journal-title":"J. Cryptology","ISSN":"https:\/\/id.crossref.org\/issn\/0933-2790","issn-type":"print"},{"key":"8","unstructured":"K. Giuliani and G. Gong, Analogues to the Gong-Harn and XTR cryptosystems, Technical Report CORR 2003-34, University of Waterloo (2003), Available at \\url{http:\/\/www.cacr.math.uwaterloo.ca\/techreports\/2003\/corr2003-34.ps}."},{"issue":"7","key":"9","doi-asserted-by":"publisher","first-page":"2601","DOI":"10.1109\/18.796413","article-title":"Public-key cryptosystems based on cubic finite field extensions","volume":"45","author":"Gong, Guang","year":"1999","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"key":"10","isbn-type":"print","doi-asserted-by":"publisher","first-page":"480","DOI":"10.1007\/11792086_34","article-title":"High security pairing-based cryptography revisited","author":"Granger, R.","year":"2006","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540360759"},{"key":"11","isbn-type":"print","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-540-24847-7_17","article-title":"A comparison of CEILIDH and XTR","author":"Granger, R.","year":"2004","ISBN":"https:\/\/id.crossref.org\/isbn\/3540221565"},{"key":"12","isbn-type":"print","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/978-3-642-13013-7_13","article-title":"Faster squaring in the cyclotomic subgroup of sixth degree extensions","author":"Granger, Robert","year":"2010","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642130120"},{"key":"13","unstructured":"D. Harris, Simultaneous field divisions: an extension of Montgomery\u2019s trick,(2008), Available at \\url{http:\/\/eprint.iacr.org\/2008\/199}."},{"key":"14","isbn-type":"print","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1007\/978-3-642-10868-6_20","article-title":"Double-exponentiation in factor-4 groups and its applications","author":"Karabina, Koray","year":"2009","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642108679"},{"issue":"1","key":"15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1515\/JMC.2010.001","article-title":"Factor-4 and 6 compression of cyclotomic subgroups of \ud835\udd3d*_{2^{4\ud835\udd5e}} and \ud835\udd3d*_{3^{6\ud835\udd5e}}","volume":"4","author":"Karabina, Koray","year":"2010","journal-title":"J. Math. Cryptol.","ISSN":"https:\/\/id.crossref.org\/issn\/1862-2976","issn-type":"print"},{"key":"16","unstructured":"\\bysame, Torus-based compression by factor 4 and 6, Accepted for publication in IEEE Transactions on Information theory, DOI 10.1109\/TIT.2012.2184846; Earlier version available at \\url{http:\/\/eprint.iacr.org\/2010\/525}."},{"key":"17","isbn-type":"print","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/11586821_2","article-title":"Pairing-based cryptography at high security levels","author":"Koblitz, Neal","year":"2005","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540302766"},{"key":"18","isbn-type":"print","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-44598-6_1","article-title":"The XTR public key system","author":"Lenstra, Arjen K.","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/3540679073"},{"key":"19","isbn-type":"print","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/978-3-540-46588-1_27","article-title":"Fast implementation of elliptic curve arithmetic in \ud835\udc3a\ud835\udc39(\ud835\udc5d\u207f)","author":"Lim, Chae Hoon","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/3540669671"},{"issue":"177","key":"20","doi-asserted-by":"publisher","first-page":"243","DOI":"10.2307\/2007888","article-title":"Speeding the Pollard and elliptic curve methods of factorization","volume":"48","author":"Montgomery, Peter L.","year":"1987","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"21","isbn-type":"print","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1007\/978-3-540-85538-5_13","article-title":"Integer variable \ud835\udf12-based Ate pairing","author":"Nogami, Yasuyuki","year":"2008","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540855033"},{"key":"22","isbn-type":"print","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/978-3-540-45146-4_21","article-title":"Torus-based cryptography","author":"Rubin, Karl","year":"2003","ISBN":"https:\/\/id.crossref.org\/isbn\/3540406743"},{"issue":"5","key":"23","doi-asserted-by":"publisher","first-page":"1401","DOI":"10.1137\/060676155","article-title":"Compression in finite fields and torus-based cryptography","volume":"37","author":"Rubin, K.","year":"2008","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"key":"24","isbn-type":"print","first-page":"177","article-title":"Implementing cryptographic pairings","author":"Scott, Michael","year":"2007","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540734888"},{"key":"25","doi-asserted-by":"crossref","unstructured":"M. Shirase, D. Han, Y. Hibin, H. Kim, and T. Takagi, A more compact representation of XTR cryptosystem, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E91-A (2008), 2843\u20132850.","DOI":"10.1093\/ietfec\/e91-a.10.2843"},{"key":"26","doi-asserted-by":"crossref","unstructured":"P. Smith and C. Skinner, A public-key cryptosystem and a digital signature system based on the Lucas function analogue to discrete logarithms, Advances in Cryptology \u2013 ASIACRYPT \u201994, Lecture Notes In Computer Science 917 (1994), 357\u2013364.","DOI":"10.1007\/BFb0000447"},{"key":"27","isbn-type":"print","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/3-540-45682-1_8","article-title":"Speeding up XTR","author":"Stam, Martijn","year":"2001","ISBN":"https:\/\/id.crossref.org\/isbn\/3540429875"},{"key":"28","doi-asserted-by":"crossref","unstructured":"\\bysame, Efficient subgroup exponentiation in quadratic and sixth degree extensions, Cryptographic Hardware and Embedded Systems \u2013 CHES 2002 2523 (2003), 159\u2013174.","DOI":"10.1007\/3-540-36400-5_24"},{"key":"29","isbn-type":"print","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/11426639_14","article-title":"Practical cryptography in high dimensional tori","author":"van Dijk, Marten","year":"2005","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540259107"},{"key":"30","isbn-type":"print","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/978-3-540-28628-8_10","article-title":"Asymptotically optimal communication for torus-based cryptography","author":"van Dijk, Marten","year":"2004","ISBN":"https:\/\/id.crossref.org\/isbn\/3540226680"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2013-82-281\/S0025-5718-2012-02625-1\/S0025-5718-2012-02625-1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2013-82-281\/S0025-5718-2012-02625-1\/S0025-5718-2012-02625-1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T17:25:52Z","timestamp":1776792352000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2013-82-281\/S0025-5718-2012-02625-1\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6,27]]},"references-count":30,"journal-issue":{"issue":"281","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["S0025-5718-2012-02625-1"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-2012-02625-1","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2012,6,27]]}}}