DOI: https://doi.org/10.1109/tit.2026.3657349
تاريخ النشر: 2026-02-03
المؤلف: Yanbin Zheng وآخرون
الموضوع الرئيسي: نظرية الترميز والتشفير
نظرة عامة
في هذا القسم، يقدم المؤلفون مفهوم الخرائط من $m$ إلى 1 بين مجموعتين نهائيتين، والذي يخدم لتوحيد وتعميم التعريفات الموجودة للخرائط من 2 إلى 1 و $n$ إلى 1 الموجودة في الأدبيات الحديثة. يقدمون معيارًا محليًا عامًا لتحديد ما إذا كانت الخريطة من $m$ إلى 1 ويقدمون ثلاث بنى جديدة من هذه الخرائط، والتي تمتد مجتمعةً إلى البنى السابقة الموثقة في الأدبيات. يستكشف المؤلفون أيضًا العلاقة بين الخرائط من $m$ إلى 1 على المجموعة الضربية $F^*_q$ والخرائط من $m_2$ إلى 1 على المجموعة الفرعية $U_\ell$، حيث $m_2 = m/(r,s)$ و $\ell = (q-1)/s$.
تبحث الورقة أيضًا في خاصية $m_2$ إلى 1 للخريطة $x^r h(x)^s$ على $U_\ell$ عبر أربع حالات متميزة. بالإضافة إلى ذلك، يتم اقتراح طريقة تكرارية لتوليد خرائط من $m$ إلى 1 من خرائط موجودة من $m$ إلى 1. تسهم النتائج بشكل كبير في فهم الخرائط من $m$ إلى 1، مقدمةً دراسات منهجية لفئات صريحة لقيم صغيرة من $m$ أو مؤشرات محددة $\ell$، وتأسيس روابط مع أنواع مختلفة من الخرائط الأساسية، بما في ذلك الحدود والدوال الكسرية.
مقدمة
تناقش مقدمة هذه الورقة الدراسة الواسعة للخرائط من واحد إلى واحد (التباديل) من حقل نهائي \( F_q \) إلى نفسه، بالإضافة إلى الاهتمام المتزايد في الخرائط من اثنين إلى واحد، والتي ترتبط بالرموز الخطية والدوال التشفيرية مثل APN، والخطية، والدوال المنحنية. يهدف المؤلفون إلى توحيد وتعميم النتائج الموجودة من خلال استكشاف منهجي للخرائط من \( m \) إلى واحد، وهي فئة أوسع تشمل الخرائط من اثنين إلى واحد. تحدد الورقة التعريفات وخصائص هذه الخرائط، مع التأكيد على أهميتها في علم التشفير ونظرية الترميز.
يستعرض المؤلفون التقدمات المهمة في هذا المجال، بما في ذلك مختلف البنى والتصنيفات للخرائط من اثنين إلى واحد، وخاصة تلك المشتقة من الأشكال الحدودية ومعايير مشابهة لـ AGW. يبرزون النتائج الرئيسية من الدراسات الحديثة، مثل غياب بعض الخرائط الحدودية من الدرجة 5 على \( F_{2^n} \) لـ \( n > 9 \) والروابط بين الخرائط من اثنين إلى واحد والهياكل الهندسية. تختتم المقدمة بتقديم مفهوم جديد للخرائط من \( m \) إلى واحد، مما يسمح بتوصيف أكثر مرونة للخرائط، وبالتالي تمهيد الطريق لمزيد من الاستكشاف النظري والتطبيقات العملية في علم التشفير والترميز.
نقاش
في هذا القسم، يناقش المؤلفون بناء الخرائط من العديد إلى واحد، مدفوعين بمعيار AGW للخرائط من واحد إلى واحد. يحدد معيار AGW الشروط التي بموجبها تكون الخريطة \( f: A \to \bar{A} \) من واحد إلى واحد بناءً على الخرائط بين مجموعات أصغر \( S \) و \( \bar{S} \). تسمح التعميمات الحديثة لهذا المعيار ببناء خرائط من $m$ إلى 1، حيث يمكن أن يكون $m$ 2 أو أكثر. يستعرض المؤلفون عدة اقتراحات ونظريات تقدم شروطًا ضرورية وكافية لهذه الخرائط، مع تسليط الضوء على أهمية الشمولية وبنية المجموعات المعنية.
تقدم الورقة تعريفًا موحدًا للخرائط من $m$ إلى 1 وتعرض معيارًا محليًا عامًا يبسط تحديد ما إذا كانت الخريطة من $m$ إلى 1. يتم اقتراح ثلاث بنى للخرائط من $m$ إلى 1، كل منها يقلل من تعقيد المشكلة من خلال ربطها بمجموعات فرعية أبسط أو خرائط مرتبطة. كما يوضح المؤلفون كيف يمكن تطبيق هذه البنى على حالات محددة، مثل الحدود على الحقول النهائية، ويقدمون شروطًا صريحة تحتها تحتفظ هذه الخرائط. بشكل عام، تسهم النتائج في فهم أعمق لبنية وخصائص الخرائط من العديد إلى واحد في المجموعات النهائية.
DOI: https://doi.org/10.1109/tit.2026.3657349
Publication Date: 2026-02-03
Author(s): Yanbin Zheng et al.
Primary Topic: Coding theory and cryptography
Overview
In this section, the authors introduce the concept of $m$-to-1 mappings between two finite sets, which serves to unify and generalize existing definitions of 2-to-1 and $n$-to-1 mappings found in recent literature. They provide a generalized local criterion for determining whether a mapping is $m$-to-1 and present three novel constructions of such mappings, which collectively extend previous constructions documented in the literature. The authors also explore the relationship between $m$-to-1 mappings on the multiplicative group $F^*_q$ and $m_2$-to-1 mappings on the subgroup $U_\ell$, where $m_2 = m/(r,s)$ and $\ell = (q-1)/s$.
The paper further investigates the $m_2$-to-1 property of the mapping $x^r h(x)^s$ on $U_\ell$ across four distinct cases. Additionally, a recursive method for generating $m$-to-1 mappings from existing $m$-to-1 mappings is proposed. The findings contribute significantly to the understanding of $m$-to-1 mappings, offering systematic studies of explicit classes for small values of $m$ or specific indices $\ell$, and establishing connections with various types of underlying mappings, including monomials and rational functions.
Introduction
The introduction of this paper discusses the extensive study of one-to-one mappings (permutations) from a finite field \( F_q \) to itself, as well as the emerging interest in two-to-one mappings, which are linked to linear codes and cryptographic functions such as APN, planar, and bent functions. The authors aim to unify and generalize existing results by systematically exploring \( m \)-to-one mappings, a broader category that includes two-to-one mappings. The paper outlines the definitions and properties of these mappings, emphasizing their relevance in cryptography and coding theory.
The authors review significant advancements in the field, including various constructions and classifications of two-to-one mappings, particularly those derived from polynomial forms and AGW-like criteria. They highlight key findings from recent studies, such as the absence of certain polynomial mappings of degree 5 over \( F_{2^n} \) for \( n > 9 \) and the connections between two-to-one mappings and geometric structures. The introduction concludes by presenting the novel concept of \( m \)-to-one mappings, which allows for a more flexible characterization of mappings, thus paving the way for further theoretical exploration and practical applications in cryptography and coding.
Discussion
In this section, the authors discuss the construction of many-to-one mappings, motivated by the AGW criterion for one-to-one mappings. The AGW criterion establishes conditions under which a mapping \( f: A \to \bar{A} \) is one-to-one based on mappings between smaller sets \( S \) and \( \bar{S} \). Recent generalizations of this criterion allow for the construction of \( m \)-to-1 mappings, where \( m \) can be 2 or more. The authors review several propositions and theorems that provide necessary and sufficient conditions for these mappings, highlighting the importance of surjectivity and the structure of the sets involved.
The paper introduces a unified definition of \( m \)-to-1 mappings and presents a generalized local criterion that simplifies the determination of whether a mapping is \( m \)-to-1. Three constructions of \( m \)-to-1 mappings are proposed, each reducing the complexity of the problem by relating it to simpler subsets or associated mappings. The authors also illustrate how these constructions can be applied to specific cases, such as polynomials over finite fields, and provide explicit conditions under which these mappings hold. Overall, the findings contribute to a deeper understanding of the structure and properties of many-to-one mappings in finite sets.