{"entities":{"Q1402367":{"pageid":1413107,"ns":120,"title":"Item:Q1402367","lastrevid":68845131,"modified":"2026-04-13T02:26:49Z","type":"item","id":"Q1402367","labels":{"en":{"language":"en","value":"A probable prime test with very high confidence for \\(n \\equiv 3\\mod4\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1971855"}},"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":"Q1402367$AFE63D64-9608-4DCB-9DEB-D1814393973E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"41cb61b50df7ee1b40f53ce96d34502f267fd6af","datavalue":{"value":{"text":"A probable prime test with very high confidence for \\(n \\equiv 3\\mod4\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1402367$8FA7BBE2-DD04-4FD3-9247-1E005E5D2CCD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"694ee7511b55ca9aa0fd2f054b7cd7d03a9052c5","datavalue":{"value":"1041.11083","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1402367$9D9FB312-B996-43DF-8357-E130EE2761C6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3e8ca735896d8fd1610d4d740dab3fd7cadda6d4","datavalue":{"value":{"entity-type":"item","numeric-id":1380459,"id":"Q1380459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1402367$12AF57CD-3A11-4093-A3EC-BDB65C15B4A4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"d5eab3bbb3b6673353b9ed770934b15d004ef795","datavalue":{"value":{"entity-type":"item","numeric-id":166358,"id":"Q166358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1402367$4D7A4C83-555F-4C65-974B-032FFDE4A630","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e470d6afc31ac12c7a48dd9fcc9ab0832c78550d","datavalue":{"value":{"time":"+2003-08-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1402367$794FA575-DD6B-4055-80EC-297FC57F4479","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d88cb76fd3bf094412bb31bc37f951b0a32259ff","datavalue":{"value":"The archetype of the probabilistic primality tests usually used in cryptography is the Miller-Rabin test. This test is extremely fast and guarantees the prime character of an odd number with such a small error probability as wanted.   It has the drawback however that a composite number can be accepted as prime by a quarter of all possible bases. It is also possible to construct composite numbers which pass the Miller-Rabin test for any given number of bases.   Other alternatives have been proposed in the literature to obtain more reliable prime tests, some of them due to the author of the present paper. In [Advances in Cryptology-Asiacrypt'01, Lect. Notes Comput. Sci. 2248, 87--106 (2001)] she analyzes the case of primes \\(n\\equiv 1 \\bmod 4\\).   In the present paper, following ideas of \\textit{C. Pomerance}, \\textit{J. Selfridge} and {S. S. Wagstaff jun.} [Math. Comput. 35, 1003--1026 (1980; Zbl 0444.10007)] and \\textit{R. Baillie} and \\textit{S. S. Wagstaff jun.} [Math. Comput. 35, 1391--1417 (1980; Zbl 0458.10003)], the author gives a new test such that a composite number \\(n\\equiv 3 \\bmod 4\\) will pass the test only with probability at most \\(1/331000\\), in the worst case. The drawback is a running time of about three times the running time of the Miller-Rabin test.   Instead of considering only the extraction of square roots of 1, as the authors mentioned before do, the paper proposes incorporating third and four root testing conditions. It combines properties relative to the residue classes of \\(n\\) modulo 3 and 8.   The \\` Combined Test' is stated in Section 2 of the paper. The following sections discuss details and some implementation issues of the proposed test.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1402367$3EDF0EA5-4988-4B4A-B8B6-B9D60700D448","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ecf21397fdcced4e2aeef35f7ab4217f79a7d6ec","datavalue":{"value":"11Y11","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1402367$5956F39F-6AF8-496E-8EBA-64A8C9803119","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f5492126398e1ddf0e8e00d7285568c890b3f47","datavalue":{"value":"11A51","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1402367$0B061098-ADAC-4777-A5C2-5F0D6699F3CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1402367$7D98866C-B95C-46A4-A226-B2EE18815DCA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ab1b96d3a7032eb7a926bfbad8b997e12aca6df2","datavalue":{"value":"1971855","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1402367$10195CF8-8C46-4696-9E91-E5B84AF21125","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e2fb18e12bca7c6e1001eb4ef46e9602fa306d1f","datavalue":{"value":"probabilistic primality tests","type":"string"},"datatype":"string"},"type":"statement","id":"Q1402367$BEDA2688-ED97-4C09-81A4-75FBFFE69D75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3c2d62af73b892ceb4d50ba4ac9427f20ae667ae","datavalue":{"value":"combined tests","type":"string"},"datatype":"string"},"type":"statement","id":"Q1402367$C3B473D6-ABCC-4FFA-8D0A-75085E17C3DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0c2ca009dee2ffc0bac9a2c51660d5898dbd9ebb","datavalue":{"value":"quadratic fields","type":"string"},"datatype":"string"},"type":"statement","id":"Q1402367$25439B30-3E52-459F-BC8B-5F5DE4892D04","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":"Q1402367$B222FCB8-2B26-4403-A925-1651B8FCE367","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":"Q1402367$41044EB9-08A2-4F7C-8D5F-1B991D0ACB9B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1e00488ad5e8cfdda9e8372416695eab9baa281a","datavalue":{"value":"https://doi.org/10.1007/s00145-002-0107-y","type":"string"},"datatype":"url"},"type":"statement","id":"Q1402367$E08F7F26-CC39-49FA-822F-EBFF7A01D7C0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"71868713b9872c15dd83853130da838c39f24aad","datavalue":{"value":"W162865231","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1402367$9DA60BC0-740A-4ED0-8076-3D336ACB44F3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a3c90caaf8f51f021a04942dd8564736440b04d7","datavalue":{"value":"10.1007/S00145-002-0107-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1402367$27CA5F8F-E23D-4B09-9E57-82C9005E3DB3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"719d9b884498caa8bddf4b7d6f6410b28364de07","datavalue":{"value":{"entity-type":"item","numeric-id":4474167,"id":"Q4474167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a5074b84faaf9c6d9130b96aabfc0fb107db47b","datavalue":{"value":{"amount":"+0.85413384","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":"Q1402367$0E84ADB6-7CCC-4301-8286-07A8DF455DAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d79c5041280a8a50326ec3c849dadac705fe1fef","datavalue":{"value":{"entity-type":"item","numeric-id":1582299,"id":"Q1582299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f325948ca4896b652c3c9473d1eefc473230abb","datavalue":{"value":{"amount":"+0.8111681","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":"Q1402367$1FC598D6-9605-4ED1-AEF6-7FE994D4D336","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"854736479c153f7234f09b4645301cd82fc8e0c4","datavalue":{"value":{"entity-type":"item","numeric-id":3786518,"id":"Q3786518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"52d322d0fea9990392002eea4502d55915c2de9b","datavalue":{"value":{"amount":"+0.7997602","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":"Q1402367$36DF07C9-F75F-44BD-8FDE-4ABE6345905A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e108ce899933160edcb7f043d4f5f70a958088e","datavalue":{"value":{"entity-type":"item","numeric-id":2708615,"id":"Q2708615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5c78e145a6da2a22b9e90ef114890b5d0187e57","datavalue":{"value":{"amount":"+0.79579246","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":"Q1402367$EDBAE7E8-368F-4B75-ADBE-EB7F5AF60E8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e58d21da3fe127f19070a62650bf663d418e236a","datavalue":{"value":{"entity-type":"item","numeric-id":1118632,"id":"Q1118632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"67d9c087818b0a70901837a835cb55476cecff07","datavalue":{"value":{"amount":"+0.7914337","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":"Q1402367$6ADB6C27-7671-443C-A3DE-8A20EA44C2D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3839848c6833d3918bb45ca6a88167e8f5080a8d","datavalue":{"value":{"entity-type":"item","numeric-id":3828064,"id":"Q3828064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21628254c93526766822b27151834e2f09645cd8","datavalue":{"value":{"amount":"+0.7885687","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":"Q1402367$D3BBA049-AE22-4204-B3E6-44669D752211","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"174dfc7918add842bca6060d03a8072da1dcf91d","datavalue":{"value":{"entity-type":"item","numeric-id":1992114,"id":"Q1992114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e3168f51330ba9ac58a237f4291f00fc888d88fc","datavalue":{"value":{"amount":"+0.78623694","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":"Q1402367$6C4EE8B3-6978-4201-853A-595A8E474A60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ebb3218cae373c063682831be60b95bf24e16378","datavalue":{"value":{"entity-type":"item","numeric-id":2442488,"id":"Q2442488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1bbf19bc9cca808b47fb6d8fa1acdf6dba0b19d0","datavalue":{"value":{"amount":"+0.7860731","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":"Q1402367$E2A0CAA4-A451-4C18-AF62-8DE36D6E1775","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2450606438b3020397305c1229cf0b480fe677b4","datavalue":{"value":{"entity-type":"item","numeric-id":3615921,"id":"Q3615921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2a023858144222cbbf8317b516d1c283ce62fd7","datavalue":{"value":{"amount":"+0.7855401","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":"Q1402367$D4D54302-DE10-4280-80FE-99841F7C39F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7694285146285b816b0edb152627d432591f19c9","datavalue":{"value":{"entity-type":"item","numeric-id":1273196,"id":"Q1273196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c8b5334e5d9544059cd40095a96ff844fe495e0","datavalue":{"value":{"amount":"+0.7844644","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":"Q1402367$186E4CB5-D183-4670-9335-B0F01DC4F5BA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A probable prime test with very high confidence for \\(n \\equiv 3\\mod4\\)","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_probable_prime_test_with_very_high_confidence_for_%5C(n_%5Cequiv_3%5Cmod4%5C)"}}}}}