tailieunhanh - Báo cáo toán học: "Generating random elements in finite groups."

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Generating random elements in finite groups. | Generating random elements in finite groups John D. Dixon School of Mathematics and Statistics Carleton University Ottawa Ontario K2G 0E2 Canada jdixon@ Submitted Aug 8 2006 Accepted Jul 9 2008 Published Jul 21 2008 Mathematics Subject Classification 20P05 20D60 20C05 20-04 68W20 Abstract Let G be a finite group of order g. A probability distribution Z on G is called -uniform if Z x 1 g e g for each x 2 G. If x1 x2 . xm is a list of elements of G then the random cube Zm Cube x1 . xm is the probability distribution where Zm y is proportional to the number of ways in which y can be written as a product x 1 x 2 x m with each i 0 or 1. Let x1 . xd be a list of generators for G and consider a sequence of cubes Wk Cube xp . xf1 x1 . xk where for k d xk is chosen at random from Wk-1. Then we prove that for each Ỗ 0 there is a constant K 0 independent of G such that with probability at least 1 Ỗ the distribution Wm is 1 4-uniform when m d K lg G . This justices a proposed algorithm of Gene Cooperman for constructing random generators for groups. We also consider modifications of this algorithm which may be more suitable in practice. 1 Introduction In 2002 Gene Cooperman posted a manuscript Towards a practical theoretically sound algorithm for random generation in finite groups on arXiv math 4 . He proposed a new algorithm for generating almost random elements of a finite group G in which the cost to set up the generator is proportional to lg2 G where lg denotes the logarithm to base 2 and the average cost to produce each of the successive random elements from the generator is proportional to lg G . The best theoretically justified generator previously known is due to Babai 2 and has a cost proportional to lg5 G . Another widely studied algorithm is the product replacement algorithm 3 see also 9 . Although Pak see 12 has shown that the product replacement algorithm produces almost random elements in time polynomial in lg G there still exists a wide gap .