{"entities":{"Q1894579":{"pageid":1905321,"ns":120,"title":"Item:Q1894579","lastrevid":69212499,"modified":"2026-04-13T05:31:08Z","type":"item","id":"Q1894579","labels":{"en":{"language":"en","value":"The Berlekamp-Massey algorithm and linear recurring sequences over a factorial domain"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 780891"}},"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":"Q1894579$3AE89AF1-1FF2-40C6-8EAD-C8565CBAD57E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4e94124bf5bba1b2ac8e7a86be5d370435962f69","datavalue":{"value":{"text":"The Berlekamp-Massey algorithm and linear recurring sequences over a factorial domain","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1894579$E839DBD5-DFE4-41B9-9E36-70ED69FE9BD2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9e5c0bb462c9392c7da50696ef6c0e3d757da6cd","datavalue":{"value":"0837.94025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894579$9F1888F6-A307-4843-9033-8B36B1E5D515","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3e67273537fe62c73dd938c79e722d013b3e078f","datavalue":{"value":"10.1007/BF01235722","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894579$57578A55-4436-47AC-AEF8-2FCF7912FE45","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"12cee7d4c2412f9c38d32f67771ae6b282995330","datavalue":{"value":{"entity-type":"item","numeric-id":191944,"id":"Q191944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894579$49ADB271-932F-4915-ABCA-48874160BC63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d177038a64580be1ec186c9396a9e9e01887ecb7","datavalue":{"value":{"entity-type":"item","numeric-id":231500,"id":"Q231500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894579$517E4B1E-9D91-46B9-9A02-1D735C3AB7C3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e71b1a810c94176f33b214acd409208085d409e4","datavalue":{"value":{"entity-type":"item","numeric-id":162945,"id":"Q162945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894579$5F390674-4431-47FA-BE26-7ADD47782F7E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b2e89868b1c268f0defa51f67a4a63561a369e84","datavalue":{"value":{"time":"+1995-08-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1894579$A479954A-695B-4916-91A2-2A67F0C3F608","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"69eea8414de87a22298d0ce4592954a1031157a6","datavalue":{"value":"The existence and effective computation of the minimal polynomial of a linear recurring sequence (lrs) with terms from a domain \\(r\\) is considered. Particular attention is given to the case when \\(R=U\\) is a factorial (unique factorization) domain. When \\(U=K\\), a field, the theory is well known and the Berlekamp-Massey (BM) algorithm computes the minimal polynomial. A more general approach is taken here to obtain information about lrs in domains such as \\(\\mathbb{Z}\\) and \\(K[X_1, X_2, \\ldots, X_n ]\\). The work is motivated by the desire to extend the theory of one variable codes and their decoding algorithms, such as BM and those based on the extended Euclidean algorithm (XE) to a multivariable theory. A generalization to XE and the polynomial remainder sequence (PRS) to \\(R[X]\\) is given. The extended algorithm (XRS) has certain invariance properties, similar to those of XE. XPRS is modified to an algorithm, BM/R, analogous to BM is given in section 3. Section 4 considers \\(\\text{lrs}(\\alpha)= \\alpha_0, \\alpha_1, \\ldots\\) where \\(\\alpha_i\\in U\\). It is shown that the ideal of the characteristic polynomial of \\((\\alpha)\\) is a principal ideal having a primitive polynomial generator. The factorial domains \\(U\\) for which the theory gives the strongest results are those for which \\(U[[X]]\\) are also factorial, called potential domains. This class includes all principal ideal domains and \\(K[X_1, \\ldots, X_n ]\\). The final section contains algorithms for computing the characteristic polynomials of lrs's.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894579$1D8AD8A0-1E35-4D5D-83E1-95805848D1B2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4430c94528f7856126af01b3ac6ccc7f8c77602b","datavalue":{"value":"94B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894579$8C054D1E-FD91-40AE-977F-B569A8DA44F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"dcefd1e200eae54420c5080733f6b5a349da9f6a","datavalue":{"value":"11T71","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894579$5D8E23C7-76EF-4BD0-9C28-99D135F5714B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894579$429B130B-9F66-4E4E-8BB7-FAB40900A85F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a20487430c81f65093c255b3f6124eff3bb99c7b","datavalue":{"value":"13F15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894579$B0C17698-C4CA-4E82-AC86-B0F15F8C9054","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"802fced9081cd42b708e2bb3399507e0865206d3","datavalue":{"value":"780891","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894579$2B94E305-E02E-474E-9F73-985C933E27C8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"99f8d0667a0f999ef322ccdbc5ff9aa849abb5c9","datavalue":{"value":"Berlekamp-Massey algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894579$E92F7E99-1CA8-4593-B5D1-6D8D4949F07C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5d2a69137098850450d1a17ddf83d6c1a1704d1f","datavalue":{"value":"existence","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894579$BE876DC8-C331-46F3-8B7C-EBBDBD069E8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"904b2e54b0e204f6a79c9cd0cbb4937fe26cb092","datavalue":{"value":"effective computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894579$38ACF524-29D6-460C-8C81-AAF7301D7640","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"13bf1e82a002ea4f43c2a812d12a7f554ea61034","datavalue":{"value":"minimal polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894579$9B32F50C-4197-4E0C-A07E-F4B7E6483FA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e0f7524d6f9df66c6aa4cf13e5bf12604b1c7d70","datavalue":{"value":"linear recurring sequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894579$66EE2DC3-B7B2-424B-82A3-E417806CECE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"75a23d2ed4404ff593b49f4496eca122c4a00541","datavalue":{"value":"one variable codes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894579$9D79B089-63BE-45E7-B3B5-14E6F126486B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fdd265674d6df629203f536a9a68808a13f0def8","datavalue":{"value":"decoding algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894579$E0EB5BCB-3634-4436-828C-8388B3B29BEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5232d4610820aa0dd012149b3e21ba651343c48e","datavalue":{"value":"extended Euclidean algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894579$E9A6BBD9-F0AC-4161-B980-B86438562F84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c2fc732426a296dc37cd34ccf846c35b9c912d7","datavalue":{"value":"polynomial remainder sequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894579$BDEDD808-9D55-446E-8D4A-100E2FBD917E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fe53b32d34b3c90c2cca54ca9113725a4b6fce50","datavalue":{"value":"factorial domains","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894579$DE761C53-EC90-4AD8-8A04-5EA2A83FC019","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d55353e7bc3d0614b86e9af78e82c119a2d0a9e0","datavalue":{"value":{"entity-type":"item","numeric-id":677137,"id":"Q677137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894579$E64EC952-EF7F-4B44-98BE-C51E50735E92","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":"Q1894579$BA55E95E-F837-46F5-A98F-5F4839D687D9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2ec93634d31be0907d2f3ca48e5fee2e3203bc6","datavalue":{"value":{"entity-type":"item","numeric-id":3968873,"id":"Q3968873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894579$C1575398-CF54-4B47-864F-2669E32CF27B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"47466ef3c36bcaa3b5c8456b06ecf3247c6d6210","datavalue":{"value":{"entity-type":"item","numeric-id":2762882,"id":"Q2762882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894579$35BAEE75-646A-4395-9523-05D86F0CF8CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8597ea8f033b7c7d8f4a033e73bb1a71b237a49c","datavalue":{"value":{"entity-type":"item","numeric-id":4405003,"id":"Q4405003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894579$E5B9F90C-1D2E-4416-A27C-DC7F5B12ACA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58ddf6c15587cc8d775178ac7830ee9b5995c206","datavalue":{"value":{"entity-type":"item","numeric-id":5532045,"id":"Q5532045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894579$CD10DC5C-6212-4E63-ACCF-AAA03FA977AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"acd40e69b1b46522d2a4b8cebd3bdd0cbcc8b190","datavalue":{"value":{"entity-type":"item","numeric-id":580398,"id":"Q580398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894579$1823FF30-73A1-446F-926B-28143385B8F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2b09403654bca6e72e9fe82ca407745705cb8b6","datavalue":{"value":{"entity-type":"item","numeric-id":3772131,"id":"Q3772131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894579$46F888DF-13B3-4A41-B62D-DE2450F52831","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf1897a37e1a0d285eb78a1068659c3ac1bcb62f","datavalue":{"value":{"entity-type":"item","numeric-id":4732508,"id":"Q4732508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894579$4E32FA12-586E-4745-A8A2-3542CA14E444","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ff4dca8a00d715cc946e2b7d67cc12d73527745","datavalue":{"value":{"entity-type":"item","numeric-id":3199325,"id":"Q3199325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894579$ED9FD57B-E73E-40FB-9BD3-0C253000818D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"795ae866466cf13fccd3b44351717f80450b1398","datavalue":{"value":{"entity-type":"item","numeric-id":5749240,"id":"Q5749240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894579$6B7F0FFD-544A-474F-8CCE-3B7B82250587","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"550370dcb301808eb58018473762b1b82f560b17","datavalue":{"value":{"entity-type":"item","numeric-id":3509721,"id":"Q3509721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894579$5C3E1469-2F38-4B4C-A1B5-398D8E1E2F47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"167aa8f433420724f1d28687996ae2418592e83b","datavalue":{"value":{"entity-type":"item","numeric-id":5554046,"id":"Q5554046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894579$B0236C0F-87F8-4446-ACC5-EF433AE3CFF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d0b2fce2b242cc432634970b75f6a32544e3aaa","datavalue":{"value":{"entity-type":"item","numeric-id":4156696,"id":"Q4156696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894579$37C86955-2CF2-4601-A510-C03B8A0DD44D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78ab30cdae1bc7800e14021ebd4dfd84f207b748","datavalue":{"value":{"entity-type":"item","numeric-id":4732508,"id":"Q4732508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ff731322c2652581711a0037ea0a2ce0586a18e","datavalue":{"value":{"amount":"+0.8837006092071533","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":"Q1894579$6FDD209D-D3EF-4856-BD38-32594E3BBE17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08f397f19e08f3d589f34b70dc7742e140073296","datavalue":{"value":{"entity-type":"item","numeric-id":4501006,"id":"Q4501006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84aecad0b1326975fa37a664f784475d153689ad","datavalue":{"value":{"amount":"+0.8247354626655579","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":"Q1894579$9BE88DE9-3571-46CC-B951-428C7CFF9F03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"346291e1f4f80a1781d30f439c0946ea2e48d382","datavalue":{"value":{"entity-type":"item","numeric-id":1286655,"id":"Q1286655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b4525071ffe4275f183ffa9853f6ab2ce9e76796","datavalue":{"value":{"amount":"+0.8229048848152161","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":"Q1894579$17D03E61-8830-46E7-9BFC-F1A42119DCF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"83f3a97347ed0da225e9518c3227d281fff4ca15","datavalue":{"value":{"entity-type":"item","numeric-id":1286694,"id":"Q1286694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b5600acd9c9c60c791eb140249eb42ed3cc2d6a1","datavalue":{"value":{"amount":"+0.8108730912208557","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":"Q1894579$89005CAF-8865-46A6-B3BA-CCA17B10266C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d5836d08f8e386dfaee977e6258bac0373bcd10","datavalue":{"value":{"entity-type":"item","numeric-id":4761725,"id":"Q4761725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d62ac91a5bd7867b0bd57c509243c1118946314","datavalue":{"value":{"amount":"+0.8090804219245911","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":"Q1894579$5224ECDB-86F2-4D9D-A53B-8DE48E18A162","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The Berlekamp-Massey algorithm and linear recurring sequences over a factorial domain","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_Berlekamp-Massey_algorithm_and_linear_recurring_sequences_over_a_factorial_domain"}}}}}