{"entities":{"Q5943093":{"pageid":8119895,"ns":120,"title":"Item:Q5943093","lastrevid":47665444,"modified":"2026-01-02T09:18:28Z","type":"item","id":"Q5943093","labels":{"en":{"language":"en","value":"A lower bound for primality"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1642221"}},"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":"Q5943093$6C1AA6C6-BE79-4E2A-9E49-359BD14A90FB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c38dd670ef865e00ed2796abedd77a6b2acee352","datavalue":{"value":{"text":"A lower bound for primality","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5943093$45AAB434-8169-4842-8EC7-B5C07AB10244","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c4b3fa32333536bbb27e3ac921edca57c783d4d8","datavalue":{"value":"1032.11058","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5943093$FE5577BA-C860-413C-80D5-EA227A7D3CB0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"86eae0bd36f68e0853fe5ab9e6c133a110babb03","datavalue":{"value":{"entity-type":"item","numeric-id":1058525,"id":"Q1058525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943093$1F091E7E-1508-4F05-86C3-413096337A24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"93f09421b6aff8e8d7720ab7e9d35f10a9deb5a2","datavalue":{"value":{"entity-type":"item","numeric-id":1112076,"id":"Q1112076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943093$E5A855B5-80C9-4D9C-A7EE-8F5072EB4C1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"165c8921a441245575fe00da025ab28703ff633a","datavalue":{"value":{"entity-type":"item","numeric-id":240100,"id":"Q240100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943093$3E07C1FF-1164-4530-B3DB-91B31EA005FA","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943093$A280F601-457F-48AF-A9E4-DD884BBA963E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"69811ff9e0a841326357127702cd41d8562484a0","datavalue":{"value":{"time":"+2003-05-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5943093$6FE050EB-78AD-4CAC-89B2-5E2BED3E30CF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"efd727c7711ac6c2af6b95dbc9cafad2af8c02ef","datavalue":{"value":"The main result of the paper is that primality testing, gcd computation and square-free computation is not in \\(AC^0\\), that is, can not be accomplished by constant depth, polynomial-size circuits of AND, OR and NOT gates. The technique used by the authors is to reduce the functions that have circuit lower bound known to divisibility and then, using a randomized reduction, to primality testing.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5943093$9D21BA4C-D02B-4977-9177-D575D31BF91A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2fbaabd45ced54cadc0390bc9cd343b83bec0729","datavalue":{"value":{"entity-type":"item","numeric-id":307804,"id":"Q307804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943093$A16818C1-C7A1-463E-B273-D88CA788580E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ecf21397fdcced4e2aeef35f7ab4217f79a7d6ec","datavalue":{"value":"11Y11","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5943093$ED579B25-001B-4C5B-8C56-4691434B27BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5943093$D77092E5-B8C7-490F-869B-3AA59731A4FF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"177c4c60d94d744ba37e49cfe3c371458284f682","datavalue":{"value":"1642221","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5943093$3FAE23EB-1D51-4F8F-B57F-532C1C9D04D0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b598197b2e9d8b7b3926c71a30f45448cf281085","datavalue":{"value":"primality","type":"string"},"datatype":"string"},"type":"statement","id":"Q5943093$1A462A6A-80CA-4FAC-BDC3-95AF88D1BF06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1f1814ebfb0c5873f215208cab188392d4def9a","datavalue":{"value":"lower bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q5943093$48C0F48B-D5BB-4AAA-A28D-F1D1F5ECC05F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bcaef8b48097d50a08be2219f6311c65284708bf","datavalue":{"value":"circuit","type":"string"},"datatype":"string"},"type":"statement","id":"Q5943093$D67A5C8B-0B7E-4F24-B030-D02B5B59FA95","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":"Q5943093$739CC53A-ADC5-4B03-9E09-F800A3B93000","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1db378e1c5c60f2d00d8e7f9f0eae7117abc9ccd","datavalue":{"value":"https://doi.org/10.1006/jcss.2000.1725","type":"string"},"datatype":"url"},"type":"statement","id":"Q5943093$5DCB8679-B81D-48A1-B8E0-ABD01377B177","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f5a7094784e24e963b71a2ea858b3c164d3e901a","datavalue":{"value":"W1920190523","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5943093$E6FB12DA-2485-4E74-8A96-FC531C0137CD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c115548701848a04f92f389f92d61be34267bf97","datavalue":{"value":{"entity-type":"item","numeric-id":594912,"id":"Q594912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943093$33D68859-8956-41C7-B1A3-558D49D71EF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3612079c5d5534ce095221788cd7ac5e361abc16","datavalue":{"value":{"entity-type":"item","numeric-id":4527042,"id":"Q4527042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943093$12B9F2C0-D650-4051-AFC8-0F6A1E1717BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f5d817fcded45c0d7d6169802a7ae39651b45a7a","datavalue":{"value":{"entity-type":"item","numeric-id":1276160,"id":"Q1276160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943093$F4B622A4-DAB0-431F-980F-872622D8C6F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00fc7604b92ee4161b549e50b4b7a4339a9979ec","datavalue":{"value":{"entity-type":"item","numeric-id":4938669,"id":"Q4938669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943093$CA50A112-9F08-4CB2-AC1E-72C95FE843E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8570a1ea6427c88fac451539a9d46d29568cdb6d","datavalue":{"value":{"entity-type":"item","numeric-id":1590081,"id":"Q1590081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943093$E3468BF1-C6C4-487A-A76D-FD35AD85E130","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e49c1c2cc487d0f3c5ab92bcc2e1f114d4bc0f3","datavalue":{"value":{"entity-type":"item","numeric-id":4251041,"id":"Q4251041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943093$21816C57-4F38-4C5D-B560-E71317A97129","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe2b5d0ea41e438a55771c82bd1fff2d6a01f091","datavalue":{"value":{"entity-type":"item","numeric-id":1096587,"id":"Q1096587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943093$AC64F380-E643-4871-86C1-E5D8BEC3C023","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3aa57810f0528ce2438cd0f484c242c53bb4e54","datavalue":{"value":{"entity-type":"item","numeric-id":3325043,"id":"Q3325043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943093$22D2786C-AFA8-420F-A601-D81DFC905A64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"485f65457c2cee586d70f7d74905dc494ee38ddc","datavalue":{"value":{"entity-type":"item","numeric-id":1235507,"id":"Q1235507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943093$B665A308-F13E-4F6A-B265-F30583708EA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4bd77ad8a38bffafafd4627b2f2c4c6bd9e1bd0e","datavalue":{"value":{"entity-type":"item","numeric-id":5548359,"id":"Q5548359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943093$D8853DFE-FE86-4C9C-B3CB-CCB3D222F717","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"13a870c969fda53b0c0c9004d9584cc75ca83354","datavalue":{"value":{"entity-type":"item","numeric-id":5900807,"id":"Q5900807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943093$8A606293-DC75-4D98-BF77-18278CF13EE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"122c8ada885963c6405a5c1b36cfb97f07059042","datavalue":{"value":{"entity-type":"item","numeric-id":1353986,"id":"Q1353986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943093$8BBA587B-1415-474F-8D7F-4D04CD37DABA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"582da33d96a2933573c76d6d04e5e7ed2ba5333b","datavalue":{"value":{"entity-type":"item","numeric-id":1178201,"id":"Q1178201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943093$AB2D5CC9-CB88-41F7-99B1-247E4CB9797A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3589abe08309ee0c80b87d4a4fa6a10bf824c734","datavalue":{"value":{"entity-type":"item","numeric-id":1235011,"id":"Q1235011"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943093$BA4B08C8-7657-4A2B-B843-6D4D9ECEB525","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb96b6c4a3a74d4635765b706e544a56f42f0711","datavalue":{"value":{"entity-type":"item","numeric-id":4759038,"id":"Q4759038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943093$197698C5-11E3-4540-8202-A76F62A0FB0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"068aeb7b51732142e58201ce0fde4f5a216caba6","datavalue":{"value":{"entity-type":"item","numeric-id":3828063,"id":"Q3828063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943093$0A72F854-DDFC-43FB-8FA6-2C6F5A7DC8CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad00a83b5d740d9489736b8014faafa0c722caaa","datavalue":{"value":{"entity-type":"item","numeric-id":3248054,"id":"Q3248054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943093$4D39CF28-025B-433A-943D-02BEC9AF0B64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39fc746819d6a86d4542ba3a284ce0ca1127563e","datavalue":{"value":{"entity-type":"item","numeric-id":1135871,"id":"Q1135871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943093$41F722A7-09D3-4EAB-B23B-9710E27A3DA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ffb7c4897464eade24b984dc253233d6968fb77","datavalue":{"value":{"entity-type":"item","numeric-id":1095871,"id":"Q1095871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943093$F7A974C3-3DD0-43CF-814D-3CBF0D2C1D48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"737d0e769bc06912eb5b7c81a62e7bbb676b4bc4","datavalue":{"value":{"entity-type":"item","numeric-id":1276548,"id":"Q1276548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943093$37A3585B-C16D-4ADF-B37E-563E8FE765B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8706e2a690d5177037c83ceb7a917b1bfcfb5f56","datavalue":{"value":{"entity-type":"item","numeric-id":4113883,"id":"Q4113883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943093$B9666169-1063-4DD3-B047-119AC5BC813A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f5d8ebd3ef53d7996f7c569cf6663fe1170b13ac","datavalue":{"value":{"entity-type":"item","numeric-id":4302435,"id":"Q4302435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943093$1BAF2727-3802-40C5-8EF7-B0E865766184","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f24672644a3c2f75158337dd684a4be75f0f6713","datavalue":{"value":"10.1006/JCSS.2000.1725","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5943093$E00B4431-3A85-43B3-8BF0-D08F82C0A6F7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b6e973937bc7362208b83daca6ede1925d34616e","datavalue":{"value":{"entity-type":"item","numeric-id":1854439,"id":"Q1854439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e63be559d5bd014cb7d90c894cf13a67a1ddd5a0","datavalue":{"value":{"amount":"+0.7673494815826416","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":"Q5943093$5081964B-21E4-4D47-A6BE-DCB1D43B75C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"593e869c60b11135bdb427026bea82a36da7bbfd","datavalue":{"value":{"entity-type":"item","numeric-id":3452497,"id":"Q3452497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cecb36097ba4b30f08c74405d6c708eab6997614","datavalue":{"value":{"amount":"+0.7593784332275391","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":"Q5943093$8A1FC131-8A01-4767-A14A-94310C690EAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a870c416d1a8a430a9fb975e94d4c3ecb7e5f837","datavalue":{"value":{"entity-type":"item","numeric-id":1178201,"id":"Q1178201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f0a11648c0c45dab7a7aba83d39533100784e20e","datavalue":{"value":{"amount":"+0.7573673129081726","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":"Q5943093$FD1DB560-0CB7-48F1-A6A9-EA7DAFCCC443","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3afa63dce86b098db843bb9dbf4777dcf9d60d65","datavalue":{"value":{"entity-type":"item","numeric-id":1885040,"id":"Q1885040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"224e2b93b28b5b9436366e6f6f639c47d1b4d33b","datavalue":{"value":{"amount":"+0.7546603083610535","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":"Q5943093$65D11213-1DE8-4DB7-B455-1B77BC66DA93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17f1e97b4a248cdb3ac51e234dc022435b9de226","datavalue":{"value":{"entity-type":"item","numeric-id":4284231,"id":"Q4284231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"939082b927dd8408f89a5a90f1c0138412305126","datavalue":{"value":{"amount":"+0.7539461851119995","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":"Q5943093$671C1541-9740-4F2C-A43B-D025ECECD004","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5943093","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5943093"}}}}}