{"entities":{"Q6606883":{"pageid":14218040,"ns":120,"title":"Item:Q6606883","lastrevid":55751443,"modified":"2026-02-17T22:09:24Z","type":"item","id":"Q6606883","labels":{"en":{"language":"en","value":"Bad witnesses for a composite number"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7914790"}},"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":"Q6606883$4B45B7FA-EA01-4DDC-858F-32168339FEFC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3aa45da0dd134bfaa6cd9243a45fab4d55eb19e2","datavalue":{"value":{"text":"Bad witnesses for a composite number","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6606883$43A81213-A5E5-44BE-A80A-D07E9FF259CB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0c2cd992525fce0b7603cf674270d2b02db49bd0","datavalue":{"value":{"entity-type":"item","numeric-id":6436447,"id":"Q6436447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6606883$11340C7D-0C44-4765-B35F-B49679F880DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1bf56c6705c563bc0befad499be51ca705684029","datavalue":{"value":{"entity-type":"item","numeric-id":1758642,"id":"Q1758642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6606883$A1C62ED5-B762-43BD-83EB-5B1EDB62DA5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e5a736319355d31e13239bc37a3f0fcf5a6f069f","datavalue":{"value":{"entity-type":"item","numeric-id":168881,"id":"Q168881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6606883$90AE46C3-1699-4804-AF41-D4E38513224C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"d7c377eb9eca9d4544de709b24b4ac445c513847","datavalue":{"value":{"entity-type":"item","numeric-id":2590509,"id":"Q2590509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6606883$463DFBC9-C72E-45BB-B88A-2EC9AA9A9BB6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"017399385e4d9ce7d03b1e5724928b0d308c6dc8","datavalue":{"value":{"time":"+2024-09-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6606883$8A5214F8-B445-4ADC-B212-0ED3D0C99E46","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6f8dbeecd85afd9c770c8f83fa0c0163eeaa93c1","datavalue":{"value":"This paper provides lower and upper bounds for the arithmetic and geometric means of the number of bad witnesses for an odd composite integer \\(n\\)\\, with regard to a particular pseudo (or probabilistic) primality test.\\N\\NLet us reminder that \\(x\\)\\, is a bad witnesses for a composite \\(n\\)\\, if the test declare that \\(n\\)\\, is prime. In this paper the pseudo-primality test is the product of a multiple rounds of the Miller-Rabin test by a Galois test (a pseudo-primality test based on a cyclic extension of \\(\\mathbb{Z}/n\\mathbb{Z}\\),\\, see [\\textit{J.-M. Couveignes} and \\textit{T. Ezome}, Rend. Circ. Mat. Palermo (2) 61, No. 2, 261--278 (2012; Zbl 1257.11106)]. As the authors point out the Miller-Rabin test is more efficient when \\(n\\)\\, has many prime divisors while the Galois test is more efficient when \\(n\\)\\, has few prime divisors.\\N\\NThe obtained results are synthesizes in Section 1, Theorem 1.1 (for the arithmetic mean) and Theorem 1.2 (for the geometric mean). These theorems are proven in the rest of the paper.\\N\\NSection 2 deals with the Galois test; 2.1 determines bounds for below and for above for the arithmetic mean of the number of bad witnesses of this test (Theorems 2.2 and 2.3) and subsection 2.3 studies the geometric mean (Theorem 2.4). \\N\\NFinally Section 3 proves the lower and upper bounds for the arithmetic and geometric mean in the case of the product test, see Theorem 3.1 and Theorem 3.2.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6606883$EC8847FD-BFC0-4F5D-AFE5-04465A1CB68B","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":"Q6606883$31E6F596-F009-428F-8677-5794DC5F40D1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ecf21397fdcced4e2aeef35f7ab4217f79a7d6ec","datavalue":{"value":"11Y11","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6606883$521DFBDB-0CF4-4C87-8DA8-D62BA94FB859","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f5492126398e1ddf0e8e00d7285568c890b3f47","datavalue":{"value":"11A51","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6606883$154A9F73-F95E-40FE-8F90-6751D344F576","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c10ae9dfb1c02e9f10ea2bc2d929b48890034aec","datavalue":{"value":"7914790","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6606883$7C963124-0D7F-4845-9D45-DC37DD93F176","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f47d98dc83a8955b217117b3cbc4b876305af0e","datavalue":{"value":"pseudoprime test","type":"string"},"datatype":"string"},"type":"statement","id":"Q6606883$D2D8B8B2-8A84-4F60-A4B8-AF1180ECA8F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8d57d3d197d0cf7dbd5d3cb7310de93cb105aa0f","datavalue":{"value":"bad witnesses","type":"string"},"datatype":"string"},"type":"statement","id":"Q6606883$09860733-95C3-41C6-97C9-CAF9CFB59DDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"64c94d49474b5b71528392ce3717916173122459","datavalue":{"value":"Miller-Rabin test","type":"string"},"datatype":"string"},"type":"statement","id":"Q6606883$E16C0F14-B6F4-41D1-B4C2-743F9F8FFB13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a3387c6088b7266bf6b17287d70b88c4450efabe","datavalue":{"value":"Galois test","type":"string"},"datatype":"string"},"type":"statement","id":"Q6606883$86DB6EFB-0766-4643-A73B-9468E63B64E0","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":"Q6606883$D86F3ED7-C69D-4867-8EB6-C8D2F340381C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"84233bbc6847c2e185b284cf773f2002c25b0098","datavalue":{"value":{"entity-type":"item","numeric-id":1334322,"id":"Q1334322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6606883$E48A7E0D-D3D6-4839-BC56-5465FAEC156D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"351abf980409feb018101933012c27db31a6c499","datavalue":{"value":{"entity-type":"item","numeric-id":4847906,"id":"Q4847906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6606883$0DEFE998-F1AD-45A9-B89D-C3288A9F5537","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"255a3cf09d95c2da8acd1302b795ab2bf99d2d3a","datavalue":{"value":{"entity-type":"item","numeric-id":5546875,"id":"Q5546875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6606883$32A4B0A0-3064-48F6-9EDB-3D36CB4A5247","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"572b63928c5da941916257b9a584fde7e94b7c24","datavalue":{"value":{"entity-type":"item","numeric-id":4992237,"id":"Q4992237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6606883$C054DE76-6AF9-4FAA-898D-F9720DE3BD8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40e06d5e16249040cb60e2ed1ea0c371fdd1dc6b","datavalue":{"value":{"entity-type":"item","numeric-id":3907627,"id":"Q3907627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6606883$7B453678-9CA2-4857-BFE0-D050972C7BF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7b90f5f555e7de90d0d9d965f4b8d4925ef144b","datavalue":{"value":{"entity-type":"item","numeric-id":4385595,"id":"Q4385595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6606883$68EB6DD8-0FD0-4CE9-BB0A-B6CF5F5433A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79261670d9bcbe0248b3e23f4bdf339e6e3c9ed3","datavalue":{"value":{"entity-type":"item","numeric-id":3715207,"id":"Q3715207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6606883$939701DA-3FFB-4DDA-A62C-B018AE1D0A98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b7d03acfe694d55b5bfb81a8721b654f11fafd6","datavalue":{"value":{"entity-type":"item","numeric-id":3139838,"id":"Q3139838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6606883$AFA30C6E-3760-4B0E-9F06-64E7272D9844","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1838cc3060d8754e2ea7edeffdca887e85927e2f","datavalue":{"value":{"entity-type":"item","numeric-id":1758643,"id":"Q1758643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6606883$5D6B7B36-8322-4F4B-8DC0-E001FD1ECB9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50f71bc7965f48b5bd343d2fb3b24afa0d5ecbe3","datavalue":{"value":{"entity-type":"item","numeric-id":3712368,"id":"Q3712368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6606883$D21326A4-B359-438B-B815-C60B49FA0E4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0394b7b1835b7cf201394c59795634086bf6a59","datavalue":{"value":{"entity-type":"item","numeric-id":2611585,"id":"Q2611585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6606883$F0202EE6-AE80-43CE-B6D0-C0B99912BD68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66cea8bc1318fab58af2934ed9c405114786b4fa","datavalue":{"value":{"entity-type":"item","numeric-id":4981596,"id":"Q4981596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6606883$A5AF8396-A1DC-4C61-993F-444CC4038859","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0d39c99d60bf368e2211383e8f67cbb18457d5f","datavalue":{"value":{"entity-type":"item","numeric-id":1762314,"id":"Q1762314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6606883$D0C64D60-FDA5-41E6-AC16-3417A90E4486","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2847756f3c49257b522462ad15287b283d00ab53","datavalue":{"value":{"entity-type":"item","numeric-id":5235112,"id":"Q5235112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6606883$06FF6BBC-99D1-4D95-A30B-13E4A694044C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"52ac54b726015b1585665123c1296c720dc366f4","datavalue":{"value":{"entity-type":"item","numeric-id":2701573,"id":"Q2701573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6606883$B1A3101C-8978-4F86-8670-3F9E19C76F0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1f6aa5a7dbb8eced91175201c5b61a84466f7ef","datavalue":{"value":{"entity-type":"item","numeric-id":3259107,"id":"Q3259107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6606883$14CA4934-F787-45D7-80E5-C14ACD5AA516","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":"Q6606883$195AB6A3-96A6-42E6-A354-D8EC684E21A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1da6a601185aa4d82a20c07d02fce511d4d8f3b4","datavalue":{"value":{"entity-type":"item","numeric-id":3877752,"id":"Q3877752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6606883$2365E76F-E1BA-438B-AA5A-34D4196F451C","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":"Q6606883$C016840D-ED49-4368-B599-5D8FE33CE6B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c88b7a6dda6487501610ffd3c8079e7ab5eb778b","datavalue":{"value":{"entity-type":"item","numeric-id":3615921,"id":"Q3615921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6606883$601005F1-7DE7-43C7-8817-C03D285A951D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5ee9e78607694ec1f2044700774a7e3412b5e1d7","datavalue":{"value":"10.4064/AA230512-17-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6606883$B0BAC145-A72C-4F75-A782-CCE6746A3572","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3786f9ffdf4950009c2fc7ebd4affbf2f1c2bba3","datavalue":{"value":{"entity-type":"item","numeric-id":1758643,"id":"Q1758643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15047e709aa6c7659ef408269a524f4647f578c2","datavalue":{"value":{"amount":"+0.7857687473297119","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":"Q6606883$86D25758-45A5-4A85-AB0F-35A6736C9949","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"74c0dc8accfcfcbffc43114b74bd115e6f852b07","datavalue":{"value":{"entity-type":"item","numeric-id":2066454,"id":"Q2066454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dccd25ef36eb488bf931b25b11cdbcd726c78493","datavalue":{"value":{"amount":"+0.7633641958236694","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":"Q6606883$DFCB93C4-DBF9-4E39-92F9-3C27F77E4331","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d586f07af7e2ad31d8ee5f9d753f0d59a1573ad5","datavalue":{"value":{"entity-type":"item","numeric-id":3712368,"id":"Q3712368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"959aefe6416f8b120e2bf56c098b731943712bf2","datavalue":{"value":{"amount":"+0.7416436076164246","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":"Q6606883$1D213057-11F6-44E0-A9B7-25258F215C75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c328f494e4ae1f1f23dd73d25217aded96644a8","datavalue":{"value":{"entity-type":"item","numeric-id":4322849,"id":"Q4322849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4b64e6f94d0080d07fad7d811a0ef887681898b","datavalue":{"value":{"amount":"+0.7278807759284973","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":"Q6606883$87DE807B-9215-4A27-A339-9CDF1C634842","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51cffd3ae11a4ce892e800d63f25725ec24112db","datavalue":{"value":{"entity-type":"item","numeric-id":3177720,"id":"Q3177720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b3bbd1d8f4fc0ed8dfc063707bdc7df45c151a43","datavalue":{"value":{"amount":"+0.725242018699646","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":"Q6606883$D40E49E5-1486-4D12-BE41-003A30FA37C5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6606883","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6606883"}}}}}