کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4586690 1334110 2009 25 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A polynomial-time reduction algorithm for groups of semilinear or subfield class
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات اعداد جبر و تئوری
پیش نمایش صفحه اول مقاله
A polynomial-time reduction algorithm for groups of semilinear or subfield class
چکیده انگلیسی

We present a Las Vegas algorithm for finding a nontrivial reduction of groups that are irreducible with m generators and either lie in the subfield class of matrix or projective groups or are semilinear or have non-absolutely irreducible derived group. Let RA denote the cost of producing a random element from a matrix algebra A and R〈HG〉 denote the cost of producing a random element in the normal closure of a group H by a group G. Then the algorithm runs in O(d3(m+dloglogdlogq)+RAlog(logd)+R〈HG〉dlogq) finite field operations. We also characterise the absolutely irreducible groups G over arbitrary fields whose derived group consists only of scalars, and prove probabilistic generation results about matrix groups.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Algebra - Volume 322, Issue 3, 1 August 2009, Pages 613-637