{"entities":{"Q654033":{"pageid":655882,"ns":120,"title":"Item:Q654033","lastrevid":63353946,"modified":"2026-04-11T12:18:23Z","type":"item","id":"Q654033","labels":{"en":{"language":"en","value":"The product replacement prospector."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5991114"}},"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":"Q654033$F9E8F91D-1203-4219-A0AB-1E1507E07EC7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6d56643b15579e61f526ad23005f5f5881d65124","datavalue":{"value":{"text":"The product replacement prospector.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q654033$6D48D853-D00D-4784-A96A-113FACFF7D0E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3891c6f63251e5ef6a7b8cf1d4a4ad69b6d8ec2d","datavalue":{"value":"1245.20001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q654033$824966AA-0B75-4F1B-B627-5A90A8A6C814","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"de5441966880934ab9b4127ad68efad726d93730","datavalue":{"value":{"entity-type":"item","numeric-id":404239,"id":"Q404239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654033$F8C3472F-84E8-4662-A618-13FFBED9D632","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"649cb128d59924c6cfcdb13e70b95523329c3106","datavalue":{"value":{"entity-type":"item","numeric-id":802742,"id":"Q802742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654033$DC657188-A3BC-41E9-BF52-AE1A58DD3FD5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ea72303f92787da89554ee5fa15621068821a762","datavalue":{"value":{"entity-type":"item","numeric-id":99061,"id":"Q99061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654033$16D2D83C-9382-4612-9F4D-C174970648DE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2d59771111bcb1a570f74a251a05a92b1b978b44","datavalue":{"value":{"time":"+2011-12-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q654033$97AE8BBD-A16B-45CF-99D7-AFBF50403049","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"84bea659762820cfe08958faa7b2a80ff8ced885","datavalue":{"value":"Many algorithms in computational group theory depend on being able to compute a list of independent random elements from a large group \\(G\\) where the group is defined by a small generating set and an appropriate group operation (technically, we are working with a black box group). The most popular program currently used to generate such elements is the product replacement algorithm (PRA) [\\textit{F. Celler, C. R. Leedham-Green, S. H. Murray, A. C. Niemeyer} and \\textit{E. A. O'Brien}, Commun. Algebra 23, No. 13, 4931-4948 (1995; Zbl 0836.20094)] which has the virtue of being quite fast. Although extensively studied, the theoretical basis for the PRA is still weak.   However, experimental evidence indicates that in practice the PRA produces roughly random elements which are not too dependent. (It has been shown that the mixing time for the PRA is bounded by a polynomial in \\(\\ln|G|\\) but in practice the algorithm is never run for sufficiently long to reach the bounds proved to ensure adequate mixing.) Fortunately in many applications we are only concerned to find an element from a subset \\(S\\subseteq G\\) where \\(|G|/|S|\\) is polynomial in \\(\\ln|G|\\) and in these cases the PRA seems to work well.   The present paper proposes a new heuristic to improve the PRA. It keeps a new temporary list (called the sampler) which is statistically tested from time to time to see whether recently generated elements appear random. If they are sufficiently random then the algorithm continues, but if they are not then the algorithm backtracks. All of the elements generated can be stored as short straight line programs. The new algorithm (called the product replacement prospector) has been implemented in the computer algebra system MAGMA and experimental evidence suggests that it is superior to the PRA.","type":"string"},"datatype":"string"},"type":"statement","id":"Q654033$772DFD74-BD2F-4377-9036-BA814A1C71E6","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"bac883d785667a63a92fc8927c00d4d1184f1321","datavalue":{"value":{"entity-type":"item","numeric-id":590084,"id":"Q590084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654033$501C2425-BE01-4542-B32E-B964AC0D78DC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f96720fe29e309c34c82deec20bd95823bb71652","datavalue":{"value":"20-04","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q654033$200CBB88-88A0-4C3D-89ED-4596A58AEA4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ef9852cdcd91e46926999d497f49e0eb30ab1aec","datavalue":{"value":"20P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q654033$0FDBB93F-84C1-43A0-9B32-C27A849F8449","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q654033$413D94DB-CEE7-43A9-BAF6-7E392E9CCB21","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"03a002031f9bd9a6fe932f6a9c27686c9e3c901f","datavalue":{"value":"5991114","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q654033$BC5A08DA-8EEB-4B82-9585-4E8D49BE815F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d63abd00ba97e023260564ab1e5de7e72c9aae49","datavalue":{"value":"computational group theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q654033$3AE45300-C769-435F-99BA-4F966DAB9528","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4c5efae6c6a6e0657ecd347fc69c73ec0f02267f","datavalue":{"value":"black-box groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q654033$39AC1F3C-08C5-4CFD-BA3F-FB7C52B245E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"939f00f5b9a9991d641e876c8115c77700366d63","datavalue":{"value":"product replacement algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q654033$8C3B2C74-5535-4839-A778-5661C3C5927D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6a84bf2d1dcde9be043284da3e16d175eebccbe2","datavalue":{"value":"random elements","type":"string"},"datatype":"string"},"type":"statement","id":"Q654033$7C0605BB-A8D5-4FF3-8ABF-1451D02AFFA6","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"dd7f0abef058f8eae97be2e317c30210cbb29e90","datavalue":{"value":{"entity-type":"item","numeric-id":13081,"id":"Q13081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654033$2908FBB3-C5BC-4CBB-A37D-B0B635F78F3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"7bd4369a99a9815f5bdd742b33b3bf73ce8bb9b1","datavalue":{"value":{"entity-type":"item","numeric-id":25498,"id":"Q25498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654033$14535F01-8326-4929-A8AA-4B3E4ED57AB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"4fe03e5b78d9974ebdfc0233dbd377f30d5d075f","datavalue":{"value":{"entity-type":"item","numeric-id":13295,"id":"Q13295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654033$F4D0886A-2B81-4B3C-800D-DEF61E14ABE5","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":"Q654033$6BBBBC63-4511-4DB1-AF15-A1DBA6E7037D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"43e5a1c21a367abee2b13d4f6c897278122d0bc2","datavalue":{"value":"https://doi.org/10.1016/j.jsc.2011.08.017","type":"string"},"datatype":"url"},"type":"statement","id":"Q654033$0156AB9E-7C5A-4C16-93B6-BF365EDEFD4B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4ee600ef50b8d44b64b687be6c2f31878f7599c2","datavalue":{"value":"W2081165772","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q654033$145B2D10-D22F-4DC7-BD8A-4A44E551779E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"05b1d6d459c53fb2aa6d7cc46e3e2d2e0ab86496","datavalue":{"value":{"entity-type":"item","numeric-id":4240509,"id":"Q4240509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654033$A076ACF2-B85C-43BF-990B-F71F57E500E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc30fb6d84af8349a5cd4d09d241caa7a9fec25a","datavalue":{"value":{"entity-type":"item","numeric-id":4820881,"id":"Q4820881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654033$24B7D341-82EE-4ED8-BC84-96B92EB65736","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd0d318899f6d495f4481731f0306e3c8c43504b","datavalue":{"value":{"entity-type":"item","numeric-id":1369784,"id":"Q1369784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654033$4AA84777-245E-45E3-A625-148B9D63612A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04d81a39e04f41a55d848b631b996676ebf9042c","datavalue":{"value":{"entity-type":"item","numeric-id":4857408,"id":"Q4857408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654033$0C21BF6A-880F-4148-B6BD-04273E6804E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94793d31e94f7dec6beaa1fc897151be1ae860d9","datavalue":{"value":{"entity-type":"item","numeric-id":3684278,"id":"Q3684278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654033$DB4A5A2C-A10F-49C4-BC41-E3F6325D3FC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28ef0ce502114c0ae62c542f8d4db09611381bec","datavalue":{"value":{"entity-type":"item","numeric-id":1326533,"id":"Q1326533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654033$6558C6D2-1A3D-4A2F-8E1B-D5FBEF0DCDCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff6312e92c29a7aae864a922178c5bbe3c2bb152","datavalue":{"value":{"entity-type":"item","numeric-id":1317235,"id":"Q1317235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654033$872676EF-ED28-41AC-A70F-7E03CAA04B5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"608b5dafa2db05cbb84ffde0336cb75e95a0908d","datavalue":{"value":{"entity-type":"item","numeric-id":1010821,"id":"Q1010821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654033$C85B4830-7347-41C7-B067-305EE529E7B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c3f28e1a16d7c97066b3338c07a139653ee0ea6","datavalue":{"value":{"entity-type":"item","numeric-id":4481935,"id":"Q4481935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654033$0D4C0FCE-797E-41CF-B063-BBCE705142E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8d247f49399cede46405e713e411fe2b8e215e0","datavalue":{"value":{"entity-type":"item","numeric-id":4781984,"id":"Q4781984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654033$194EB7B5-AFD4-4132-B77E-5B9A30E84169","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18f856c74e2332f21277ad1355cda3bf0900681f","datavalue":{"value":{"entity-type":"item","numeric-id":731248,"id":"Q731248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654033$23D83E81-5511-4E53-9AF2-41060F9DF0EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3313bc08d273235c44360297f29d369ce85755b","datavalue":{"value":{"entity-type":"item","numeric-id":2759632,"id":"Q2759632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654033$64DA70C0-FB4E-4773-9152-99B864591AEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9253a686b19b68b57a6d21b7458a0aa90a5036d9","datavalue":{"value":{"entity-type":"item","numeric-id":2759638,"id":"Q2759638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654033$D5BD028F-8B47-4D71-84E9-1F9D5BFD3D5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20a81c65ba947a04a03bfcfa9f7113b85c8d19f1","datavalue":{"value":{"entity-type":"item","numeric-id":3966901,"id":"Q3966901"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654033$59E9489D-471E-4CD4-AAF4-47693924B307","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1c62ada788f3ca01a4c6f8156af507942db5d91","datavalue":{"value":{"entity-type":"item","numeric-id":4787523,"id":"Q4787523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654033$D96DC920-DA17-4D44-AA1C-509DBA40C477","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e8145246ac47096cab0dcd6140e342d646159e5d","datavalue":{"value":"10.1016/J.JSC.2011.08.017","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q654033$5E320C0D-6764-4C5E-AC3A-ABB2489BAEF7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a8c4e07084ea5e834288c7dff40988a54eb954d","datavalue":{"value":{"entity-type":"item","numeric-id":2759638,"id":"Q2759638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3534f06463e4b39bb67112731adb295dbf6e7b8a","datavalue":{"value":{"amount":"+0.8060364127159119","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":"Q654033$11626427-D2F1-4F8E-96AB-619DDFF85636","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fdaa7fd0fe4c3804cd772f66952cc6cc8a45cf49","datavalue":{"value":{"entity-type":"item","numeric-id":4811498,"id":"Q4811498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d42e488ccbce8cc80a70860e4d68a5ceed10319","datavalue":{"value":{"amount":"+0.783326268196106","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":"Q654033$5080C269-7A26-46EB-BE1D-752E81876CD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d6f4c46bc8dd3ec11037af0c062ffd765629e4a4","datavalue":{"value":{"entity-type":"item","numeric-id":4952678,"id":"Q4952678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b5e2299bce620a78e28b56cad21984dfcefc3928","datavalue":{"value":{"amount":"+0.7540920376777649","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":"Q654033$87427CEA-3D56-4F1D-947E-C08F41F607E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f55c04153f82f3e95d0e19b1de11fcfa73dee9fa","datavalue":{"value":{"entity-type":"item","numeric-id":4857408,"id":"Q4857408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"806019af8031157dae4554254e1ff24fd8f9a4ea","datavalue":{"value":{"amount":"+0.7534745931625366","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":"Q654033$78C396B1-53F9-4187-BDDB-7ECC39BEA592","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49a018066929d5d5b2c72d3ec7b19e314a6590ec","datavalue":{"value":{"entity-type":"item","numeric-id":324208,"id":"Q324208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a99e712cd990e22c8e0a73fe4cfa339a974aa44b","datavalue":{"value":{"amount":"+0.7526267766952515","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":"Q654033$606C250F-683D-45DF-A48D-997ED24242BF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The product replacement prospector.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_product_replacement_prospector."}}}}}