You are here

the minimal logarithmic signature conjecture

Download pdf | Full Screen View

Date Issued:
2011
Summary:
The minimal logarithmic signature conjecture states that in any finite simple group there are subsets Ai, 1 i s such that the size jAij of each Ai is a prime or 4 and each element of the group has a unique expression as a product Qs i=1 ai of elements ai 2 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, An, 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 PSLn(q), the projective symplectic groups PSp2n(q) for all n and q a prime power, and the projective orthogonal groups of positive type + 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 nite groups of Lie type and groups with a split BN-pair, it is also shown that every nite group of Lie type can be expressed as a disjoint union of sets, each of which has an MLS.
Title: On the minimal logarithmic signature conjecture.
156 views
82 downloads
Name(s): Singhi, Nidhi.
Charles E. Schmidt College of Science
Department of Mathematical Sciences
Type of Resource: text
Genre: Electronic Thesis Or Dissertation
Date Issued: 2011
Publisher: Florida Atlantic University
Physical Form: electronic
Extent: viii, 55 p. : ill. (some col.)
Language(s): English
Summary: The minimal logarithmic signature conjecture states that in any finite simple group there are subsets Ai, 1 i s such that the size jAij of each Ai is a prime or 4 and each element of the group has a unique expression as a product Qs i=1 ai of elements ai 2 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, An, 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 PSLn(q), the projective symplectic groups PSp2n(q) for all n and q a prime power, and the projective orthogonal groups of positive type + 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 nite groups of Lie type and groups with a split BN-pair, it is also shown that every nite group of Lie type can be expressed as a disjoint union of sets, each of which has an MLS.
Identifier: 741264713 (oclc), 3172946 (digitool), FADT3172946 (IID), fau:3670 (fedora)
Note(s): by NIdhi Singhi.
Thesis (Ph.D.)--Florida Atlantic University, 2011.
Includes bibliography.
Electronic reproduction. Boca Raton, Fla., 2011. Mode of access: World Wide Web.
Subject(s): Finite groups
Abelian groups
Number theory
Combinatorial group theory
Mathematical recreations
Linear algebraic groups
Lie groups
Persistent Link to This Record: http://purl.flvc.org/FAU/3172946
Use and Reproduction: http://rightsstatements.org/vocab/InC/1.0/
Host Institution: FAU