The minimal logarithmic signature conjecture states that in any finite simple group there are subsets Ai, 1 ≤ i ≤ s such that the size ∣Ai∣ of each Ai is a prime or 4 and each element of the group has a unique expression as a product i=1sai of elements ai ∈ Ai. Logarithmic signatures have been used in the construction of several cryptographic primitives since the late 1970's [3, 15, 17, 19, 16]. The conjecture is shown to be true for various families of simple groups including cyclic groups, A n, PSLn(q) when gcd(n, q -- 1) is 1, 4 or a prime and several sporadic groups [10, 9, 12, 14, 18]. This dissertation is devoted to proving that the conjecture is true for a large class of simple groups of Lie type called classical groups. The methods developed use the structure of these groups as isometry groups of bilinear or quadratic forms. A large part of the construction is also based on the Bruhat and Levi decompositions of parabolic subgroups of these groups.;In this dissertation the conjecture is shown to be true for the following families of simple groups: the projective special linear groups PSL n(q), the projective symplectic groups PSp2n(q) for all n and q a prime power, and the projective orthogonal groups of positive type W+2n (q) for all n and q an even prime power. During the process, the existence of minimal logarithmic signatures (MLS's) is also proven for the linear groups: GLn (q), PGLn( q), SLn(q), the symplectic groups: Sp2n( q) for all n and q a prime power, and for the orthogonal groups of plus type O+2n (q) for all n and q an even prime power. The constructions in most of these cases provide cyclic MLS's. Using the relationship between finite groups of Lie type and groups with a split BN-pair, it is also shown that every finite group of Lie type can be expressed as a disjoint union of sets, each of which has an MLS.
展开▼
