{"entities":{"Q1344091":{"pageid":1354830,"ns":120,"title":"Item:Q1344091","lastrevid":47300095,"modified":"2026-01-01T06:59:53Z","type":"item","id":"Q1344091","labels":{"en":{"language":"en","value":"Tests for permutation functions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 720501"}},"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":"Q1344091$EA84521C-02D9-4128-BF6E-AAFC6ECD9E8B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3dde373c14a81dbadd79dd8fcd553084af9cd37f","datavalue":{"value":{"text":"Tests for permutation functions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1344091$BB7F710A-5684-4E5A-9C5F-B6A317417F15","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fae9ac04e86d54442b46fbd997f3a1992adf791e","datavalue":{"value":"0820.11073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1344091$8E5879AF-7C41-4B59-AB81-20208AC0B849","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b3fceea3389b17a8b89a3cb62aab2546ba593a36","datavalue":{"value":{"entity-type":"item","numeric-id":912619,"id":"Q912619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1344091$43D8AFA0-1D3C-4B52-8F2B-A54C24B704A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7429c710692d5d0c38830d08277242d2066f38db","datavalue":{"value":{"entity-type":"item","numeric-id":165879,"id":"Q165879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1344091$FC3370D8-1FAD-43F2-8EED-46E7F4FB0158","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"33122a93dfb64681be222c65bf841053fa198b88","datavalue":{"value":{"entity-type":"item","numeric-id":165874,"id":"Q165874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1344091$156A0F08-C148-4B9D-B9C9-53335264B5F8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"191728e620ca2d66220fdf5e72b7e38829c4c6cf","datavalue":{"value":{"time":"+1995-02-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1344091$D21C323E-16D3-434D-B6A2-5DAAEC894811","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e70b478696a13454e3cb9f6afdfcec6665bd0748","datavalue":{"value":"For \\(q\\) a prime power, let \\(\\mathbb{F}_ q\\) denote the finite field of order \\(q\\) and let \\(f\\in \\mathbb{F}_ q (x)\\) be a rational function over \\(\\mathbb{F}_ q\\). \\(D\\subseteq \\mathbb{F}_ q\\) will denote the domain of definition of \\(f\\). In recent years many papers have been written concerning permutation polynomials over \\(\\mathbb{F}_ q\\), i.e. permutations which are induced by polynomials over \\(\\mathbb{F}_ q\\). In this paper the authors consider several more general settings and study three notions of permutation function: (i) \\(f\\) is a permutation of \\(\\mathbb{F}_ q\\); (ii) \\(f\\) is a permutation on \\(D\\); (iii) \\(f\\) is injective on \\(D\\).    The paper contains many detailed results concerning each of these notions of permutation function as well as their inter-connections. In particular for each of them, a random polynomial-time algorithm test is presented. In addition, for the image or value set size of an arbitrary rational function, a fully polynomial-time randomized approximation scheme is given. Finally the paper concludes with a list of five open questions.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1344091$8A5CA84D-B352-4555-A20E-1CA721141C33","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7103934093940ed00bd032af288aef5e1c1d07ea","datavalue":{"value":{"entity-type":"item","numeric-id":234387,"id":"Q234387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1344091$3891455D-8018-435C-9232-2C6B1A3019F9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"157305dfd5c4a00203c592f58c4b16e8bc6d182b","datavalue":{"value":"11T30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1344091$7638BEC4-E623-4EE1-B460-C4F6C27D8DEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5005488ac12471348bfecb95099a57fd4da722ac","datavalue":{"value":"11T06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1344091$F2CCDEB1-412E-43BF-A6EE-01E615B8F5E7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dd64404b1edec2012d0bf3a6ba79c1de3d7c9de5","datavalue":{"value":"720501","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1344091$F2DFBEA0-7130-44F4-969E-91926566635C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a3711b386902559bb22bf67091b7eca92012716a","datavalue":{"value":"finite field","type":"string"},"datatype":"string"},"type":"statement","id":"Q1344091$0ECA5C04-8B01-4EFE-A495-63AB0AB957FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"82749bd5b48db862a59a512b087a79ccf4652d64","datavalue":{"value":"permutation polynomials","type":"string"},"datatype":"string"},"type":"statement","id":"Q1344091$C83B11D5-4248-46A1-8DFF-CDD47EF8992E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"907748f71d03f88161e1a4e38523442a9ab79b34","datavalue":{"value":"permutation function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1344091$0A0B4787-556A-49C6-888F-A47BD156879E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"283c25598a757edec6aa9c81e987197426ae50d7","datavalue":{"value":"random polynomial-time algorithm test","type":"string"},"datatype":"string"},"type":"statement","id":"Q1344091$796C4430-C1EA-41DD-A0EC-300501AE0D58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ebdae972efd17280aec739e1ef6654f11fed6fa3","datavalue":{"value":"polynomial-time randomized approximation scheme","type":"string"},"datatype":"string"},"type":"statement","id":"Q1344091$1E1AB9BE-C5CC-4D8E-824A-E83957D38235","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88dfc651eef17a1e0c9a34c9bb44e29ddc054131","datavalue":{"value":"open questions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1344091$C09A6BCF-9C19-423C-9726-67757E243DEE","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":"Q1344091$B7DD7640-0385-4971-9259-FA2DAF41EAAF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7fa0c12bf9286526202b12b060296f7bd6e3c3ba","datavalue":{"value":"https://doi.org/10.1006/ffta.1995.1003","type":"string"},"datatype":"url"},"type":"statement","id":"Q1344091$A6CCFC69-58E1-475E-83FE-CD1DD37BC57C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a225cce66bd65bc655a816f7cf9cb3da11bc65f1","datavalue":{"value":"W1981913693","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1344091$0139F1FD-39D7-41A8-86AE-E2E85682C367","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"df6c1798a325c5d49ebf65ba24b786039fc0924d","datavalue":{"value":"10.1006/FFTA.1995.1003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1344091$F86FE5DD-E932-4CFC-B0EE-03CFB44E6084","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3388db6bfd28079b1b3dae99449484e8e5350a8","datavalue":{"value":{"entity-type":"item","numeric-id":3360269,"id":"Q3360269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"afb3f5f6ac639e9f33fa9ac91ef5085563407796","datavalue":{"value":{"amount":"+0.8619017004966736","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":"Q1344091$EC69892A-ACB1-479B-AE76-E5875E88E7C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aad1a907853fbb200bf6b29672f3004ce0628367","datavalue":{"value":{"entity-type":"item","numeric-id":1207336,"id":"Q1207336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da5bc43b7a25da3bf97dee4f0acb41fdf77da2d7","datavalue":{"value":{"amount":"+0.8496386408805847","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":"Q1344091$E5CB01F0-C993-4DFD-ADB4-E7BF907CE749","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2915b171c4cbb65ae3c78df9182afe42151c5012","datavalue":{"value":{"entity-type":"item","numeric-id":5890844,"id":"Q5890844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"25dd3f1a72c0f1ad6f23ee61cff200cf59912336","datavalue":{"value":{"amount":"+0.8432558178901672","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":"Q1344091$957A1B99-023A-4067-B0DD-E07CF497F2E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"093090684beb7d2c6404de09e467e23aecf8ef04","datavalue":{"value":{"entity-type":"item","numeric-id":5917358,"id":"Q5917358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18d536da94bdadf40263f2582c20f48aed86790c","datavalue":{"value":{"amount":"+0.8391653299331665","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":"Q1344091$497669A0-B2EC-4A64-88E5-C5D2443EC2A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ee2cebbb46b678517bcc5ad813e7e53a4913fc9","datavalue":{"value":{"entity-type":"item","numeric-id":2238914,"id":"Q2238914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1d39608e393bb4394900ae2e6ba904ad6eb50b2","datavalue":{"value":{"amount":"+0.8376412987709045","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":"Q1344091$1FCDD9AD-3A8E-4325-B6D3-54DA9B6B8B8E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1344091","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1344091"}}}}}