{"entities":{"Q1123581":{"pageid":1134330,"ns":120,"title":"Item:Q1123581","lastrevid":67050972,"modified":"2026-04-12T14:36:20Z","type":"item","id":"Q1123581","labels":{"en":{"language":"en","value":"Exact deconvolution using number-theoretic transforms"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4110060"}},"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":"Q1123581$0B4DE510-3228-4DE7-A562-93161217B19E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cd991363f0d32a8257b5ae9e12d6ec0237759322","datavalue":{"value":{"text":"Exact deconvolution using number-theoretic transforms","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1123581$92784B9F-95AF-47D1-9D2A-B424358D382F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6f4b11df984ff571530f31b2b5edd8520fbbc590","datavalue":{"value":"0677.65145","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123581$168F3CB6-E376-495D-B936-CABF2DCD74EC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2997f087864a70e55902847d28987d6d8deb0604","datavalue":{"value":"10.1016/0898-1221(88)90128-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123581$668331EF-F713-4DA6-8D45-16E609A6BCCC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1123581$D6DFE275-0E71-438E-8B9F-28C9518BB73A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"05cdc86aee9763fc7228e3c704b7a14f50d35496","datavalue":{"value":"Let us consider a one- (or two-) dimensional deconvolution problem \\(a*x=b\\) where * stands for cyclic convolution, a and b are known integer vectors (or matrices) and x is a vector (matrix) of the formal solution in the field of rational numbers \\({\\mathbb{Q}}\\). This solution exists and is unique if and only if the circulant (block) matrix A associated with a is invertible over \\({\\mathbb{Q}}\\), i.e. the determinant \\(d=\\det A\\neq 0\\). Using symmetric residue arithmetic modulo an odd integer \\(m>1\\) and number theoretic transforms (NTTs) the authors present two algorithms which yield the exact solution x without round-off errors.    The first algorithm assumes \\(m=m_ 1m_ 2...m_ s\\) where \\(m_ i\\), \\(i=1,2,...,s\\) are relatively prime. Applying the Chinese remainder theorem (CRT) the original problem is converted to s deconvolution problems over residue rings modulo \\(m_ i\\), \\(i=1,...,s\\), which are solved in parallel by means of a set of s NTTs. Within this algorithm a new computational scheme is introduced for the CRT reconstruction of the symmetric residue modulo m from the symmetric residues modulo \\(m_ i\\), \\(i=1,...,s\\). This scheme resembles a modular analogue of the recursive computation of divided differences. The value of d is obtained as an intermediate result, allowing thus the regularity check \\(d\\neq 0\\) as well.    An example of a \\(3\\times 3\\) deconvolution illustrates the above method. The second algorithm is a generalization of the recent result of \\textit{M. Morh\u00e1\u010d} [Comput. Math. Appl. Part A 12, 319-329 (1986; Zbl 0609.65030)] to arbitrary length (not necessarily the 2-radix one), using one NTT modulo m (not necessarily the Fermat number transform) several times. This algorithm assumes the a priori knowledge of \\(d\\neq 0\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123581$62317B3F-82B2-4094-AAC0-A43E6AECE05D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"588be99e69a86bc02ca9cc8ddd46725bc447e370","datavalue":{"value":"65T40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123581$FC6D0427-242B-4261-976D-8E612F6D7723","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"72309745094959b676ca20810c7af21a33fe24b5","datavalue":{"value":"65F30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123581$DA84204B-AE91-4642-99EF-56E191A3424A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"843de71235f44a800ae389e1734df6bb7650efec","datavalue":{"value":"65K10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123581$1DB9C219-25EC-492E-B859-549424D7B4C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8f1fdbd37ea55781316a099df1ac6c996bd515a2","datavalue":{"value":"93B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123581$35B0A723-7A8B-4E55-935E-065767143EFD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"360e2333da0fb6800161468bb92f8cb337bee2e2","datavalue":{"value":"4110060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123581$0E9C3F61-0621-4CF5-A74E-F1663EE4927C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a9446bc6b5ec3b6f4efa59435bb7973cbd9adef","datavalue":{"value":"deconvolution","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123581$CD26A7B9-FAA8-492F-9348-1ACE77170F40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d7e13171f0e301f9a7c03d8101ccbe541e557886","datavalue":{"value":"cyclic convolution","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123581$4A867D20-BF72-4673-9504-A75C7594D949","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d568570bfed50b56c7381bc353464f373a596868","datavalue":{"value":"residue arithmetic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123581$834D954F-BCE4-4A23-BC79-31611CAEA649","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fa5f3d9dc6abe78597bcf8bbd1a1d520a71f4768","datavalue":{"value":"number theoretic transforms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123581$9A9E6268-1CDE-400D-9C3F-6E61BC8F6079","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2bf2159b83c1cb1978a8a55c136391b653478ee6","datavalue":{"value":"Chinese remainder theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123581$5D137DC7-77D9-4550-A35B-0D3D4080B651","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"20cb5f900346d6218be2e7d1c87b3ca77a3b494d","datavalue":{"value":"reconstruction","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123581$657EE449-14D3-43F0-8FAF-28FB00F376BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5ec4be342daf2578298a23ddadf8deb2e8156b97","datavalue":{"value":"recursive computation of divided differences","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123581$A08E0B52-5483-4FC6-A88D-A278CE8F07B6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"37b2a87e2e5c6e6387abb1976539b24d6978d6fd","datavalue":{"value":{"entity-type":"item","numeric-id":1087579,"id":"Q1087579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123581$33002B62-D078-45B2-A956-B6ACBFDE1B44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9e7db92679b9f3756f1d1954bd5f57a163a637e7","datavalue":{"value":{"entity-type":"item","numeric-id":222546,"id":"Q222546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123581$0FFBE040-FA25-41F6-9C8B-150F32BAB205","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ce5f65bda9473525ae76f6fddca6447d9c01ba3f","datavalue":{"value":{"entity-type":"item","numeric-id":1793929,"id":"Q1793929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123581$32B32F3A-4A32-4E87-A951-D334B3E1875F","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":"Q1123581$0D5C6EB4-2D0C-47F4-928F-32D1428D1A0E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fa7cef9e53b9475a6cdd26e53af7117eb45cf04b","datavalue":{"value":"https://doi.org/10.1016/0898-1221(88)90128-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1123581$B5C78460-B76B-43B7-BEA8-0D211F8F499A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1554c8617ed7436941baeef7883e750a4c093068","datavalue":{"value":"W2085169188","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123581$648D6DF2-76AB-497A-ABEA-6E72890E76FE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f959aeb707b85853c9e70d5adcb8bc9e95b1b575","datavalue":{"value":{"entity-type":"item","numeric-id":4151724,"id":"Q4151724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123581$02E0636A-FCD0-40A7-8FF2-EB8290834D31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a1a6a287d9243437b8a676a895453e0737ae618","datavalue":{"value":{"entity-type":"item","numeric-id":5553682,"id":"Q5553682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123581$1834966F-148A-46BE-AEFE-1064E3DC2723","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"618f44db6bfd93e13234bfb2f360e35fdf448776","datavalue":{"value":{"entity-type":"item","numeric-id":5589677,"id":"Q5589677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123581$2DC0FF1D-C7F3-4B96-A45E-230CE872963E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d581c1d6ca22d83eebd16b00ba3a57e08a130dd","datavalue":{"value":{"entity-type":"item","numeric-id":3752449,"id":"Q3752449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123581$1B70A550-9F83-4C32-ABAA-DF3ECAC13ECF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5864ff407691828143db89ed04abca180a61361","datavalue":{"value":{"entity-type":"item","numeric-id":2547695,"id":"Q2547695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123581$B919FAA6-C202-4FA1-963D-155E76508909","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d9f4b230a2d1c214182b291d964a3270a9cd482","datavalue":{"value":{"entity-type":"item","numeric-id":5625308,"id":"Q5625308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123581$626FEB32-7837-4A60-B3DA-0CA087845D39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"507334689f347ba0c77cd4f96c1ae97d2e084806","datavalue":{"value":{"entity-type":"item","numeric-id":3735040,"id":"Q3735040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123581$1FB04959-2D96-4453-8417-733408C551AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74725b141ba328ca8786298a890b280a7241e560","datavalue":{"value":{"entity-type":"item","numeric-id":3750038,"id":"Q3750038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123581$2616776D-4231-4508-AF05-90EF30C24D27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"701179a4cb6778efdf79b6951df4a172985b04f5","datavalue":{"value":{"entity-type":"item","numeric-id":3208805,"id":"Q3208805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123581$3FDE24C3-A0D2-4BE8-BA18-EBD4FBA115FD","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"293935db3834ff8b5d542ae1771b7c6cb66baa38","datavalue":{"value":{"entity-type":"item","numeric-id":85551,"id":"Q85551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123581$040A8339-7153-498F-9DE5-C6701FDD01F4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f0d26800e48724cd3502e96947144a63345754a","datavalue":{"value":{"entity-type":"item","numeric-id":3750038,"id":"Q3750038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"248c2b00d8f37609f2009b44ef8b97f899f8417b","datavalue":{"value":{"amount":"+0.8194793462753296","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":"Q1123581$F09DDE20-5A96-4695-A049-0A30B38A3BB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d89df451c6b80e649012391d2fa2f62a405ef6d","datavalue":{"value":{"entity-type":"item","numeric-id":1774849,"id":"Q1774849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"246390686bf4e4241f30f0d774c0dc7671f048e7","datavalue":{"value":{"amount":"+0.7808133959770203","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":"Q1123581$650A60D5-007C-4988-A276-BFDBA7307F11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f7ffd69e2fccfab99367209012a44cff6303df5e","datavalue":{"value":{"entity-type":"item","numeric-id":4291045,"id":"Q4291045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b595d5f51eebe033a6b50c5652e355f78ad75de","datavalue":{"value":{"amount":"+0.7780299782752991","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":"Q1123581$38C6459D-7688-46C9-A608-323470DD354A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fabf605dd31ea17d84ab2e087be96cbbd73f00d","datavalue":{"value":{"entity-type":"item","numeric-id":3698249,"id":"Q3698249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b595d5f51eebe033a6b50c5652e355f78ad75de","datavalue":{"value":{"amount":"+0.7780299782752991","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":"Q1123581$CA216741-2469-492C-B32B-E083720C0BC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca232b2f0f4ff7b452ab5e8280a712a723c5d93d","datavalue":{"value":{"entity-type":"item","numeric-id":1825622,"id":"Q1825622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28a4be571b3e21738355a971a5ec5447db1c3643","datavalue":{"value":{"amount":"+0.7762935161590576","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":"Q1123581$7AAB22B2-AB53-4711-A079-AC9283D373E0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Exact deconvolution using number-theoretic transforms","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Exact_deconvolution_using_number-theoretic_transforms"}}}}}