Fast Forward Permutations

Title: Fast Forward Permutations

Research Question: Can we create a permutation that allows for efficient computation of its values, even when given only a few calls to an underlying permutation?

Methodology: The researchers proposed a new method called the "Choose Cycle Lengths" (CCL) process. This process generates a sequence of numbers that represents the lengths of the cycles in a permutation. They then used this process to create a new type of permutation called a "fast forward permutation." This permutation is designed to have its values computed efficiently, even when given only a few calls to the underlying permutation.

Results: The researchers proved that their CCL process generates a sequence of numbers that represents the lengths of the cycles in a permutation, and that this sequence can be used to create a fast forward permutation. They also showed that the expected running time of their CCL process is O(log|Ω|), making it highly efficient.

Implications: The creation of fast forward permutations has several implications. First, it solves an open problem in the field of computer science. Second, it provides a new method for creating permutations with efficient computation times, even when given only a few calls to an underlying permutation. This could have practical applications in various fields, such as cryptography and data processing.

Link to Article: https://arxiv.org/abs/0112016v1 Authors: arXiv ID: 0112016v1