Constructing Small Generating Sets for the Multiplicative Groups of Algebras over Finite Fields

被引：3

作者：

Huang, Ming-Deh ^{[1
]}

Liu, Lian ^{[1
]}

机构：

[1] Univ Southern Calif, Dept Comp Sci, Los Angeles, CA 90089 USA

来源：

PROCEEDINGS OF THE 2016 ACM INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION (ISSAC 2016) | 2016年

关键词：

computational algebra; generating sets; character sums; expander graphs; CAYLEY-GRAPHS; POLYNOMIALS; ELEMENTS;

D O I：

10.1145/2930889.2930921

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 F-p[x]/F, where p is a prime number and F is an element of F-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.

引用

页码：287 / 294

页数：8

共 19 条

[1] Function field sieve method for discrete logarithms over finite fields [J].

Adleman, LM ;

Huang, MDA .

INFORMATION AND COMPUTATION, 1999, 151 (1-2) :5-16

[2]

[Anonymous], 2013095 CRYPT EPRINT

[3] On primitive elements in finite fields of low characteristic [J].

Bhowmick, Abhishek ;

Le, Thai Hoang .

FINITE FIELDS AND THEIR APPLICATIONS, 2015, 35 :64-77

[4]

Chung F., 1992, Spectral Graph Theory

[5] SEVERAL GENERALIZATIONS OF WEIL SUMS [J].

CHUNG, FRK .

JOURNAL OF NUMBER THEORY, 1994, 49 (01) :95-106

[6]

Chung FRK., 1989, J AM MATH SOC, V2, P187, DOI [DOI 10.1090/S0894-0347-1989-0965008-X, DOI 10.2307/1990973.MR965008]

[7]

Developers T. S., 2016, SAG MATH SOFTW VERS

[8]

Göloglu F, 2013, LECT NOTES COMPUT SC, V8043, P109, DOI 10.1007/978-3-642-40084-1_7

[9] Expander graphs and their applications [J].

Hoory, Shlomo ;

Linial, Nathan ;

Wigderson, Avi .

BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 2006, 43 (04) :439-561

[10]

Huang M., 2013, ABS13041206 CORR

← 1 2 →