{"entities":{"Q2023317":{"pageid":2034059,"ns":120,"title":"Item:Q2023317","lastrevid":72425823,"modified":"2026-04-14T04:49:39Z","type":"item","id":"Q2023317","labels":{"en":{"language":"en","value":"Integer factoring and compositeness witnesses"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7342057"}},"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":"Q2023317$7BDBC178-30B2-43B3-A46C-343AD68336B1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9e270ab383da378941e7ea94e95df85b5211f07e","datavalue":{"value":{"text":"Integer factoring and compositeness witnesses","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2023317$8BB856A6-8A2C-4A70-931F-B51FB321970C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f72d49343f250aa264b0240a478464ef70bf4032","datavalue":{"value":"1468.11244","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2023317$AC942211-4EBA-433D-A9F6-07B0B1E506CA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5d29a642488bc71a1d9a7e3ad688226b491d7bc2","datavalue":{"value":{"entity-type":"item","numeric-id":445243,"id":"Q445243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2023317$B6B0D52F-B495-4A2E-ADA8-A46E906F4F03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"80ec4495a41202a2572f1d37636eeb0070bf9804","datavalue":{"value":{"entity-type":"item","numeric-id":593082,"id":"Q593082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2023317$81624B1E-C2B8-42A6-B5EE-1CD35606D382","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52d43017492cad5b25a46de83afd30a61ffd99d6","datavalue":{"value":{"entity-type":"item","numeric-id":269100,"id":"Q269100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2023317$0ABA9E47-997C-4166-8834-5CB372E0561D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"960dc4bf51b8f5076beb0d650fe9e65aae11ca84","datavalue":{"value":{"time":"+2021-05-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2023317$41B86194-F32B-4B2F-BDF4-4420EB4E94CD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b06a4f31b12e884d179920c94fad38a944637085","datavalue":{"value":"An increasingly popular approach to the integer factorization problem is the study of its relations to other difficult tasks in algorithmic number theory. One such example is the computation of Euler's totient function \\(\\varphi\\). It is a well-known open problem to find an unconditional, deterministic, polynomial-time algorithm for factoring \\(N\\in\\mathbb{N}\\) under the assumption that \\(\\varphi(N)\\) is known. In this context, the authors present several reductions from integer factoring to problems related to \\(\\varphi\\), such as computing \\(\\varphi(N)\\), multiples of \\(\\varphi(N)\\), the factorization of \\(\\varphi(N)\\) or a small number of iterates of \\(\\varphi\\). All these reductions are unconditional, deterministic and polynomial-time, but fail for certain inputs, the so-called ``hard'' integers. While results of this type have already been known, the contribution of the present paper is the improvement of the upper bounds for the number of hard integers.  The core idea is based on the notions of Fermat-Euclid witnesses and Power-Difference witnesses. In short, such witnesses \\(w\\in\\mathbb{Z}_N^*\\) allow to compute a proper factor of \\(N\\) via certain GCD expressions that require knowledge of \\(\\varphi(N)\\). The authors show that either there is such a witness up to a small bound \\(B\\), or certain primitive Dirichlet characters with large least character nonresidue exist. Subsequently, they establish the results stated in the abstract by exploiting already known bounds for least character nonresidues. Further refinements are achieved by assuming knowledge of the factorization of \\(\\varphi(N)\\). Finally, a hybrid approach using at most \\(\\log N\\) iterations of \\(\\varphi\\) is presented. As pointed out in the last section of the paper, some of the algorithms also work if only a multiple of \\(\\varphi(N)\\) is known.   In any case, the paper is an interesting contribution to this research area, and a valuable investigation of compositeness witnesses and the properties of hard numbers.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2023317$9C951255-EA55-402D-8472-ED545DBF6233","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f2946998a2c149ebedca1faa40aa5a7396a7e8e3","datavalue":{"value":{"entity-type":"item","numeric-id":2023316,"id":"Q2023316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2023317$A36487B9-1F9F-41A7-96C0-03780A7C72B0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"20afa916015e6219375b9937ece6e51d63990b6f","datavalue":{"value":"11Y05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2023317$5C8F7D38-B7B4-4F09-B4CC-3113FADCE19B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ecf21397fdcced4e2aeef35f7ab4217f79a7d6ec","datavalue":{"value":"11Y11","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2023317$FB05BC92-8976-4803-AEF5-36FC73F70238","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2023317$DA152787-85C5-428D-AE82-34EA67C95139","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5f9b48101e515c5287e3629a1b4bb750408e12b3","datavalue":{"value":"7342057","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2023317$F11C8E96-0FF7-4DA8-B89B-3131162AAB5B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f8628b2397710b2a25f56f0169ab55109851fba","datavalue":{"value":"large sieve","type":"string"},"datatype":"string"},"type":"statement","id":"Q2023317$ED617385-3A90-4E0A-AB8F-94CFCA4A24DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e2d67ecdb390a2c7f8029c2cea4bbf5d95555af6","datavalue":{"value":"factoring algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2023317$EC3261E7-F246-499B-B5F8-2444DBB5A4F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ddd8c734546af12d10a00953995bb7c46ed7978c","datavalue":{"value":"\\(Z_n^*\\)-generating sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q2023317$2A908110-9D71-4C16-9CCF-F97191F80D4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e2c46f52eb85d03165440a0e8a221152843a6d72","datavalue":{"value":"Dirichlet characters","type":"string"},"datatype":"string"},"type":"statement","id":"Q2023317$D6D55556-C2A6-4794-BA5A-F98D4E9377FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"817151c95b34daf6b44e8d72d36a83e6a09df489","datavalue":{"value":"smooth numbers","type":"string"},"datatype":"string"},"type":"statement","id":"Q2023317$375EAA35-5DAD-48AC-9DB7-1B9D87B68F08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34cc51cc702c9ffe71135a0854c51100bbffb25d","datavalue":{"value":"discrete logarithm problem for composite numbers","type":"string"},"datatype":"string"},"type":"statement","id":"Q2023317$BDBA4F02-D1C6-40A9-971D-A46CA8088AB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1744e1de6a219f0fd41dbb5363996dfeef58808f","datavalue":{"value":"primality testing","type":"string"},"datatype":"string"},"type":"statement","id":"Q2023317$4A79142B-74C1-4215-B32E-C5CB634B1587","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b326388fef7d1e658c90a7b7a36062ed00c4f6ba","datavalue":{"value":"Euler's totient function","type":"string"},"datatype":"string"},"type":"statement","id":"Q2023317$DB94564C-D781-4BEE-B8B1-948780CC0A62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d324115690d97a4f2702714fef4213f7d99fe719","datavalue":{"value":"RSA","type":"string"},"datatype":"string"},"type":"statement","id":"Q2023317$45F3DC4B-7061-4362-B400-7EC523A8827B","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":"Q2023317$3B330E03-A282-4ED8-959D-F237E7559367","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"58e8286a24807beadbbf6f84eb057d8f1d7a320e","datavalue":{"value":"https://doi.org/10.1515/jmc-2019-0023","type":"string"},"datatype":"url"},"type":"statement","id":"Q2023317$BC82BB35-AD70-41B7-892F-ABBBE2293B27","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9c3eb90ad34899aee85f00be895e47ac3938e207","datavalue":{"value":"W3080573067","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2023317$80BDF2AF-67A3-4322-9051-D09AF6942994","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc195a2addde90ed4009301c95e9141ac0061d2e","datavalue":{"value":{"entity-type":"item","numeric-id":4847943,"id":"Q4847943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2023317$0954F5DE-EE37-49C6-BEC9-EE55EB8CA324","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"654ef497bc56536d1acc44d89e9f6eaa5d631fe0","datavalue":{"value":{"entity-type":"item","numeric-id":2649761,"id":"Q2649761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2023317$5684CDBD-ACDE-4FBF-ADEE-CB9402B0694D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"921770db39ea626c2bc3c20886aa03631dfb47be","datavalue":{"value":{"entity-type":"item","numeric-id":3429795,"id":"Q3429795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2023317$1D1208E9-2C28-4153-A4DF-D76B1AB1D9FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d149eba9bb1ffda2574f762af329ecd09d87165","datavalue":{"value":{"entity-type":"item","numeric-id":5317673,"id":"Q5317673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2023317$3D026902-993D-42C6-9CDA-BDE77301878D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1dae642989c88a9599d3e96cd20db78715293189","datavalue":{"value":{"entity-type":"item","numeric-id":4606357,"id":"Q4606357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2023317$A2C9E280-526D-4921-B7C8-D0D4425D4DD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"13862168fb9af9e5175aea58ee5d963f2bd17d94","datavalue":{"value":{"entity-type":"item","numeric-id":1808862,"id":"Q1808862"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2023317$77EF3148-61BC-47DA-BCCA-74AD8D4486D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0da7b8f8e936ddf92daa1fdc6355191e26d6a604","datavalue":{"value":{"entity-type":"item","numeric-id":2785582,"id":"Q2785582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2023317$09895DBB-3CD4-4C6F-9F5F-E7885810CFC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60bae71ec6d3fd98884d465779379d0bdca17fab","datavalue":{"value":{"entity-type":"item","numeric-id":1112857,"id":"Q1112857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2023317$67E47948-4924-4D6A-B749-A07C3D5F04E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5a5889e90e815a8d25fa7c2beadeec29372b61f","datavalue":{"value":{"entity-type":"item","numeric-id":3602986,"id":"Q3602986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2023317$62D9C37F-5BD8-42DC-A568-D6D807C081EE","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":"Q2023317$166210B2-7EA6-4B0D-9A0C-D42814C71483","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65d0c410a37bcd5c702930fc77602b93b7508625","datavalue":{"value":{"entity-type":"item","numeric-id":445245,"id":"Q445245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2023317$502520AF-A89E-442B-87B2-F329411EF90E","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":"Q2023317$6DFB112C-D8B3-4CB6-A952-F406302B2690","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":"Q2023317$E6C38DA6-5C0E-4058-BE85-C97BDA5890AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7db89954414792366ef750af344e12bd9243cae2","datavalue":{"value":{"entity-type":"item","numeric-id":5500818,"id":"Q5500818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2023317$068063A7-F8FB-4B98-A41F-2000AFDD249F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af52e6d1470e66d58326faea5633d0adbca9adbe","datavalue":{"value":{"entity-type":"item","numeric-id":3584788,"id":"Q3584788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2023317$97311BBD-3016-4000-8B66-556E7D649CD3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0fb0494b4a99a462254e37bd3d61fe11877a6001","datavalue":{"value":"10.1515/JMC-2019-0023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2023317$E147E942-2567-4632-BEFB-358C966FDB4A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90f8bf0b226f6d0fd5854dab1e2e4b22accef4ad","datavalue":{"value":{"entity-type":"item","numeric-id":4606357,"id":"Q4606357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4df44ff1c989040bc984de792361cceabafbddec","datavalue":{"value":{"amount":"+0.85698401927948","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":"Q2023317$471E0758-2FD8-45AF-9943-513E5901328B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1c7bd6ca644a5f609423f4f011b6e4d57e2e27b","datavalue":{"value":{"entity-type":"item","numeric-id":1091136,"id":"Q1091136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e6f6f0f6ee4ccba8f207c0b05722a33500d725ed","datavalue":{"value":{"amount":"+0.7770046591758728","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":"Q2023317$A74739D4-98F0-435C-B0D5-C67D06B82D3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e23a05e210186820f8a2bca9ae87a419e4d808b","datavalue":{"value":{"entity-type":"item","numeric-id":4595597,"id":"Q4595597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d9f92fc5eba4887748b326ca731c6d2af4e6cac","datavalue":{"value":{"amount":"+0.773185133934021","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":"Q2023317$1B2D8FF0-FC6A-403E-8F12-84D25C5C333E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78cbfdaa6346d5624a9ece50663b3a2bfb572b1c","datavalue":{"value":{"entity-type":"item","numeric-id":4612569,"id":"Q4612569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc8078fe63c1afc616ebe3326650459b0a0a17e9","datavalue":{"value":{"amount":"+0.7705385684967041","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":"Q2023317$DCD4D022-15AF-413C-AC71-F3F2E0910634","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b86739a5b57e896d3e0961b2b7b434eb26fb99f","datavalue":{"value":{"entity-type":"item","numeric-id":3584788,"id":"Q3584788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"89f2c410d22c3eeceee48af4aac50c90a2e62909","datavalue":{"value":{"amount":"+0.7634528279304504","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":"Q2023317$2CF1A8A7-EF4A-4A6F-B902-E644DC6447A5","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2023317$21D28A2B-61D8-4992-8BEF-DCC8C481FCEE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Integer factoring and compositeness witnesses","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Integer_factoring_and_compositeness_witnesses"}}}}}