Cited By
View all- Rasri AMeemark Y(2017)Algebraic Cayley graphs over finite local ringsFinite Fields and Their Applications10.1016/j.ffa.2017.08.00248:C(227-240)Online publication date: 1-Nov-2017
Constructing Small Generating Sets for the Multiplicative Groups of Algebras over Finite Fields
Authors: 
Ming-Deh Huang, Lian LiuAuthors Info & Claims
Abstract
We consider computational problems concerning algebras over finite fields. In particular, we propose an algorithm for finding a small generating set for the multiplicative group of GF(p)[x]/F, where p is a prime number and F in GF(p)[x] is an arbitrary polynomial. Based on this result, a new set of expander graphs can be explicitly constructed. In addition, we present algorithms for basis construction and decomposition of a given element with respect to the basis.
References
[1]
Finite field morphisms. http://doc.sagemath.org/html/en/reference/finite_rings/sage/rings/finite_rings/hom_finite_field.html.
[2]
L. M. Adleman and M.-D. A. Huang. Function field sieve method for discrete logarithms over finite fields. Information and Computation, 151(1--2):5--16, 1999.
[3]
A. Bhowmick and T. H. Lê. On primitive elements in finite fields of low characteristic. Finite Fields and Their Applications, 35:64 -- 77, 2015.
[4]
F. R. K. Chung. Diameters and eigenvalues. American Mathematical Society, 2(2):187--196, 1989.
[5]
F. R. K. Chung. Several generalizations of weil sums. J. Number Theory, 49:95--106, 1994.
[6]
F. R. K. Chung. Spectral Graph Theory. American Mathematical Society, 1997.
[7]
T. S. Developers. Sage Mathematics Software (Version 7.1), 2016. http://www.sagemath.org.
[8]
F. Gölouglu, R. Granger, G. McGuire, and J. Zumbragel. Advances in Cryptology -- CRYPTO 2013: 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18--22, 2013. Proceedings, Part II, pages 109--128. Springer Berlin Heidelberg, Berlin, Heidelberg, 2013.
[9]
S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications. BULL. AMER. MATH. SOC., 43(4):439--561, 2006.
[10]
M. Huang and A. K. Narayanan. Finding primitive elements in finite fields of small characteristic. CoRR, abs/1304.1206, 2013.
[11]
A. Joux. A new index calculus algorithm with complexity l(1/4+o(1)) in very small characteristic. Cryptology ePrint Archive, Report 2013/095, 2013.
[12]
N. M. Katz. An estimate for character sums. Journal of the American Mathematical Society, 2(2):pp. 197--200, 1989.
[13]
M. Lu, D. Wan, L.-P. Wang, and X.-D. Zhang. Algebraic cayley graphs over finite fields. Finite Fields and Their Applications, 28:43 -- 56, 2014.
[14]
G. L. Mullen and D. Panario. Handbook of Finite Fields. Chapman & Hall/CRC, 1st edition, 2013.
[15]
R. Popovych. Elements of high order in finite fields of the form. Finite Fields and Their Applications, 19(1):86--92, 2013.
[16]
V. Shoup. Searching for primitive roots in finite fields. Mathematics of Computation, 58(197):369--380, 1992.
[17]
I. E. Shparlinski. Cayley graphs generated by small degree polynomials over finite fields. SIAM Journal on Discrete Mathematics, 29(1):376--381, 2015.
[18]
J. von zur Gathen and I. Shparlinski. Orders of gauss periods in finite fields. Applicable Algebra in Engineering, Communication and Computing, 9(1):15--24.
[19]
D. Wan. Generators and irreducible polynomials over finite fields. Mathematics of Computation, 66:1195--1212, 1997.
[20]
A. Weil. Basic number theory. Grundlehren der mathematischen Wissenschaften. Springer-Verlag, 1974.
Index Terms
- Constructing Small Generating Sets for the Multiplicative Groups of Algebras over Finite Fields
Recommendations
Algebraic Cayley graphs over finite fields
A new algebraic Cayley graph is constructed using finite fields. It provides a more flexible source of expander graphs. Its connectedness, the number of connected components, and diameter bound are studied via Weil's estimate for character sums. ...
On pseudorandom sequences of $$k$$k symbols constructed using finite fields
A family of pseudorandom sequences of $$k$$ k symbols are constructed by using finite fields of prime-power order. The construction is an extension of certain construction of Sárközy and Winterhof on binary sequences using the quadratic character with ...
Additive Decompositions of Subgroups of Finite Fields
We say that a set ${\mathcal S}$ is additively decomposed into two sets ${\mathcal A}$ and ${\mathcal B}$ if ${\mathcal S} = \{a+b:a\in {\mathcal A}, b \in {\mathcal B}\}$. Here we study additive decompositions of multiplicative subgroups of finite fields. ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2016
434 pages
ISBN:9781450343800
DOI:10.1145/2930889
- General Chairs:
- Sergei Abramov,
- Eugene Zima,
- Program Chair:
- Xiao-Shan Gao
Copyright © 2016 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 20 July 2016
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
ISSAC '16
Sponsor:
ISSAC '16: International Symposium on Symbolic and Algebraic Computation
July 20 - 22, 2016
ON, Waterloo, Canada
Acceptance Rates
Overall Acceptance Rate 395 of 838 submissions, 47%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 60Total Downloads
- Downloads (Last 12 months)3
- Downloads (Last 6 weeks)0
Reflects downloads up to 14 Feb 2025
Other Metrics
Citations
Cited By
View all- Rasri AMeemark Y(2017)Algebraic Cayley graphs over finite local ringsFinite Fields and Their Applications10.1016/j.ffa.2017.08.00248:C(227-240)Online publication date: 1-Nov-2017
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in