{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:31:27Z","timestamp":1764981087260,"version":"3.46.0"},"reference-count":16,"publisher":"Walter de Gruyter GmbH","issue":"4","license":[{"start":{"date-parts":[[2018,9,20]],"date-time":"2018-09-20T00:00:00Z","timestamp":1537401600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018,12,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>We provide a new heuristic polynomial time algorithm that computes short paths between arbitrary pairs of vertices in Lubotzky\u2013Philipps\u2013Sarnak\u2019s Ramanujan graphs.\nThe paths returned by our algorithm are shorter by a factor approximately 16\/7 compared to previous work, and they are close to optimal for vertices corresponding to diagonal matrices.\nOur results also lead to an improved cryptanalysis of the Charles\u2013Goren\u2013Lauter hash function.<\/jats:p>","DOI":"10.1515\/jmc-2017-0051","type":"journal-article","created":{"date-parts":[[2018,9,20]],"date-time":"2018-09-20T05:02:42Z","timestamp":1537419762000},"page":"191-202","source":"Crossref","is-referenced-by-count":3,"title":["Better path-finding algorithms in LPS Ramanujan graphs"],"prefix":"10.1515","volume":"12","author":[{"given":"Eduardo","family":"Carvalho Pinto","sequence":"first","affiliation":[{"name":"Ecole Polytechnique , Paris , France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3482-6743","authenticated-orcid":false,"given":"Christophe","family":"Petit","sequence":"additional","affiliation":[{"name":"School of Computer Science , University of Birmingham , Birmingham , United Kingdom"}]}],"member":"374","published-online":{"date-parts":[[2018,9,20]]},"reference":[{"key":"2025120600294185961_j_jmc-2017-0051_ref_001_w2aab3b7b2b1b6b1ab1b8b1Aa","unstructured":"A.  Blass, A.  Bocharov and Y.  Gurevich,\nOptimal ancilla-free Pauli+V circuits for axial rotations,\npreprint (2014),\nhttps:\/\/arxiv.org\/abs\/1412.1033v1."},{"key":"2025120600294185961_j_jmc-2017-0051_ref_002_w2aab3b7b2b1b6b1ab1b8b2Aa","doi-asserted-by":"crossref","unstructured":"D.  Charles and K.  Lauter,\nComputing modular polynomials,\nLMS J. Comput. Math. 8 (2005), 195\u2013204.\n10.1112\/S1461157000000954","DOI":"10.1112\/S1461157000000954"},{"key":"2025120600294185961_j_jmc-2017-0051_ref_003_w2aab3b7b2b1b6b1ab1b8b3Aa","doi-asserted-by":"crossref","unstructured":"D. X.  Charles, K. E.  Lauter and E. Z.  Goren,\nCryptographic hash functions from expander graphs,\nJ. Cryptology 22 (2009), no. 1, 93\u2013113.\n10.1007\/s00145-007-9002-x","DOI":"10.1007\/s00145-007-9002-x"},{"key":"2025120600294185961_j_jmc-2017-0051_ref_004_w2aab3b7b2b1b6b1ab1b8b4Aa","unstructured":"G.  Cornacchia,\nSu di un metodo per la risoluzione in numeri interi dell\u2019 equazione \u2211h=0nch\u2062xn-h\u2062yh=p{\\sum_{h=0}^{n}c_{h}x^{n-h}y^{h}=p},\nGiornale Mat. Battaglini 46 (1903), 33\u201390."},{"key":"2025120600294185961_j_jmc-2017-0051_ref_005_w2aab3b7b2b1b6b1ab1b8b5Aa","unstructured":"G.  Davidoff, P.  Sarnak and A.  Valette,\nElementary Number Theory, Group Theory, and Ramanujan Graphs,\nLondon Math. Soc. Stud. Texts 55,\nCambridge University Press, Cambridge, 2003."},{"key":"2025120600294185961_j_jmc-2017-0051_ref_006_w2aab3b7b2b1b6b1ab1b8b6Aa","unstructured":"C. Fieker A.  Steel, W.  Bosma and J. J.  Cannon,\nHandbook of Magma Functions, edition 2.20,\n2013, http:\/\/http:\/\/magma.maths.usyd.edu.au\/magma\/."},{"key":"2025120600294185961_j_jmc-2017-0051_ref_007_w2aab3b7b2b1b6b1ab1b8b7Aa","doi-asserted-by":"crossref","unstructured":"H. A.  Helfgott,\nGrowth and generation in SL2\u2062(\u2124\/p\u2062\u2124){\\rm SL}_{2}(\\mathbb{Z}\/p\\mathbb{Z}),\nAnn. of Math. (2) 167 (2008), no. 2, 601\u2013623.","DOI":"10.4007\/annals.2008.167.601"},{"key":"2025120600294185961_j_jmc-2017-0051_ref_008_w2aab3b7b2b1b6b1ab1b8b8Aa","doi-asserted-by":"crossref","unstructured":"S.  Hoory, N.  Linial and A.  Wigderson,\nExpander graphs and their applications,\nBull. Amer. Math. Soc. (N.S.) 43 (2006), no. 4, 439\u2013561.\n10.1090\/S0273-0979-06-01126-8","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"2025120600294185961_j_jmc-2017-0051_ref_009_w2aab3b7b2b1b6b1ab1b8b9Aa","doi-asserted-by":"crossref","unstructured":"A.  Lubotzky, R.  Phillips and P.  Sarnak,\nRamanujan graphs,\nCombinatorica 8 (1988), no. 3, 261\u2013277.\n10.1007\/BF02126799","DOI":"10.1007\/BF02126799"},{"key":"2025120600294185961_j_jmc-2017-0051_ref_010_w2aab3b7b2b1b6b1ab1b8c10Aa","doi-asserted-by":"crossref","unstructured":"D.  Micciancio and S.  Goldwasser,\nComplexity of Lattice Problems. A Cryptographic Perspective,\nKluwer Int. Ser. Eng. Comp. Sci. 671,\nKluwer Academic Publishers, Boston, 2002.","DOI":"10.1007\/978-1-4615-0897-7_8"},{"key":"2025120600294185961_j_jmc-2017-0051_ref_011_w2aab3b7b2b1b6b1ab1b8c11Aa","doi-asserted-by":"crossref","unstructured":"C.  Petit, K.  Lauter and J.-J.  Quisquater,\nFull cryptanalysis of LPS and Morgenstern hash functions,\nSecurity and Cryptography for Networks\u2014SCN 2008,\nLecture Notes in Comput. Sci. 5229,\nSpringer, Berlin (2008), 263\u2013277.","DOI":"10.1007\/978-3-540-85855-3_18"},{"key":"2025120600294185961_j_jmc-2017-0051_ref_012_w2aab3b7b2b1b6b1ab1b8c12Aa","unstructured":"N. J.  Ross,\nOptimal ancilla-free Clifford+V approximation of z-rotations,\npreprint (2015),\nhttps:\/\/arxiv.org\/abs\/1409.4355v2."},{"key":"2025120600294185961_j_jmc-2017-0051_ref_013_w2aab3b7b2b1b6b1ab1b8c13Aa","unstructured":"N. T.  Sardari,\nComplexity of strong approximation on the sphere,\npreprint (2017),\narxiv.org\/abs\/1703.02709."},{"key":"2025120600294185961_j_jmc-2017-0051_ref_014_w2aab3b7b2b1b6b1ab1b8c14Aa","unstructured":"N. T.  Sardari,\nThe least prime number represented by a binary quadratic form,\npreprint (2018),\narxiv.org\/abs\/1803.03218."},{"key":"2025120600294185961_j_jmc-2017-0051_ref_015_w2aab3b7b2b1b6b1ab1b8c15Aa","doi-asserted-by":"crossref","unstructured":"P.  Sarnak,\nSome Applications of Modular Forms,\nCambridge Tracts in Math. 99,\nCambridge University Press, Cambridge, 1990.","DOI":"10.1017\/CBO9780511895593"},{"key":"2025120600294185961_j_jmc-2017-0051_ref_016_w2aab3b7b2b1b6b1ab1b8c16Aa","doi-asserted-by":"crossref","unstructured":"J.-P.  Tillich and G.  Z\u00e9mor,\nCollisions for the LPS expander graph hash function,\nAdvances in Cryptology\u2014EUROCRYPT 2008,\nLecture Notes in Comput. Sci. 4965,\nSpringer, Berlin (2008), 254\u2013269.","DOI":"10.1007\/978-3-540-78967-3_15"}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.degruyter.com\/view\/j\/jmc.2018.12.issue-4\/jmc-2017-0051\/jmc-2017-0051.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2017-0051\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2017-0051\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:29:54Z","timestamp":1764980994000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2017-0051\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,20]]},"references-count":16,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2018,6,19]]},"published-print":{"date-parts":[[2018,12,1]]}},"alternative-id":["10.1515\/jmc-2017-0051"],"URL":"https:\/\/doi.org\/10.1515\/jmc-2017-0051","relation":{},"ISSN":["1862-2984","1862-2976"],"issn-type":[{"type":"electronic","value":"1862-2984"},{"type":"print","value":"1862-2976"}],"subject":[],"published":{"date-parts":[[2018,9,20]]}}}