کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656682 1632977 2016 36 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Functional graphs of polynomials over finite fields
ترجمه فارسی عنوان
نمودارهای کاربردی چند جملهای بر حوزه های محدود
کلمات کلیدی
نقشه های چندجمله ای، نمودار عملکردی، زمینه های محدود، مبلغ کاراکتر، الگوریتم درختان
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

Given a function f   in a finite field FqFq of q elements, we define the functional graph of f as a directed graph on q   nodes labelled by the elements of FqFq where there is an edge from u to v   if and only if f(u)=vf(u)=v. We obtain some theoretical estimates on the number of non-isomorphic graphs generated by all polynomials of a given degree. We then develop a simple and practical algorithm to test the isomorphism of quadratic polynomials that has linear memory and time complexities. Furthermore, we extend this isomorphism testing algorithm to the general case of functional graphs, and prove that, while its time complexity deviates from linear by a (usually small) multiplier dependent on graph parameters, its memory complexity remains linear. We exploit this algorithm to provide an upper bound on the number of functional graphs corresponding to polynomials of degree d   over FqFq. Finally, we present some numerical results and compare function graphs of quadratic polynomials with those generated by random maps and pose interesting new problems.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 116, January 2016, Pages 87–122
نویسندگان
, , , , , ,