### Abstract

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 Z_{G} 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 S_{n}. Random permutations find applications in design of experiments simulation cryptology, voice-encryption etc. Given a logarithmic signature α for s_{n} and a seed s_{0}, we could efficiently compute the following sequence : ᾶ(s_{0}), ᾶ(s_{0} + 1),…,ᾶ(s_{0} + 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 language | English (US) |
---|---|

Title of host publication | Computing in the 1990's - 1st Great Lakes Computer Science Conference, Proceedings |

Editors | Naveed A. Sherwani, Elise de Doncker, John A. Kapenga |

Publisher | Springer Verlag |

Pages | 199-205 |

Number of pages | 7 |

ISBN (Print) | 9780387976280 |

DOIs | |

State | Published - 1991 |

Event | 1st Great Lakes Computer Science Conference, 1989 - Kalamazoo, United States Duration: Oct 18 1989 → Oct 20 1989 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 507 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 1st Great Lakes Computer Science Conference, 1989 |
---|---|

Country | United States |

City | Kalamazoo |

Period | 10/18/89 → 10/20/89 |

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

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

## Cite this

*Computing in the 1990's - 1st Great Lakes Computer Science Conference, Proceedings*(pp. 199-205). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 507 LNCS). Springer Verlag. https://doi.org/10.1007/BFb0038493