{"entities":{"Q700165":{"pageid":702014,"ns":120,"title":"Item:Q700165","lastrevid":63617673,"modified":"2026-04-11T14:23:10Z","type":"item","id":"Q700165","labels":{"en":{"language":"en","value":"Explicit computation of isomorphisms between finite fields"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1809732"}},"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":"Q700165$91450958-520B-4F3A-8F1A-F225A43B5AC9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4139be02a383505f2646947fa1f7a1b3f26e85e1","datavalue":{"value":{"text":"Explicit computation of isomorphisms between finite fields","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q700165$F50F3598-0F3C-4FCF-87C1-5FA6A6267F05","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ae922de4fe053f4e73ca9f88bd4b55741dbaf131","datavalue":{"value":"1058.11071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q700165$6CF88486-C636-46FF-8D79-D17EAB85B3CE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e389905a04d19d58bd80245b6d90a35f83f7966d","datavalue":{"value":{"entity-type":"item","numeric-id":700163,"id":"Q700163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q700165$27D69942-595A-41A4-B9EE-8009F33B28F4","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":"Q700165$EF4CC1E2-5F23-482A-8257-33DF686919CD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"bffdc8b8d5e9929ac7ba3da2bea94b5f4ddd4baf","datavalue":{"value":{"time":"+2002-09-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q700165$611CF683-997B-4B47-BCFC-6F6D9179C07B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0576ef2aa33306c130d573cade406a86d8fc0e8d","datavalue":{"value":"Let \\(T_1\\) and \\(T_2\\) be two irreducible polynomials of degree \\(n\\) over the finite field \\(\\mathbb F_p\\), where \\(p\\) is a prime. Then the finite fields \\(K_1 = \\mathbb F_p[X]/(T_1)\\) and \\(K_2 = \\mathbb F_p[X]/(T_2)\\) both have \\(p^n\\) elements and so are isomorphic. The isomorphism can be represented as a polynomial \\(S\\) over \\(\\mathbb F_p\\) such that \\(T_1 \\circ S \\equiv 0 \\pmod{T_2}\\). The paper presents a fast algorithm to construct \\(S\\) using Kummer and Artin-Schreier theory. The four cases \\(n \\mid p-1\\), \\(p \\nmid n\\), \\(n = p^k\\) and \\(n = qp^k\\) are treated separately. When \\(n \\mid p-1\\) there exists a primitive \\(n\\)th root of unity \\(\\zeta\\) in \\(\\mathbb F_p\\), so \\(K_1\\) is a Kummer extension of \\(\\mathbb F_p\\). This simple special case of \\(p \\nmid n\\) leads to a faster implementation.  More generally, when \\(p \\nmid n\\), let \\(C = \\mathbb F_p[\\zeta]\\). Classical Kummer theory relies on a tower of extensions of \\(\\mathbb F_p\\), but instead the paper extends Kummer theory to the \\(\\mathbb F_p\\)-algebra \\(K_1 \\otimes_{\\mathbb F_p} C\\) as follows. If \\(k\\) is a field, \\(K\\) a cyclic extension of \\(k\\) of degree \\(n\\) prime to the characteristic of \\(k\\), and \\(C\\) a finite extension of \\(k\\) containing a primitive \\(n\\)th root of unity, then the \\(C\\)-algebra \\(K \\otimes_k C\\) is an \u00e9tale algebra, i.e.\\ it has no nonzero nilpotent elements. Denote by \\(\\sigma\\) a generator of the Galois group of the extension \\(K/k\\). Then the set of elements of the \\(k\\)-algebra \\(K \\otimes_k C\\) fixed by the automorphism \\(\\widetilde\\sigma : x \\otimes y \\mapsto \\sigma(x) \\otimes y\\) is a field isomorphic to \\(C\\).  The characteristic polynomial of \\(\\sigma\\) considered as an endomorphism of the \\(k\\)-vector space \\(K\\) is equal to \\(X^n-1\\), and ker(\\(\\widetilde\\sigma - \\zeta\\text{id}\\)) is a one-dimensional vector space over \\(C\\). If \\(\\alpha\\) and \\(\\beta\\) are eigenvectors of \\(\\widetilde\\sigma\\) for the eigenvalue \\(1 \\otimes \\zeta\\) then both \\(\\alpha^n\\) and \\(\\beta^n\\) are nonzero elements of \\(k \\otimes_k C\\), \\(\\alpha^n/\\beta^n\\) is an \\(n\\)th power in \\(k \\otimes_k C\\), and if \\(\\alpha^n = \\beta^n\\) then there exists an integer \\(j\\) such that \\(\\alpha = \\widetilde\\sigma^j(\\beta)\\). Assuming that \\(\\zeta\\) generates \\(C\\) over \\(k\\), so that \\(C = k(\\zeta)\\), let \\(r = [C:k]\\). If \\(a_0\\) is the first component of \\(\\alpha\\) on the power basis \\((1 \\otimes \\zeta^i)_{i=0}^{r-1}\\) of \\(K \\otimes_k C\\) over \\(C\\) then \\(a_0\\) is a primitive element for the extension \\(K/k\\). The above theory leads fairly directly to the main algorithm of the paper, in which the efficient factorization over \\(\\mathbb F_p\\) of cyclotomic polynomials is based on Theorem 9 of \\textit{V. Shoup} [J. Symb. Comput. 17, 371--391 (1994; Zbl 0815.11059)].  When \\(n = p^k\\), Artin-Schreier theory is used to construct almost-canonical irreducible polynomials of degree \\(p^k\\), using Lemma 2.3 of Shoup (loc. cit.), and an explicit algorithm is given. When \\(n = qp^k\\), the procedure is first to compute isomorphisms between extensions of \\(\\mathbb F_p\\) of order \\(q\\) and order \\(p^k\\), and then combine them, following Lemma 2.4 of \\textit{V. Shoup} [Math. Comput. 54, 435--447 (1990; Zbl 0712.11077)]. Finally, an algorithm is given to factorize over \\(K_2\\) a polynomial over \\(\\mathbb F_p\\), based on Galois theory and using the previous algorithms to compute isomorphisms. Timings are given for an implementation using PARI [\\textit{C. Batut, K. Belabas, D. Bernardi, H. Cohen,} and \\textit{M. Olivier}, User's guide to PARI-GP, version 2.0.19.], which in most cases are significantly faster than the root-finding function in NTL [\\textit{V. Shoup}, NTL: A library for doing number theory (version 4.0a), http://www.shoup.net/ntl/].","type":"string"},"datatype":"string"},"type":"statement","id":"Q700165$19C008C4-1681-4517-96BA-7F914099A1F4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"01d2861165170082a6b93beafe0f21e87b2f19ee","datavalue":{"value":{"entity-type":"item","numeric-id":700164,"id":"Q700164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q700165$A4ECDC54-3A49-4BC7-B7B7-9984C2D772C5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q700165$D3428495-2649-41E4-9D5A-E74CDDD50D2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"157305dfd5c4a00203c592f58c4b16e8bc6d182b","datavalue":{"value":"11T30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q700165$ABCBC371-00A6-43AA-8C23-6BA49F93B115","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cdeb0c697807c27c4bd5801c766181e8a14ababc","datavalue":{"value":"1809732","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q700165$C0A67276-4515-4776-870A-ECAC64EA77B5","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"80e13f713e4a9d791edc305e16d4730bf0eb3d4f","datavalue":{"value":{"entity-type":"item","numeric-id":13393,"id":"Q13393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q700165$BCE34341-0457-4F17-B721-899BDC0DD62B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"5199c731888cb3ba10630bedfbd9575640bb4daa","datavalue":{"value":{"entity-type":"item","numeric-id":13434,"id":"Q13434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q700165$F206A20F-5555-4DC0-BFE8-478B810ABECD","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":"Q700165$FFB9FDBA-F95D-406F-9006-3C60BD0E3F77","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"93fc7a419aa2dd1be5ebde9499b89c4d3b436c50","datavalue":{"value":"https://doi.org/10.1006/ffta.2001.0344","type":"string"},"datatype":"url"},"type":"statement","id":"Q700165$B3E07BBA-0822-4D06-90D2-8E108FBF428A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6fc821eba2db482a7eb4b70ca512e97ae789d102","datavalue":{"value":"W2095191510","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q700165$CAE5DEF8-B84B-4B26-868B-A4E4E27E4733","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b7d03acfe694d55b5bfb81a8721b654f11fafd6","datavalue":{"value":{"entity-type":"item","numeric-id":3139838,"id":"Q3139838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q700165$7F9D60C0-4B31-449A-9E3F-A6C76F0BBEFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f62e2eb38860e3d36d846e3738c20dc2c2b0e66c","datavalue":{"value":{"entity-type":"item","numeric-id":3491686,"id":"Q3491686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q700165$8E05255A-EB75-42A3-BA72-46921ED0EB87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90510f4dee0b4cb63a1b6cecd2f7aa83f934cd29","datavalue":{"value":{"entity-type":"item","numeric-id":4396457,"id":"Q4396457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q700165$491D898D-564F-4ECF-A150-588ACF2A2141","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fbb248515103736ab3ddd5613b186a704911c860","datavalue":{"value":{"entity-type":"item","numeric-id":5906578,"id":"Q5906578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q700165$E3988F81-725B-47D5-A914-697256698F0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b6235e1e6d2d7fcb045ea61a7f80b32ab5ff51a","datavalue":{"value":{"entity-type":"item","numeric-id":3497178,"id":"Q3497178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q700165$185F1A79-82B9-484C-9CDF-752AAF50951C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6a7a6cd98e63874e2f91d5178c6982ae66780b00","datavalue":{"value":"10.1006/FFTA.2001.0344","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q700165$4889EE8D-98A8-4DBE-ACE3-EBC5C166B226","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7f217d2ff6c587bfb841e2b1b25edbca67a1f0c","datavalue":{"value":{"entity-type":"item","numeric-id":3491686,"id":"Q3491686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce5f7f5d07fa1413c7d36bdd6f754b12caad3bb2","datavalue":{"value":{"amount":"+0.8714110851287842","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":"Q700165$B17D3F01-E21A-40F7-AB81-BF67EA51214B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9711bfb8916802120679f4287c5ebe05c73312f9","datavalue":{"value":{"entity-type":"item","numeric-id":910432,"id":"Q910432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1fb11b67aa4bdad60b4b9d6bb4648fc83a933755","datavalue":{"value":{"amount":"+0.8114103674888611","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":"Q700165$852B8723-FCE0-4861-86A6-A224F820E1CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa34ee871411aed432e1098ebc2f6637e7a21c14","datavalue":{"value":{"entity-type":"item","numeric-id":4612574,"id":"Q4612574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e4f579eb442657280d3a172a6295cae43555f5c","datavalue":{"value":{"amount":"+0.8087929487228394","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":"Q700165$883540C6-68C7-43D3-9B59-002C0F02F0B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e084f32e99c44feb4df505f94049e3ad2dc2a9aa","datavalue":{"value":{"entity-type":"item","numeric-id":3481819,"id":"Q3481819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b73442e70ce74e6b5d174e4f4096f331e2785a13","datavalue":{"value":{"amount":"+0.8062242269515991","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":"Q700165$EC8CEFCF-86CE-42D0-BE7A-90EE611CA286","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bda4ecc76bcca88d565439097c411c1d57964ba5","datavalue":{"value":{"entity-type":"item","numeric-id":1167763,"id":"Q1167763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4de6ab70cfa974e405c0071c294c4e8b2e6754ef","datavalue":{"value":{"amount":"+0.8034684658050537","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":"Q700165$5239A2DB-6EE9-4DDB-9971-EAED12391F36","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Explicit computation of isomorphisms between finite fields","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Explicit_computation_of_isomorphisms_between_finite_fields"}}}}}