{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T04:04:11Z","timestamp":1750478651192,"version":"3.41.0"},"reference-count":0,"publisher":"Cambridge University Press (CUP)","issue":"4-5","license":[{"start":{"date-parts":[[2004,9,24]],"date-time":"2004-09-24T00:00:00Z","timestamp":1095984000000},"content-version":"unspecified","delay-in-days":85,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2004,7]]},"abstract":"<jats:p>The Lehmer\u2013Euclid Algorithm is an improvement of the Euclid Algorithm when applied to large integers. The original Lehmer\u2013Euclid Algorithm replaces divisions on multi-precision integers by divisions on single-precision integers. Here we study a slightly different algorithm that replaces computations on <jats:inline-formula>$n$<\/jats:inline-formula>-bit integers by computations on <jats:inline-formula>$\\mu n$<\/jats:inline-formula>-bit integers. This algorithm depends on the truncation degree <jats:inline-formula>$\\mu\\in ]0, 1[$<\/jats:inline-formula> and is denoted as the <jats:inline-formula>${\\mathcal{LE}}_\\mu$<\/jats:inline-formula> algorithm. The original Lehmer\u2013Euclid Algorithm can be viewed as the limit of the <jats:inline-formula>${\\mathcal{LE}}_\\mu$<\/jats:inline-formula> algorithms for <jats:inline-formula>$\\mu \\to 0$<\/jats:inline-formula>. We provide here a precise analysis of the <jats:inline-formula>${\\mathcal{LE}}_\\mu$<\/jats:inline-formula> algorithm. For this purpose, we are led to study what we call the <jats:italic>Interrupted Euclid Algorithm<\/jats:italic>. This algorithm depends on some parameter <jats:inline-formula>$\\alpha \\in [0, 1]$<\/jats:inline-formula> and is denoted by <jats:inline-formula>${\\mathcal E}_{\\alpha}$<\/jats:inline-formula>. When running with an input <jats:inline-formula>$(a, b)$<\/jats:inline-formula>, it performs the same steps as the usual Euclid Algorithm, but it stops as soon as the current integer is smaller than <jats:inline-formula>$a^\\alpha$<\/jats:inline-formula>, so that <jats:inline-formula>${\\mathcal E}_{0}$<\/jats:inline-formula> is the classical Euclid Algorithm. We obtain a very precise analysis of the algorithm <jats:inline-formula>${\\mathcal E}_{\\alpha}$<\/jats:inline-formula>, and describe the behaviour of main parameters (number of iterations, bit complexity) as a function of parameter <jats:inline-formula>$\\alpha$<\/jats:inline-formula>. Since the Lehmer\u2013Euclid Algorithm <jats:inline-formula>${\\mathcal {LE}}_\\mu$<\/jats:inline-formula> when running on <jats:inline-formula>$n$<\/jats:inline-formula>-bit integers can be viewed as a sequence of executions of the Interrupted Euclid Algorithm <jats:inline-formula>${\\mathcal E}_{1\/2}$<\/jats:inline-formula> on <jats:inline-formula>$\\mu n $<\/jats:inline-formula>-bit integers, we then come back to the analysis of the <jats:inline-formula>${\\mathcal {LE}}_\\mu$<\/jats:inline-formula> algorithm and obtain our results.<\/jats:p>","DOI":"10.1017\/s0963548304006261","type":"journal-article","created":{"date-parts":[[2004,9,24]],"date-time":"2004-09-24T13:28:19Z","timestamp":1096032499000},"page":"499-536","source":"Crossref","is-referenced-by-count":4,"title":["Dynamical Analysis of the Parametrized Lehmer\u2013Euclid Algorithm"],"prefix":"10.1017","volume":"13","author":[{"given":"BENO\u00ceT","family":"DAIREAUX","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"BRIGITTE","family":"VALL\u00c9E","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2004,9,24]]},"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548304006261","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,20]],"date-time":"2025-06-20T15:46:42Z","timestamp":1750434402000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548304006261\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,7]]},"references-count":0,"journal-issue":{"issue":"4-5","published-print":{"date-parts":[[2004,1]]}},"alternative-id":["S0963548304006261"],"URL":"https:\/\/doi.org\/10.1017\/s0963548304006261","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2004,7]]}}}