The Experts below are selected from a list of 768021 Experts worldwide ranked by ideXlab platform
Chaoping Xing - One of the best experts on this subject based on the ideXlab platform.
-
On subFields of the Hermitian Function Field involving the involution automorphism
Journal of Number Theory, 2019Co-Authors: Chaoping XingAbstract:Abstract A Function Field over a finite Field is called maximal if it achieves the Hasse–Weil bound. Finding possible genera that maximal Function Fields can achieve has both theoretical interest and practical applications to coding theory and other topics. As a subField of a maximal Function Field is also maximal, one way to find maximal Function Fields is to find all subFields of a maximal Function Field. Due to the large automorphism group of the Hermitian Function Field, it is natural to find as many subFields of the Hermitian Function Field as possible. In literature, most of papers studied subFields fixed by subgroups of the decomposition group at one point (usually the point at infinity). This is because it becomes much more complicated to study the subField fixed by a subgroup that is not contained in the decomposition group at one point. In this paper, we study subFields of the Hermitian Function Field fixed by subgroups that are not contained in the decomposition group of any point except the cyclic subgroups. It turns out that some new maximal Function Fields are found.
-
On subFields of the Hermitian Function Fields involving the involution automorphism
arXiv: Number Theory, 2017Co-Authors: Chaoping XingAbstract:A Function Field over a finite Field is called maximal if it achieves the Hasse-Weil bound. Finding possible genera that maximal Function Fields achieve has both theoretical interest and practical applications to coding theory and other topics. As a subField of a maximal Function Field is also maximal, one way to find maximal Function Fields is to find all subFields of a maximal Function Field. Due to the large automorphism group of the Hermitian Function Field, it is natural to find as many subFields of the Hermitian Function Field as possible. In literature, most of papers studied subFields fixed by subgroups of the decomposition group at one point (usually the point at infinity). This is because it becomes much more complicated to study the subField fixed by a subgroup that is not contained in the decomposition group at one point. In this paper, we study subFields of the Hermitian Function Field fixed by subgroups that are not contained in the decomposition group of any point except the cyclic subgroups. It turns out that some new maximal Function Fields are found.
-
folded codes from Function Field towers and improved optimal rate list decoding
Symposium on the Theory of Computing, 2012Co-Authors: Venkatesan Guruswami, Chaoping XingAbstract:We give a new construction of algebraic codes which are efficiently list decodable from a fraction 1-R-e of adversarial errors where R is the rate of the code, for any desired positive constant e. The worst-case list size output by the algorithm is O(1/e), matching the existential bound for random codes up to constant factors. Further, the alphabet size of the codes is a constant depending only on e --- it can be made exp(~O(1/e2)) which is not much worse than the non-constructive exp(1/e) bound of random codes. The code construction is Monte Carlo and has the claimed list decoding property with high probability. Once the code is (efficiently) sampled, the encoding/decoding algorithms are deterministic with a running time Oe(Nc) for an absolute constant $c$, where N is the code's block length. Our construction is based on a careful combination of a linear-algebraic approach to list decoding folded codes from towers of Function Fields, with a special form of subspace-evasive sets. Instantiating this with the explicit "asymptotically good" Garcia-Stichtenoth (GS for short) tower of Function Fields yields the above parameters. To illustrate the method in a simpler setting, we also present a construction based on Hermitian Function Fields, which offers similar guarantees with a list-size and alphabet size polylogarithmic in the block length N. In comparison, algebraic codes achieving the optimal trade-off between list decodability and rate based on folded Reed-Solomon codes have a decoding complexity of NΩ(1/e), an alphabet size of NΩ(1/e2), and a list size of O(1/e2) (even after combination with subspace-evasive sets). Thus we get an improvement over the previous best bounds in all three aspects simultaneously, and are quite close to the existential random coding bounds. Along the way, we shed light on how to use automorphisms of certain Function Fields to enable list decoding of the folded version of the associated algebraic-geometric codes.
-
folded codes from Function Field towers and improved optimal rate list decoding
arXiv: Information Theory, 2012Co-Authors: Venkatesan Guruswami, Chaoping XingAbstract:We give a new construction of algebraic codes which are efficiently list decodable from a fraction $1-R-\eps$ of adversarial errors where $R$ is the rate of the code, for any desired positive constant $\eps$. The worst-case list size output by the algorithm is $O(1/\eps)$, matching the existential bound for random codes up to constant factors. Further, the alphabet size of the codes is a constant depending only on $\eps$ - it can be made $\exp(\tilde{O}(1/\eps^2))$ which is not much worse than the lower bound of $\exp(\Omega(1/\eps))$. The parameters we achieve are thus quite close to the existential bounds in all three aspects - error-correction radius, alphabet size, and list-size - simultaneously. Our code construction is Monte Carlo and has the claimed list decoding property with high probability. Once the code is (efficiently) sampled, the encoding/decoding algorithms are deterministic with a running time $O_\eps(N^c)$ for an absolute constant $c$, where $N$ is the code's block length. Our construction is based on a linear-algebraic approach to list decoding folded codes from towers of Function Fields, and combining it with a special form of subspace-evasive sets. Instantiating this with the explicit "asymptotically good" Garcia-Stichtenoth tower of Function Fields yields the above parameters. To illustrate the method in a simpler setting, we also present a construction based on Hermitian Function Fields, which offers similar guarantees with a list and alphabet size polylogarithmic in the block length $N$. Along the way, we shed light on how to use automorphisms of certain Function Fields to enable list decoding of the folded version of the associated algebraic-geometric codes.
-
Function-Field codes
Applicable Algebra in Engineering Communication and Computing, 2008Co-Authors: Dirk Hachenberger, Harald Niederreiter, Chaoping XingAbstract:Function-Field codes provide a general perspective on the construction of algebraic-geometry codes. We briefly review the theory of Function-Field codes and establish some new results in this theory, including a propagation rule. We show how to derive linear codes from Function-Field codes, thus generalizing a construction of linear codes due to Xing, Niederreiter, and Lam.
Venkatesan Guruswami - One of the best experts on this subject based on the ideXlab platform.
-
folded codes from Function Field towers and improved optimal rate list decoding
Symposium on the Theory of Computing, 2012Co-Authors: Venkatesan Guruswami, Chaoping XingAbstract:We give a new construction of algebraic codes which are efficiently list decodable from a fraction 1-R-e of adversarial errors where R is the rate of the code, for any desired positive constant e. The worst-case list size output by the algorithm is O(1/e), matching the existential bound for random codes up to constant factors. Further, the alphabet size of the codes is a constant depending only on e --- it can be made exp(~O(1/e2)) which is not much worse than the non-constructive exp(1/e) bound of random codes. The code construction is Monte Carlo and has the claimed list decoding property with high probability. Once the code is (efficiently) sampled, the encoding/decoding algorithms are deterministic with a running time Oe(Nc) for an absolute constant $c$, where N is the code's block length. Our construction is based on a careful combination of a linear-algebraic approach to list decoding folded codes from towers of Function Fields, with a special form of subspace-evasive sets. Instantiating this with the explicit "asymptotically good" Garcia-Stichtenoth (GS for short) tower of Function Fields yields the above parameters. To illustrate the method in a simpler setting, we also present a construction based on Hermitian Function Fields, which offers similar guarantees with a list-size and alphabet size polylogarithmic in the block length N. In comparison, algebraic codes achieving the optimal trade-off between list decodability and rate based on folded Reed-Solomon codes have a decoding complexity of NΩ(1/e), an alphabet size of NΩ(1/e2), and a list size of O(1/e2) (even after combination with subspace-evasive sets). Thus we get an improvement over the previous best bounds in all three aspects simultaneously, and are quite close to the existential random coding bounds. Along the way, we shed light on how to use automorphisms of certain Function Fields to enable list decoding of the folded version of the associated algebraic-geometric codes.
-
folded codes from Function Field towers and improved optimal rate list decoding
arXiv: Information Theory, 2012Co-Authors: Venkatesan Guruswami, Chaoping XingAbstract:We give a new construction of algebraic codes which are efficiently list decodable from a fraction $1-R-\eps$ of adversarial errors where $R$ is the rate of the code, for any desired positive constant $\eps$. The worst-case list size output by the algorithm is $O(1/\eps)$, matching the existential bound for random codes up to constant factors. Further, the alphabet size of the codes is a constant depending only on $\eps$ - it can be made $\exp(\tilde{O}(1/\eps^2))$ which is not much worse than the lower bound of $\exp(\Omega(1/\eps))$. The parameters we achieve are thus quite close to the existential bounds in all three aspects - error-correction radius, alphabet size, and list-size - simultaneously. Our code construction is Monte Carlo and has the claimed list decoding property with high probability. Once the code is (efficiently) sampled, the encoding/decoding algorithms are deterministic with a running time $O_\eps(N^c)$ for an absolute constant $c$, where $N$ is the code's block length. Our construction is based on a linear-algebraic approach to list decoding folded codes from towers of Function Fields, and combining it with a special form of subspace-evasive sets. Instantiating this with the explicit "asymptotically good" Garcia-Stichtenoth tower of Function Fields yields the above parameters. To illustrate the method in a simpler setting, we also present a construction based on Hermitian Function Fields, which offers similar guarantees with a list and alphabet size polylogarithmic in the block length $N$. Along the way, we shed light on how to use automorphisms of certain Function Fields to enable list decoding of the folded version of the associated algebraic-geometric codes.
Hwanyup Jung - One of the best experts on this subject based on the ideXlab platform.
-
Artin–Schreier extensions of the rational Function Field
Mathematische Zeitschrift, 2014Co-Authors: Hwanyup Jung, Pyung-lyun KangAbstract:In this paper we study the arithmetic of Artin–Schreier extensions of $$\mathbb {F}_{q}(T)$$ F q ( T ) . We determine the integral closure of $$\mathbb {F}_{q}[T]$$ F q [ T ] in Artin–Schreier extension of $$\mathbb {F}_{q}(T)$$ F q ( T ) . We also investigate the average values of the $$L$$ L -Functions of orders of Artin–Schreier extensions and study the average values of ideal class numbers when $$p=3$$ p = 3 in detail.
-
Determinant formulas for class numbers in Function Fields
Mathematics of Computation, 2004Co-Authors: Hwanyup Jung, Sunghan Bae, Jaehyun AhnAbstract:In this paper, by extending Kucera's idea to the Function Field case, we obtain several determinant formulas involving the real class number and the relative class number of any subField of cyclotomic Function Fields. We also provide several examples using these determinant formulas.
-
demjanenko matrix and recursion formula for relative class number over Function Fields
Journal of Number Theory, 2003Co-Authors: Hwanyup Jung, Jaehyun AhnAbstract:Abstract In this paper, we define Demjanenko matrix in Function Field and express the relative ideal class numbers h − ( O K P n ) as the determinant of this matrix. We also define another matrix which give us a recursion formula for the relative divisor class numbers h−(KPn).
Jaehyun Ahn - One of the best experts on this subject based on the ideXlab platform.
-
Determinant formulas for class numbers in Function Fields
Mathematics of Computation, 2004Co-Authors: Hwanyup Jung, Sunghan Bae, Jaehyun AhnAbstract:In this paper, by extending Kucera's idea to the Function Field case, we obtain several determinant formulas involving the real class number and the relative class number of any subField of cyclotomic Function Fields. We also provide several examples using these determinant formulas.
-
demjanenko matrix and recursion formula for relative class number over Function Fields
Journal of Number Theory, 2003Co-Authors: Hwanyup Jung, Jaehyun AhnAbstract:Abstract In this paper, we define Demjanenko matrix in Function Field and express the relative ideal class numbers h − ( O K P n ) as the determinant of this matrix. We also define another matrix which give us a recursion formula for the relative divisor class numbers h−(KPn).
Reynald Lercier - One of the best experts on this subject based on the ideXlab platform.
-
the Function Field sieve in the medium prime case
Lecture Notes in Computer Science, 2006Co-Authors: Antoine Joux, Reynald LercierAbstract:In this paper, we study the application of the Function Field sieve algorithm for computing discrete logarithms over finite Fields of the form F q n when q is a medium-sized prime power. This approach is an alternative to a recent paper of Granger and Vercauteren for computing discrete logarithms in tori, using efficient torus representations. We show that when q is not too large, a very efficient L(1/3) variation of the Function Field sieve can be used. Surprisingly, using this algorithm, discrete logarithms computations over some of these Fields are even easier than computations in the prime Field and characteristic two Field cases. We also show that this new algorithm has security implications on some existing cryptosystems, such as torus based cryptography in T 30 , short signature schemes in characteristic 3 and cryptosystems based on super-singular abelian varieties. On the other hand, cryptosystems involving larger baseFields and smaller extension degrees, typically of degree at most 6, such as LUC, XTR or T 6 torus cryptography, are not affected.
-
The Function Field Sieve is quite special
2002Co-Authors: Antoine Joux, Reynald LercierAbstract:In this paper, we describe improvements to the Function Field sieve (FFS) for the discrete logarithm problem in $GF(p^n)$, when $p$ is small. Our main contribution is a new way to build the algebraic Function Fields needed in the algorithm. With this new construction, the heuristic complexity is as good as the complexity of the construction proposed by Adleman and Huang~\cite{AdHu99}, i.e $L_{p^n}[{1}/{3},c] = \exp( (c+o(1)) \log(p^n)^{\frac{1}{3}} \log(\log(p^n))^{\frac{2}{3}})$ where $c=(32/9)^{\frac{1}{3}}$. With either of these constructions the FFS becomes an equivalent of the special number Field sieve used to factor integers of the form $A^N\pm B$. From an asymptotic point of view, this is faster than older algorithm such as Coppersmith's algorithm and Adleman's original FFS. From a practical viewpoint, we argue that our construction has better properties than the construction of Adleman and Huang. We demonstrate the efficiency of the algorithm by successfully computing discrete logarithms in a large finite Field of characteristic two, namely $GF(2^{521})$.
