کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4945884 | 1439190 | 2018 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Baby-step giant-step algorithms for the symmetric group
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
هوش مصنوعی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We study discrete logarithms in the setting of group actions. Suppose that G is a group that acts on a set S. When r,sâS, a solution gâG to rg=s can be thought of as a kind of logarithm. In this paper, we study the case where G=Sn and develop analogs to Shanks' baby-step / giant-step procedure for ordinary discrete logarithms. Specifically, we compute two sets A,BâSn such that every permutation of Sn can be written as a product ab of elements aâA and bâB. Our deterministic procedure is optimal up to constant factors, in the sense that A and B can be computed in optimal asymptotic complexity, and |A| and |B| are a small constant from n! in size. We also analyze randomized “collision” algorithms for the same problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Symbolic Computation - Volume 85, MarchâApril 2018, Pages 55-71
Journal: Journal of Symbolic Computation - Volume 85, MarchâApril 2018, Pages 55-71
نویسندگان
Eric Bach, Bryce Sandlund,