{"entities":{"Q1994923":{"pageid":2005665,"ns":120,"title":"Item:Q1994923","lastrevid":78337745,"modified":"2026-05-06T11:21:15Z","type":"item","id":"Q1994923","labels":{"en":{"language":"en","value":"A refinement of M\u00fcller's cube root algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7312696"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1994923$90EF4C83-568C-4EA9-BA35-78DA029060E5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"075f3e69e9306ecb4a37840ae3a85c6e76a5b49c","datavalue":{"value":{"text":"A refinement of M\u00fcller's cube root algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1994923$7D836EC2-065D-4744-B98D-FC00363B7179","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6067a011c6415af767cb4df652700583cc36cdd6","datavalue":{"value":"1473.11217","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1994923$9ECC2F8F-4798-4ABF-9101-C922511591FE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fe9ba1d3987737329512b296d74440f5b7a2902e","datavalue":{"value":{"entity-type":"item","numeric-id":1994922,"id":"Q1994922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1994923$19716CFD-55DF-4FCC-B3D9-11C59083AE89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f17c887fa7c17f603948924252951a446472597b","datavalue":{"value":{"entity-type":"item","numeric-id":676286,"id":"Q676286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1994923$98DF5C74-D6AB-453A-A1E7-9DB757C3D917","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c8e77ed48ab08af59a4492a775e7c85fabd1b576","datavalue":{"value":{"entity-type":"item","numeric-id":317405,"id":"Q317405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1994923$09FFF723-693F-4B87-9A17-27D8A1C7C060","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"33122a93dfb64681be222c65bf841053fa198b88","datavalue":{"value":{"entity-type":"item","numeric-id":165874,"id":"Q165874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1994923$6CBD1B29-3882-4E61-B768-A43D082A4F0B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"62c65c68b7bf9ecbb68d021649cd5dea931c0173","datavalue":{"value":{"time":"+2021-02-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1994923$4A010330-35B9-4143-82A9-7F8B7CF32467","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"20b875a855ad362e55e4222b8787ea0b4dee1b50","datavalue":{"value":"For a prime number \\(p\\), finding cube roots in the finite field \\(\\mathbb{F}_p\\) has several applications in computational number theory. For instance, pairing based cryptosystems (see [\\textit{D. Boneh} and \\textit{M. Franklin}, Lect. Notes Comput. Sci. 2139, 213--229 (2001; Zbl 1002.94023)] and [\\textit{I. Duursma} and \\textit{H.-S. Lee}, Lect. Notes Comput. Sci. 2894, 111--123 (2003; Zbl 1189.11056)]) using elliptic and hyperelliptic curves requires basic arithmetic operations including cube root computations.  Two standard algorithms for cube root extraction in finite fields are available; Adleman-Manders-Miller (AMM) algorithm which is a generalization of the Tonelli-Shanks square root algorithm, and the Cipolla-Lehmer algorithm. The complexity of the AMM algorithm is \\(O(\\nu_3(p-1)(\\log p)^3)\\) bit additions, where \\(\\nu_3(p-1)\\) is the largest nonnegative integer \\(e\\) such that \\(3^e\\) divides \\(p-1\\). If \\(\\nu_3(p-1) \\approx \\log p\\), we get the worst time complexity \\(O((\\log p)^4)\\). However, the complexity of the Cipolla-Lehmer algorithm is \\(O((\\log p)^3)\\), and it does not depend on \\((\\nu_3(p-1)\\). It follows that, compared with the Cipolla-Lehmer algorithm, the AMM algorithm becomes inefficient for primes \\(p\\) with large \\((\\nu_3(p-1)\\).  \\textit{H. C. Williams} [in: Proc. 3rd Southeast. Conf. Combinat., Graph Theory, Computing, Florida Atlantic Univ., Boca Raton. 451--462 (1972; Zbl 0265.10001)] gave a \\(q^{\\mathrm{th}}\\) root algorithm, requiring \\(22 \\log p\\) multiplications. A refinement of this algorithm was given in [\\textit{K. S. Williams} and \\textit{K. Hardy}, Math. Comput. 61, No. 203, 475--483 (1993; Zbl 0782.11040)] by Williams-Hardy. This algorithm requires \\(14.5 \\log p\\) multiplications.  \\textit{S. M\u00fcller} [Fields Inst. Commun. 41, 293--304 (2004; Zbl 1089.11069)] gave a fast algorithm which needs only \\(8.5 \\log p\\) multiplications.  In this paper, the authors present an algorith (an improvement of M\u00fcller's algorithm) which needs \\(7.5 \\log p\\) multiplications in the field \\(\\mathbb{F}_p\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1994923$C99FFD3D-5D4C-4440-BC1B-C63542EEE1DC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b075f07c559a8304fe6fd3ca13dbfedf00a01341","datavalue":{"value":{"entity-type":"item","numeric-id":232463,"id":"Q232463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1994923$CA1EAEF4-A065-4C9C-9C2D-D2834992B800","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5005488ac12471348bfecb95099a57fd4da722ac","datavalue":{"value":"11T06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1994923$66EEBF18-DFDA-4C1E-978F-7F0E2A942F47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1994923$78971838-5118-45B4-98BD-5B6E6E40344A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1994923$EDA41C46-FE58-4E8C-A992-279856DACD7E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5adaf6c9cfaa30685aa853af2ca94cd2de191264","datavalue":{"value":"7312696","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1994923$A3693B83-F941-4AF1-908A-2E2D8A343E1D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a3711b386902559bb22bf67091b7eca92012716a","datavalue":{"value":"finite field","type":"string"},"datatype":"string"},"type":"statement","id":"Q1994923$1C3D25BB-918F-4AA5-ABFB-BC479DF6FA3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"30b1d76ce3403466b85d66369f5b303403893118","datavalue":{"value":"cube root","type":"string"},"datatype":"string"},"type":"statement","id":"Q1994923$AC5CD848-F74D-4293-84A2-8D627CF99157","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"94a6d72e97e338df2715257c20ef57ace0f129ed","datavalue":{"value":"linear recurrence relation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1994923$3363C997-F83A-43A1-B189-FC34D099287E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4af892502956ac550f5d1fff86935bd903ede7e6","datavalue":{"value":"Cipolla-Lehmer algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1994923$F9C71D0E-845A-4441-AB59-263FB2F80987","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1994923$43AE9F80-11A8-4FC0-8073-86B8EB60B1A9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b05d856b7c62375363b4c0e48e6c2820d669a222","datavalue":{"value":"https://doi.org/10.1016/j.ffa.2020.101708","type":"string"},"datatype":"url"},"type":"statement","id":"Q1994923$EFB2684A-B64A-432B-9EE7-A7F6A3021276","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"117edafdf873053f4d26e98646cd0b8787f4fb57","datavalue":{"value":"W3040926342","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1994923$521D69E2-7A59-4EB0-9A38-803C5824EFA5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d708a4a38b2b92b479b4b0e9d1e701a6d375848a","datavalue":{"value":{"entity-type":"item","numeric-id":4783728,"id":"Q4783728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1994923$DFE08818-01B5-4733-B58E-DBDF5AFF95F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e71281c26f63c55fc2a5b754403b550a1d18e8e6","datavalue":{"value":{"entity-type":"item","numeric-id":2345923,"id":"Q2345923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1994923$542D68AC-A719-43E1-8835-E3C864895240","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b64d3c98f637cc0eaa762b4996f036df95dd65da","datavalue":{"value":{"entity-type":"item","numeric-id":2456564,"id":"Q2456564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1994923$35688FAB-5589-4986-99C5-911B476F16CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9ce947291e6c0c95aba74026c4e45b8795e3ce4","datavalue":{"value":{"entity-type":"item","numeric-id":5902377,"id":"Q5902377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1994923$FC6905CB-9371-4510-A2A1-1164A7C5D166","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb463df0def3236ef95738636b3e4bea503e063d","datavalue":{"value":{"entity-type":"item","numeric-id":4503477,"id":"Q4503477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1994923$8EBE7A3B-D807-4C09-962A-13B9B432BCA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"19d34ace1aa4ba6fec165d3aae2fbb06103b5686","datavalue":{"value":{"entity-type":"item","numeric-id":5617656,"id":"Q5617656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1994923$F8D6E421-D693-4F5C-8C6A-17913A5E6088","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b44778fe6ddbbe0a76c6affd85e69ebf341affff","datavalue":{"value":{"entity-type":"item","numeric-id":4664853,"id":"Q4664853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1994923$41505603-81F9-4286-AF07-BCDAEA532F3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23284f6aa1f5a0314ad839b56b9de3ad21fa0de6","datavalue":{"value":{"entity-type":"item","numeric-id":4063214,"id":"Q4063214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1994923$00B45642-0335-4E16-ADC6-F2A6F678084F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed1d1b31b9e19117e208fbabad5b33aca12f8ae3","datavalue":{"value":{"entity-type":"item","numeric-id":5682381,"id":"Q5682381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1994923$85955BAD-7B92-42A4-AD60-811D0D37697A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57181617dc4271d4682e144dfa243e76e32e9170","datavalue":{"value":{"entity-type":"item","numeric-id":3137483,"id":"Q3137483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1994923$D87B6866-12DC-4C21-8813-D859E1780627","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c2234f8e30b19f05a72397fce29482dea5cb48f7","datavalue":{"value":"10.1016/J.FFA.2020.101708","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1994923$66930A74-F400-4FDD-BCEB-A118791386DF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a4de07c9f9b24a9218922cfe1ac990f41b1ab7b4","datavalue":{"value":{"entity-type":"item","numeric-id":4664853,"id":"Q4664853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3fa3de0e88ca6e4f0fcbdeede1b26e27bf506c1f","datavalue":{"value":{"amount":"+0.8851180672645569","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1994923$010FF494-FB01-4F5F-8AA4-5AFD5CF83D10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77427aafe48e5c3469eef3dc0754e694ddad809c","datavalue":{"value":{"entity-type":"item","numeric-id":2345923,"id":"Q2345923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb336ae1dbe8b8f2c4cc403c8a0d9b21fc46bcdf","datavalue":{"value":{"amount":"+0.8565554618835449","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1994923$EC387530-B2D6-4881-B34D-34C91AB3417F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e2cf3a58769b98ab3cb9c1b99510e9f967218a0","datavalue":{"value":{"entity-type":"item","numeric-id":1614110,"id":"Q1614110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"85baedb6b18132dd4df9f0b51df4502af488d024","datavalue":{"value":{"amount":"+0.8415110111236572","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1994923$11C1E70A-3939-409B-878C-5E98CA5E4959","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"107b0a8a70e2cce68eb55bb88b34e4b587cfd60e","datavalue":{"value":{"entity-type":"item","numeric-id":3137483,"id":"Q3137483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"85baedb6b18132dd4df9f0b51df4502af488d024","datavalue":{"value":{"amount":"+0.8415110111236572","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1994923$C1DF0529-EA38-45D1-9E47-34C6119BCF87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0bc5a1e5b6cced3e896c61702a34e03eedec79c2","datavalue":{"value":{"entity-type":"item","numeric-id":4968635,"id":"Q4968635"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c6c1be2992d39f8ceaf71e4fa6a2ef6f9047938b","datavalue":{"value":{"amount":"+0.8268527388572693","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1994923$86D30424-A41F-4BD7-8B1C-F147E4253453","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A refinement of M\u00fcller's cube root algorithm","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_refinement_of_M%C3%BCller%27s_cube_root_algorithm"}}}}}