{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:27:46Z","timestamp":1750220866306,"version":"3.41.0"},"reference-count":6,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,2,16]],"date-time":"2019-02-16T00:00:00Z","timestamp":1550275200000},"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 Commun. Comput. Algebra"],"published-print":{"date-parts":[[2019,2,16]]},"abstract":"<jats:p>\n            We present an algorithm which computes the\n            <jats:italic>\n              D\n              <jats:sup>th<\/jats:sup>\n            <\/jats:italic>\n            term of a sequence satisfying a linear recurrence relation of order\n            <jats:italic>d<\/jats:italic>\n            over a field K in\n            <jats:italic>O<\/jats:italic>\n            (M(d\u0304) log(\n            <jats:italic>D<\/jats:italic>\n            ) + M(\n            <jats:italic>d<\/jats:italic>\n            ) log(\n            <jats:italic>d<\/jats:italic>\n            )) operations in K, where d\u0304 \u2264\n            <jats:italic>d<\/jats:italic>\n            is the degree of the squarefree part of the annihilating polynomial of the recurrence and M is the cost of polynomial multiplication in K. This is a refinement of the previously optimal result of\n            <jats:italic>O<\/jats:italic>\n            (M(\n            <jats:italic>d<\/jats:italic>\n            ) log(\n            <jats:italic>D<\/jats:italic>\n            )) operations, due to Fiduccia.\n          <\/jats:p>","DOI":"10.1145\/3313880.3313894","type":"journal-article","created":{"date-parts":[[2019,2,19]],"date-time":"2019-02-19T20:54:15Z","timestamp":1550609655000},"page":"100-103","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["A fast algorithm for solving linearly recurrent sequences"],"prefix":"10.1145","volume":"52","author":[{"given":"Seung Gyu","family":"Hyun","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephen","family":"Melczer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Catherine","family":"St-Pierre","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,2,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/860854.860870"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214007"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.2000.0370"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1994.1025"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087604.3087634"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"J. von zur Gathen and J. Gerhard. Modern Computer Algebra. Cambridge University Press Cambridge third edition 2013.   J. von zur Gathen and J. Gerhard. Modern Computer Algebra. Cambridge University Press Cambridge third edition 2013.","DOI":"10.1017\/CBO9781139856065"}],"container-title":["ACM Communications in Computer Algebra"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313880.3313894","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313880.3313894","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:23:46Z","timestamp":1750202626000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313880.3313894"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,16]]},"references-count":6,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,2,16]]}},"alternative-id":["10.1145\/3313880.3313894"],"URL":"https:\/\/doi.org\/10.1145\/3313880.3313894","relation":{},"ISSN":["1932-2240"],"issn-type":[{"type":"print","value":"1932-2240"}],"subject":[],"published":{"date-parts":[[2019,2,16]]},"assertion":[{"value":"2019-02-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}