{"entities":{"Q284473":{"pageid":286240,"ns":120,"title":"Item:Q284473","lastrevid":60644046,"modified":"2026-04-10T18:15:16Z","type":"item","id":"Q284473","labels":{"en":{"language":"en","value":"Explicit primality criteria for \\(h \\cdot 2^n \\pm 1\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6581590"}},"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":"Q284473$830ED3A2-D491-4A4A-9974-70672ACB5C54","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cd17b3232f995b1f2684a583b4274b9b948d7b47","datavalue":{"value":{"text":"Explicit primality criteria for \\(h \\cdot 2^n \\pm 1\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q284473$584C2D32-94B7-4D8E-BE44-F8C7983052ED","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5171e2eaa7afc2934ca5bf9b8849c9c00d257696","datavalue":{"value":"1364.11014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q284473$49DE9420-A309-4034-B0EF-86C74427A534","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"075b0b9899510014362b726311850407e8758c36","datavalue":{"value":{"entity-type":"item","numeric-id":284471,"id":"Q284471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q284473$31434406-DFEE-4A9C-8700-EAE5847583BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ef479e0159218282d491084c78b5a43759ff37fb","datavalue":{"value":{"entity-type":"item","numeric-id":284472,"id":"Q284472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q284473$F88E5D7E-DE9D-466C-84C6-491D5DE07983","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"2af5fe3b27a04082f1eae9cf17090e68be06cc07","datavalue":{"value":{"entity-type":"item","numeric-id":194678,"id":"Q194678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q284473$814CB9AD-2063-4D3D-8EA7-14DB0F109949","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"520e6f0241f1a69086f50367d5722006ec0b624b","datavalue":{"value":{"time":"+2016-05-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":"Q284473$0DEBACE8-A6CC-4011-A8A6-0C9182E618CE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6eef03bc74c43fa57f93f7f7441f79b6b776b4d2","datavalue":{"value":"https://arxiv.org/abs/1306.4456","type":"string"},"datatype":"url"},"type":"statement","id":"Q284473$1E8F8E19-31EC-4AFC-B42B-1554DA09AD7C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f5492126398e1ddf0e8e00d7285568c890b3f47","datavalue":{"value":"11A51","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q284473$69568BD1-92A4-4A00-ABE6-21801DC76F71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0614cfe757af775354cacad4d1852bd334b9e455","datavalue":{"value":"11A15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q284473$72DA0C82-3289-4245-A810-9D1E90E18F09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ecf21397fdcced4e2aeef35f7ab4217f79a7d6ec","datavalue":{"value":"11Y11","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q284473$48E12B00-1CA2-4B1F-B283-DDABD25A2D15","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a0075f8dfef3d31187e3a9fe946765a81a1a357a","datavalue":{"value":"6581590","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q284473$EA21B747-02B2-4450-9098-42B161DEAB25","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"864ecd6b7699339c14f74412e5619a2d89288db0","datavalue":{"value":"primality tests","type":"string"},"datatype":"string"},"type":"statement","id":"Q284473$8351623E-EB1F-47AA-A535-1012C671599B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f415e07b903a15e315b6b515597008043be02db","datavalue":{"value":"generalized Lucasian sequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q284473$50742F90-19DE-4144-854D-E621B5850C52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4cb8018e2978a087422ccf8edbd3ac4e7d1bf741","datavalue":{"value":"seeds","type":"string"},"datatype":"string"},"type":"statement","id":"Q284473$3A7BB05C-BE9F-4EF7-B947-7FA913D1354D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5178d7c79dc49c860e9d89986e9ba5f27ae66e07","datavalue":{"value":"reciprocity laws","type":"string"},"datatype":"string"},"type":"statement","id":"Q284473$E1F641D9-4C89-409C-A05D-8939FD25C54B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q284473$5B4C7C9C-00AB-4009-9D3A-FEA3ECBB52B8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8892955fafe16ba1bddb104e5d82ec8889d70fd9","datavalue":{"value":{"entity-type":"item","numeric-id":1313210,"id":"Q1313210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q284473$DEC3B7C0-040C-400F-9979-2EDCCC132734","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":"Q284473$FFFD1C9A-D5B5-4C74-9EB4-CE12B0A6A237","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3c2bccb24b515e01e356d8d43901d7912991774e","datavalue":{"value":"W2963828264","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q284473$52AD6A65-D6E5-4DF8-9807-DCA5DE8ABCA5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e34c673d35aff55c8e065f163a63c5a57954c2f7","datavalue":{"value":{"entity-type":"item","numeric-id":4382830,"id":"Q4382830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q284473$143A45B1-AC26-46EC-AA95-FB924A3AD935","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32dc4231617de9248aa0395dff5e12cfaed911c5","datavalue":{"value":{"entity-type":"item","numeric-id":4813597,"id":"Q4813597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q284473$E85CB6C5-54C1-4034-9A50-2256423A081A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a48eeb62cc02a9febe6884f374e513c8ecddb778","datavalue":{"value":{"entity-type":"item","numeric-id":3137451,"id":"Q3137451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q284473$CCBEB0AD-8BE6-4547-B68B-58312C46C185","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e3e8bcd9ac407075ef6c156fbc648c056d47207","datavalue":{"value":{"entity-type":"item","numeric-id":3999066,"id":"Q3999066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q284473$A58D4F68-3C61-48B6-A903-C2520B580B43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d864ecf0887e3285d5a657ecba76076407dae52","datavalue":{"value":{"entity-type":"item","numeric-id":2548172,"id":"Q2548172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q284473$1AB7C6F7-869C-4B7A-8FC2-BA66CA1DEBB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b30d5e572a2001443c05483b553f3cfd7bc29775","datavalue":{"value":{"entity-type":"item","numeric-id":5690489,"id":"Q5690489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q284473$AC3BA56D-6C85-4269-A62C-6A1DA60840DC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"620589e4ef6a7726bfd4eea6c8713780c71b6062","datavalue":{"value":"10.5802/JTNB.928","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q284473$E6754502-9B4E-42DE-BB7F-6390BA07F408","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9bb76414808fbd284e8cbbb9c2038a1d771b1a95","datavalue":{"value":{"entity-type":"item","numeric-id":3417673,"id":"Q3417673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94ac80ef795a3608387e1d4369db9e4c77bee824","datavalue":{"value":{"amount":"+0.8356562","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q284473$E3E5FE2C-6A7E-4FCA-BA18-96D016A5A445","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6547ad479c1e3827f9b8b3f43a7c4e5bbe9bf5f2","datavalue":{"value":{"entity-type":"item","numeric-id":3625894,"id":"Q3625894"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4100df1dda4f9b6aa14ea99b74832b5406d2f445","datavalue":{"value":{"amount":"+0.8003341","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q284473$8536AD80-F3BE-4359-99E5-3387F4B1131E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"79c9ffc856ecf163e633e9b0dd2edf8155223762","datavalue":{"value":{"entity-type":"item","numeric-id":2330377,"id":"Q2330377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bce501b695673bf9a355248206b8401dfbcd37cd","datavalue":{"value":{"amount":"+0.79080904","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q284473$567760CC-1698-4FD4-B50F-4E231E32C4DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe826fe935505d9e1b94076f1b8cee356388291a","datavalue":{"value":{"entity-type":"item","numeric-id":3748328,"id":"Q3748328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9635d5efc4074400f33a83f8e6b86de37af1557f","datavalue":{"value":{"amount":"+0.790294","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q284473$1D511363-AEAE-4E65-ABB6-1C3D88945EC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4e0bde8ea729dacd60bdca250ebbfba9dfd8236","datavalue":{"value":{"entity-type":"item","numeric-id":5042431,"id":"Q5042431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7935a7f1a4002a1675e65e49d25edb8daead010d","datavalue":{"value":{"amount":"+0.78207314","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q284473$B31BBA60-EFCA-4FA0-8B8C-0B270F71FC14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"614de1b1319bc93281e59f28cb95e6038e634373","datavalue":{"value":{"entity-type":"item","numeric-id":5424045,"id":"Q5424045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35cf1b7524c5a0b8e53ddf2c12869aceb7a41ced","datavalue":{"value":{"amount":"+0.77968276","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q284473$F748A9DB-3948-4732-9C00-C0C7A1D3158E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"72f54d3b730461cbf2f2c803c4714591b743b599","datavalue":{"value":{"entity-type":"item","numeric-id":5109565,"id":"Q5109565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"87a8485a20911ba054d92c0ff7013567930a265c","datavalue":{"value":{"amount":"+0.7750428","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q284473$F2637263-FD4C-4A73-BC44-5C95813162B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe68f1a10187d4bbf32a10a4c6efc31bd8a216d9","datavalue":{"value":{"entity-type":"item","numeric-id":887438,"id":"Q887438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e59639e5e36e6ee9f75746398d5ef82f38063500","datavalue":{"value":{"amount":"+0.769578","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q284473$F4AB86E8-B37B-4FEB-B1F0-6BEFBBDD69F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c168466f53accc92e9fed49337a3bc50aa944e7","datavalue":{"value":{"entity-type":"item","numeric-id":4501051,"id":"Q4501051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"deba2b71eaa3244904e1966c57639f474d2d39ce","datavalue":{"value":{"amount":"+0.7572224","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q284473$1C852713-F71F-4159-AAB6-8255FE91C3AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de620ea12e4d7cd8c63d5aef78564380bd454a67","datavalue":{"value":{"entity-type":"item","numeric-id":3601262,"id":"Q3601262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f12e5d10171fafb5fe7113eb6a6c2bdb3e3f24c4","datavalue":{"value":{"amount":"+0.7475158","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q284473$151F0413-4F80-4AFC-BA14-C916845D55BA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"757128f4b37ca21d86d75a93d19d569970d8e2fd","datavalue":{"value":"\u00c9. Lucas, in the XIX century, proposed efficient deterministic primality tests for the two families of numbers \\(h2^n+1\\) and \\(h2^n-1\\). These Lucasian tests are given in term of recurrence sequences of integer numbers \\(\\{u_n\\}\\), which depends on a recurrence equation and an initial value, the \\textit{seed}, see [\\textit{H. C. Williams}, \u00c9douard Lucas and primality testing. New York, NY: John Wiley \\& Sons (1998; Zbl 1155.11363)].NEWLINENEWLINEThe Lucas-Lehmer test, for the Mersenne numbers \\(M_p=2^p-1\\), takes as seed \\(u_0=4\\) (a constant). \\textit{W. Bosma} [Math. Comp. 61, No. 203, 97--109 (1993; Zbl 0817.11060)] gave two tests for those two families when \\(h\\not \\equiv 0 \\bmod 3\\), using in both cases a seed depending only on \\(h\\) and not on \\(n\\) and \\textit{P. Berrizbeitia} and \\textit{T. G. Berry} [Math. Comput. 73, No. 247, 1559--1564 (2004; Zbl 1090.11004)] provide a test common to the two families which, assuming \\(h\\not \\equiv 0 \\bmod 5\\), uses a seed depending only on \\(h\\).NEWLINENEWLINEThe aim of the present paper is to give a similar result when \\(h\\not \\equiv 0 \\bmod 17\\). The paper introduces the notion of a \\textit{generalized Lucasian sequence} \\(\\{(T_k^1, \\dots ,T_k^f)\\}\\), defined from a given initial value (the seed) \\(\\{(T_0^1, \\ldots,T_0^f)\\}\\). The primality test (Theorem 3.1, stated in Section 3 and proved in Section 4) treated the two cases \\(h2^n\\pm 1\\) simultaneously and need two generalized Lucasian sequences and, for \\(h\\not \\equiv 0 \\bmod 17\\) fixed, two seeds (independents of \\(n\\)). The paper argues that ``our generalized Lucasian primality test improves the results of Berrizbeitia and Berry and Bosma'', since for instance when \\(h=15\\) those tests need infinitely many seeds.NEWLINENEWLINESection 5 studies the computational complexity of the primality test of Theorem 3.1 , proving that for \\(M=h2^n\\pm 1\\) this complexity is \\(\\tilde O(log^2M)\\) bit operations. The paper concludes with an open problem concerning the possibility, for arbitrary \\(h\\) of a generalized Lucasian primality test for the families \\(h2^n\\pm 1\\) with finitely many seeds depending only on \\(h\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q284473$6B29F26A-C625-459A-8E7D-8A0C8346658C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Explicit primality criteria for \\(h \\cdot 2^n \\pm 1\\)","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Explicit_primality_criteria_for_%5C(h_%5Ccdot_2%5En_%5Cpm_1%5C)"}}}}}