Random permutations from logarithmic signatures

Spyros S. Magliveras, Nasir D. Memon

Research output: Chapter in Book/Report/Conference proceedingConference contribution


A cryptographle system, called PGM, was invented in the late 1970‘s by S. Magiiveras. PGM iS based on the prolific existence of certain kinds of factorizatlon sets, called logarithmic signatures, for finite permutation groups. Logarithmic signatures were initially motivated by C. Sims’ bases and strong generators. A logarithmic signature α, for a given group G, induces a mapping â from ZG to G. Hence it would be natural to use logarithmic signatures for generating random elements in a group. In this paper we focus on generating random permutations in the symmetric group Sn. Random permutations find applications in design of experiments simulation cryptology, voice-encryption etc. Given a logarithmic signature α for sn and a seed s0, we could efficiently compute the following sequence : ᾶ(s0), ᾶ(s0 + 1),…,ᾶ(s0 + r - 1) of r permutations. We claim that this sequence behaves llke a sequence of random permutations. We undertake statistical tests to substantiate our claim.

Original languageEnglish (US)
Title of host publicationComputing in the 1990's - 1st Great Lakes Computer Science Conference, Proceedings
EditorsNaveed A. Sherwani, Elise de Doncker, John A. Kapenga
PublisherSpringer Verlag
Number of pages7
ISBN (Print)9780387976280
StatePublished - 1991
Event1st Great Lakes Computer Science Conference, 1989 - Kalamazoo, United States
Duration: Oct 18 1989Oct 20 1989

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume507 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other1st Great Lakes Computer Science Conference, 1989
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Random permutations from logarithmic signatures'. Together they form a unique fingerprint.

Cite this