{"entities":{"Q809609":{"pageid":811457,"ns":120,"title":"Item:Q809609","lastrevid":64539117,"modified":"2026-04-11T20:34:02Z","type":"item","id":"Q809609","labels":{"en":{"language":"en","value":"A deterministic algorithm for modular knapsack problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4213454"}},"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":"Q809609$88E64AE6-295E-4DCA-B7B8-5F295A19D4C1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c35a03805671ccc3f84e8bf780b5a49c7187d42d","datavalue":{"value":{"text":"A deterministic algorithm for modular knapsack problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q809609$F2B8B8CC-1432-489D-A169-DF82E8AAC40D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b136cfebb750dee0f3790fa20a6f40698603e161","datavalue":{"value":"0733.68043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809609$3BF53FAF-B8FD-454C-8F70-9085FA14B2D6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"203f8cd0a5a2a3b39bd43b75783e0b8c31f5a05f","datavalue":{"value":"10.1016/0304-3975(91)90077-F","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809609$A4972C3B-6E12-468D-9B20-DA76FEB151E6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809609$3B174F01-74E8-440E-AAD1-2BC520BE2AD3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q809609$4957400B-541D-4B4A-A782-D961C08D753C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2e96956025df97d1833e3c346b0bb06b350e7477","datavalue":{"value":"The knapsack problem is quite a well known NP-complete problem, and as a such it is considered hard to solve in general. Fortunately its use as a basis of one of the first public key cryptosystems initiated a series of attempts to solve efficiently at least some of its subcases.    The article by A. Salomaa presents a deterministic algorithm to test whether a given knapsack vector is super-reachable, i.e. whether it may be calculated from a super-increasing vector by modular multiplication. In the positive case the algorithm produces such a super-increasing vector as well as a multiplier and a modulus. This is enough to efficiently calculate solution of the original knapsack problem.    The complexity of the algorithm depends on the growth of the entries of the original knapsack vector with respect to n, the dimension of the vector. If the entries of the knapsack vector are assumed to grow linearly in n, then the complexity of the algorithm is \\(0(n^ 3)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q809609$850E831B-8DD1-43C8-8A9C-5F1682FAD584","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809609$A95459DC-A348-4A56-9B1D-88B56E6AD47D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"817ee748606f03fadbe784c2dd4775be9e3b9bfe","datavalue":{"value":"4213454","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809609$F1722758-F468-4311-AC02-286B5FF71FFE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"adc70ad36cac8cb2c64857da848c519f36c64a5b","datavalue":{"value":"modular knapsack problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q809609$5E407232-7798-434C-B12A-6D70657BC3DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"172317ff0318c34249079325f55c546e5938ab9d","datavalue":{"value":"super-increasing vector","type":"string"},"datatype":"string"},"type":"statement","id":"Q809609$B37D1F57-D54D-47D1-968E-CE88999FD343","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"68cd74126590d1f1d3236e0fd93eec1c418d218f","datavalue":{"value":"knapsack vector","type":"string"},"datatype":"string"},"type":"statement","id":"Q809609$90332775-63FE-4D47-827B-D319B3AE5A9A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f58f3719f2f81c417cf620530e45b407dd1c4f1c","datavalue":{"value":{"entity-type":"item","numeric-id":235701,"id":"Q235701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809609$5BA8B2C6-0241-4C57-9C3F-48583D9DA1D1","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4418b7d4f2a0250db5c25bb23e561efd56a43eb7","datavalue":{"value":{"entity-type":"item","numeric-id":587571,"id":"Q587571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809609$F96D1BF1-6B70-468A-BED3-DC9E829EB10D","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":"Q809609$F47AF6D8-19AA-41C2-9CA7-F103DE5A4EC7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e59305d56c28d0f38a95a6ab2d34297a08dc4d9b","datavalue":{"value":{"entity-type":"item","numeric-id":5864294,"id":"Q5864294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809609$107BF7D8-99F1-4FF7-9CD2-B54249495D7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5457b0cb72c8b95f4127d6fa8247d739851c4b50","datavalue":{"value":{"entity-type":"item","numeric-id":3680279,"id":"Q3680279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809609$87F4277C-69CD-4281-9914-2ED518853CC7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9c9f20401f33ba0d594baccb0c243da13215ac42","datavalue":{"value":"https://doi.org/10.1016/0304-3975(91)90077-f","type":"string"},"datatype":"url"},"type":"statement","id":"Q809609$6F6CC046-AA12-4D46-A344-C520BACB4023","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"581772f363c1f3043eb18c9d2224c350b5cc5b42","datavalue":{"value":"W2087851677","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809609$7C08AECF-6FC4-4D99-A1D5-5C996F096604","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3fb5613f6c0c9b845e6525312b41df9d3196d82","datavalue":{"value":{"entity-type":"item","numeric-id":3348425,"id":"Q3348425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0897760964ced7a37239ca76b240b000836523ca","datavalue":{"value":{"amount":"+0.8922943472862244","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":"Q809609$A38C657A-153B-461A-95D8-D231EEDEFE96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8af181606a7d526b39029ad5af3ee6f38a2a9efe","datavalue":{"value":{"entity-type":"item","numeric-id":4739793,"id":"Q4739793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b87937a1466df0af54ab06407fec23effaee4c5c","datavalue":{"value":{"amount":"+0.8298260569572449","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":"Q809609$65D60765-BAF9-4382-9F89-8FD24DBB74E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"59b9324b3768f7b5368c704c55d1e76975ac0ed5","datavalue":{"value":{"entity-type":"item","numeric-id":5019315,"id":"Q5019315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71cf33dce2f44227de2182e93fe91bdc4f48c685","datavalue":{"value":{"amount":"+0.8224883675575256","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":"Q809609$ADD28B0F-18B3-4A4B-B065-8860F6EB8F09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07dabaf98f8dd5f469d61e7cb2b8691c22891121","datavalue":{"value":{"entity-type":"item","numeric-id":3345787,"id":"Q3345787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30a261ad8a6f2156b98fdf5b36d58f793db6963a","datavalue":{"value":{"amount":"+0.7973847985267639","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":"Q809609$5F29C334-A86B-4F2B-A2AA-067895AF81A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4282cc83764503d67aca032a677941a20dd4ec4a","datavalue":{"value":{"entity-type":"item","numeric-id":3771969,"id":"Q3771969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9910b970497cedb64c40063588c6831338875aae","datavalue":{"value":{"amount":"+0.79194575548172","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":"Q809609$29362FB9-EEB0-41C0-BE46-19DDAF468454","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A deterministic algorithm for modular knapsack problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_deterministic_algorithm_for_modular_knapsack_problems"}}}}}