{"entities":{"Q799477":{"pageid":801325,"ns":120,"title":"Item:Q799477","lastrevid":64463097,"modified":"2026-04-11T20:03:13Z","type":"item","id":"Q799477","labels":{"en":{"language":"en","value":"Integer programming and cryptography"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3874958"}},"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":"Q799477$32BF08A1-23DE-44EA-95B1-40B48719AA79","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"788640873af8d62bc4f85f2ea1df19d654602611","datavalue":{"value":{"text":"Integer programming and cryptography","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q799477$75D2F01C-1130-4CE8-AC83-1ED985C01750","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f2eaa82ba40b30a70d385ff8aa2aff74af6be9ec","datavalue":{"value":"0548.90050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799477$04D06895-0E32-48C6-8CBD-27753E51076F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9f244c93758217c23271375596726a57781849f1","datavalue":{"value":"10.1007/BF03024123","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799477$618ACADE-1474-495F-8887-D85954A29F52","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7fb1fb9e3613de38b550373bd0384fba28a5a775","datavalue":{"value":{"entity-type":"item","numeric-id":215534,"id":"Q215534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799477$26702802-A7BE-43F7-8053-B89EE34F571E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q799477$28DB2BED-0C53-4AE4-9D3F-E92E00B58031","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"248e84803b83772ed745d1c8e36d93850265c700","datavalue":{"value":"Several years ago it was shown that there exists a polynomial-time algorithm for the integer linear programming problem with a fixed number of variables [see the author, Math. Oper. Res. 8, 538-548 (1983; Zbl 0524.90067)]. The present paper explains the basic idea behind this algorithm by considering the problem how to decide whether a given triangle in the plane contains a point with integer coordinates. In addition, the paper describes how A. Shamir applied the integer programming algorithm in order to break the cryptographic system proposed by R. C. Merkle and M. E. Hellman [see \\textit{A. Shamir}, Proc. 23rd IEEE Symp. Found. Computer Sci., 145-152 (1982)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q799477$5DF65743-08F4-4D3C-964D-6F1D3284DCE6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799477$D00FFE7A-6E7E-4362-9834-30AF740F1C48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799477$3288A986-1C02-4982-8FF3-393D9429DC89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"58bd804a9b32ab16fea71636cf187b83a20de8f7","datavalue":{"value":"68P25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799477$F1E1D03A-EB62-4590-B9FD-8E7174887192","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"418d4d19aa7c87e33d52e580c9c108a1bc2de096","datavalue":{"value":"90C90","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799477$3A01D89A-6472-4122-A7DF-F4043EF2BF26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f4c7782f72175e3602c0085cb3bfabe8f23ebb24","datavalue":{"value":"94B99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799477$17F845C6-B8F0-4495-8E36-323917B913D3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b0f2e8b0d2fa2aa48130bccfb013ffe20e224993","datavalue":{"value":"3874958","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799477$6F7CA429-5166-4222-87E2-A36048026D98","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d54d97c9d74a7974164bd27bc3725f50a6bd71c8","datavalue":{"value":"cryptography","type":"string"},"datatype":"string"},"type":"statement","id":"Q799477$3479C3BC-4911-4A79-AD8F-93633D7B53A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2363d166b5b9fc791a0d6228cc5a474e45585fdd","datavalue":{"value":"polynomial-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q799477$D6A6B04A-8F26-4AB5-B7A1-30AA5A79050E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"faf217caaedd52eb71dcc9c0db47d47440a8fd56","datavalue":{"value":"integer linear programming problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q799477$F59EF3A0-E9B7-4B65-9CDE-2514E7D1BA9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"617c9fe9c0f16c139f26d08fc811f4834f993186","datavalue":{"value":"triangle in the plane","type":"string"},"datatype":"string"},"type":"statement","id":"Q799477$AAC5D822-3D32-4012-A914-5C7E83BEEC4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f34abac97ff38f8dd956a155c68168408375fee0","datavalue":{"value":"integer coordinates","type":"string"},"datatype":"string"},"type":"statement","id":"Q799477$9451BA6D-DC67-4110-8A9D-E44C249324E3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e59e3014c42347e04009f2d7e82f52c134765490","datavalue":{"value":{"entity-type":"item","numeric-id":165880,"id":"Q165880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799477$1E972C0A-8024-4C8F-B7A3-B3376391B40C","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":"Q799477$9A96E553-15CD-4EA5-A0D4-6908CD2C00EE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c1048fb3608a0cbc8e79944a470514716448194","datavalue":{"value":{"entity-type":"item","numeric-id":1259538,"id":"Q1259538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799477$032E860A-10FF-40BB-BD25-4259F109BC00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24a0a4a8909ae78f81d63b94195d86eb68d43477","datavalue":{"value":{"entity-type":"item","numeric-id":1153837,"id":"Q1153837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799477$5E6C2E2D-0709-46DE-AFA3-C383C202FD9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799477$40C7E4E5-BBCB-4843-B85B-7E263F493AA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7b369429581047e1dabd46e6eafe270ef5ac985","datavalue":{"value":{"entity-type":"item","numeric-id":3037135,"id":"Q3037135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799477$DBA77938-F2F2-4830-91D1-EF3C83C94981","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2496d76f7d7fec9d96f39f6e3a59ed93c78d8e95","datavalue":{"value":{"entity-type":"item","numeric-id":1165896,"id":"Q1165896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799477$2D7BC884-797E-4F7F-B0FC-EF118BE6C791","rank":"normal"},{"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":"Q799477$DA0C47B3-3469-4755-8EDA-601C31DBB2BD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d24e9aa1762af3f0163076bb84a2fc95a05d4b2","datavalue":{"value":{"entity-type":"item","numeric-id":3332923,"id":"Q3332923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"67c8321afa47276a29337ac6a0468848fc8472bf","datavalue":{"value":{"amount":"+0.8263905048370361","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":"Q799477$D5D929EA-E3BF-440A-9F6D-153681DFF551","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8eb91d9efa70da7caedea74c6afafffddf14a440","datavalue":{"value":{"entity-type":"item","numeric-id":3346214,"id":"Q3346214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d8fdd1dcfc5725f839ee10f30c3accd68598039a","datavalue":{"value":{"amount":"+0.7921725511550903","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":"Q799477$2100BE73-8807-47B1-AE80-0FA49FA70A5D","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":"6b8de406dadf49005e3e70133159c1fbf2d8f552","datavalue":{"value":{"amount":"+0.76417475938797","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":"Q799477$3FAB2CCD-B222-4101-BDA7-9B4B40466256","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a485ec23f8859262777f0fb029544a916c46235","datavalue":{"value":{"entity-type":"item","numeric-id":3342451,"id":"Q3342451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9dd9969e4cee06118edee17b94f8adcb40da198","datavalue":{"value":{"amount":"+0.7609760165214539","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":"Q799477$FE3F6A7A-7D3A-4C6C-95F4-95C66F33FF96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b7ef1fb9def3ecc5d7a62bdb18bf11c70b364f9f","datavalue":{"value":{"entity-type":"item","numeric-id":3770433,"id":"Q3770433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a710509af2e91969b9f79fce112fc4a623baf601","datavalue":{"value":{"amount":"+0.7609291076660156","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":"Q799477$E0297DEE-84E9-4F88-95A1-BC702FD6493E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Integer programming and cryptography","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Integer_programming_and_cryptography"}}}}}