{"entities":{"Q1190750":{"pageid":1201499,"ns":120,"title":"Item:Q1190750","lastrevid":47072545,"modified":"2025-12-31T14:13:59Z","type":"item","id":"Q1190750","labels":{"en":{"language":"en","value":"The inverse of an automorphism in polynomial time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 56194"}},"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":"Q1190750$955DD85E-69CF-4467-9A48-D16E0322FAEE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3a2c521829c90c56aa21673433b01dbef68eda6e","datavalue":{"value":{"text":"The inverse of an automorphism in polynomial time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1190750$E4B853A6-8F87-4EF3-B00F-27F2D66D0CA4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2ab93b7dd97661435149343fae4706cd14464748","datavalue":{"value":"0805.13006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190750$404F7149-9036-421F-BB7D-3D1EBD0C35BA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5439c9cc2acb4150d6fbc0815fba389fac4edb79","datavalue":{"value":"10.1016/S0747-7171(08)80090-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190750$730E75A0-C69E-49EF-8CA7-F93599AC3FCC","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":"Q1190750$00068901-4A78-4B38-BCD7-DFB2C54EB70B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d9b40ce89936be2de8343a01d1ced7ff59f76b3e","datavalue":{"value":{"time":"+1992-09-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1190750$FA7EE727-23CE-4611-A39F-8AD87C1589C6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"130687ea17bc55eb68c1f0362fb0ddf7f37edeb5","datavalue":{"value":"A \\(K\\)-endomorphism of a polynomial ring \\(K[\\vec x]\\) is a mapping of the polynomial ring to itself which preserves addition and multiplication and which fixes every element \\(k\\) of \\(K\\).   Problem 1 (Endomorphism invertibility) Let \\(\\sigma : x_ i \\mapsto h_ i (\\vec x)\\) for \\(1 \\leq i \\leq d\\) be an endomorphism over a polynomial ring \\(K [\\vec x]\\) given by the coefficients of the polynomials \\(h_ i \\in K [\\vec x]\\). Determine if \\(\\sigma\\) is invertible, and if it is compute its inverse.   A subproblem of problem 1 is the following:   Problem 2 (Inverse of an automorphism) Let \\(\\sigma : x_ i \\mapsto h_ i (\\vec x)\\) for \\(1 \\leq i \\leq d\\) be an automorphism over a polynomial ring \\(K[\\vec x]\\) given by the coefficients of the polynomials \\(h_ i \\in K [\\vec x]\\). Compute the inverse of \\(\\sigma\\).   In this paper we give a new solution to problem 2 which works over any commutative ring \\(K\\) and requires a number of arithmetic operations which is polynomial in the dense representation of the input and output polynomials. Our algorithm for problem 2 also leads to a new, exponential time solution to problem 1 in the case where \\(K\\) is a field.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190750$382A8A00-A707-44AB-A0DB-88D3531E342B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"134db59e1dd21b74810139030592980e5f363e0f","datavalue":{"value":"13P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190750$87C65A35-FDA9-4BFF-9C46-616ED615A33E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190750$204A81E2-955B-4606-BF59-D5DE16C0495C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"391950414a099d56bc54d4355f229d909cdcb643","datavalue":{"value":"13F20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190750$3BEE05C9-5EF5-4998-B4B5-DACF5A7287B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de3565cfd3393000dd87ca545f95ff84d4c1446","datavalue":{"value":"68W10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190750$59D5490D-611C-43DD-A127-A51C0A7D3619","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"872dcc0d5ccf3f3c98c0c57cbdcc02d8d45a1fc6","datavalue":{"value":"56194","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190750$F0D7289A-CA16-4594-9BC5-E7BB4D5D6CC4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3720fbda496208e49edfcca51cc3a8b89f78778b","datavalue":{"value":"endomorphism of a polynomial ring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190750$C177322A-764F-432D-AFCF-8C31A5BDF50F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5d0df757f180618b6834b6077fad53a5f751aff7","datavalue":{"value":"endomorphism invertibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190750$FDDB2585-A0E3-4BF4-89BF-8FC03719E5ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"172e750250fd1292eb6709084b2dc7062ccfeebe","datavalue":{"value":"inverse of an automorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190750$E3867B22-15A1-49E6-B065-D22087C16D7E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b595d27cd8e3056d0ee898b7ed77a1b4d9172d2b","datavalue":{"value":{"entity-type":"item","numeric-id":916421,"id":"Q916421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190750$8F11B73E-BB52-4725-86D3-E434531409D6","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":"Q1190750$0F438A2B-56F6-493E-987F-B373A155AF44","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"414269a822edd88e6ee70c177020ee8b41af7c5a","datavalue":{"value":{"entity-type":"item","numeric-id":3678628,"id":"Q3678628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190750$2BD467E3-304A-4CC0-9F13-794CD538DFCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2ff57ef70bd9e86c9b7017e46b8cd84cb7965f4","datavalue":{"value":{"entity-type":"item","numeric-id":3714165,"id":"Q3714165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190750$5DDA307E-14F4-4276-85B2-41F13C08FD6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7590acfb35c9f5198acd245aa781f128ad19997","datavalue":{"value":{"entity-type":"item","numeric-id":3325839,"id":"Q3325839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190750$8C6B4752-2C3E-4BE2-B8BE-759B872C3C3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bafb7194e44cfc712bfc44cb5c7951031751daa7","datavalue":{"value":{"entity-type":"item","numeric-id":5903274,"id":"Q5903274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190750$6ED4B09F-FB22-46B0-B9EF-3B17D1DC9F78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c881199b9040cb6f49a9750d7a613b6e7f8e1f7","datavalue":{"value":{"entity-type":"item","numeric-id":1080656,"id":"Q1080656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190750$5F259BA1-A514-4622-A29A-AD9A0A65C216","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa9d74fed92074cc90157e94abdbe5dcf3b20977","datavalue":{"value":{"entity-type":"item","numeric-id":753496,"id":"Q753496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190750$3F6439DD-695D-42B8-B191-8296858A5DD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2f7a81f7b25675b22b5e68e225f38ca7adbe782","datavalue":{"value":{"entity-type":"item","numeric-id":755793,"id":"Q755793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190750$6CDB0436-805E-4BA8-BF7B-F5B8076E2181","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27d7e3ea5e32569f562d397c63044c70766a5448","datavalue":{"value":{"entity-type":"item","numeric-id":5185900,"id":"Q5185900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190750$EEBD69BA-CFC4-4028-8550-DC9CB17D4D88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55671e87319c03a503219a2b4948488361c95655","datavalue":{"value":{"entity-type":"item","numeric-id":5893804,"id":"Q5893804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190750$013AA437-61B4-42F9-8733-94535B5BF9C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05426ecc83d2d488ec81f6073b448c60e4e103c8","datavalue":{"value":{"entity-type":"item","numeric-id":3698903,"id":"Q3698903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190750$466BFF03-9433-4BF4-A3FD-1544B090CB38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7db347c000b2454add83720eee2bfeb503fee96d","datavalue":{"value":{"entity-type":"item","numeric-id":1090716,"id":"Q1090716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190750$9BA5A23A-D253-4C7E-98E3-AA4B013421A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34e07bbfbd474415c68245b81b457e1fed4d156b","datavalue":{"value":{"entity-type":"item","numeric-id":1115485,"id":"Q1115485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190750$557209FA-84A9-4BE8-B2E7-3AA83A07755B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af34082069d70b5a60167da7dbb034dd0869653b","datavalue":{"value":{"entity-type":"item","numeric-id":3886825,"id":"Q3886825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190750$26C61BA9-3569-4B8C-AA49-AE90206BB948","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d9addab61bb73777221af90496950694624bcf1","datavalue":{"value":{"entity-type":"item","numeric-id":797636,"id":"Q797636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190750$3E190D40-7ABB-4C24-96F7-95CEF3708735","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0322103f340ea88011bd3d9c87bf5c7ccfa41d14","datavalue":{"value":{"entity-type":"item","numeric-id":1823681,"id":"Q1823681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190750$02784B28-D096-4FCD-ABF9-AB73FC0D6C85","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e555583a8f112fa3e564109af56627dd7d7c9e80","datavalue":{"value":"https://doi.org/10.1016/s0747-7171(08)80090-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1190750$2BE255DF-FAB2-445A-A075-08532960421B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fb4c26b8044e9333cce07a332783d86512d3a208","datavalue":{"value":"W2017876328","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190750$FBF5439A-E0FD-4B1A-A1F3-12E2E8CBF7CC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35f6e8c777b06bebe40237e94c6c1165c13862c3","datavalue":{"value":{"entity-type":"item","numeric-id":4909069,"id":"Q4909069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4898f6b18503b372a22c27ec7ddd2eac488e5db","datavalue":{"value":{"amount":"+0.8313484191894531","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":"Q1190750$D84B732F-7A5F-4926-ABEB-5E175AA5DAC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd4829c760d0ea3a934f15fdd357323072618cdf","datavalue":{"value":{"entity-type":"item","numeric-id":5383820,"id":"Q5383820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f7abaa9d428014891c51b4ac6878ea0407016fd","datavalue":{"value":{"amount":"+0.8115428686141968","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":"Q1190750$D5AEA7A6-3C58-45CB-99A1-FA4707ABE183","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e6d4418c6ab3a19e370821db78b9158630d9d78","datavalue":{"value":{"entity-type":"item","numeric-id":797636,"id":"Q797636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cdaecef28e118b1bfe37fcb8078d9586175260b9","datavalue":{"value":{"amount":"+0.7998571991920471","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":"Q1190750$141106DE-AE30-40B3-997C-B021AEE01270","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a6ccf756f27534dae7d650f4f4413f1c726dab92","datavalue":{"value":{"entity-type":"item","numeric-id":3349050,"id":"Q3349050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff585bbad3b20e636ad7afc3214708208dc5daad","datavalue":{"value":{"amount":"+0.7894272208213806","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":"Q1190750$2BD08D74-30A6-468C-9785-533248362C10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"14884de1cf080ec8e60561f2d07d1c85e888df2b","datavalue":{"value":{"entity-type":"item","numeric-id":5749394,"id":"Q5749394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24c1c98c3920e1ec3f98989a32b6425216b79011","datavalue":{"value":{"amount":"+0.7747517824172974","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":"Q1190750$A113AFA6-2E66-4F16-94D5-D60A25F3F285","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1190750","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1190750"}}}}}