Skip to content

Generates a not-so-pseudorandom cyclic permutation using modular exponentiation

Notifications You must be signed in to change notification settings

bwesterb/powercycle

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

5 Commits
 
 
 
 
 
 
 
 
 
 

Repository files navigation

powercycle

Go package to generate a (not-so*) pseudo-random cycle.

Example

package main

import (
	"fmt"
	"github.com/bwesterb/powercycle"
)

func main() {
	var x uint64
	cycle := powercycle.New(10)
	for i := 0; i < 10; i++ {
		fmt.Println(x)
		x = cycle.Apply(x)
	}
}

might output

0
6
4
1
2
9
3
5
8
7

Not-so pseudorandom

For efficiency, the cycles generated are of a very particular form. So do not use this package if you want to have a real pseudo-random cycle.

How it works

To generate a cycle of size n, we find a prime p > n + 1 such that furthermore (p - 1)/2 is also a prime. This makes it easy to find a generator g modulo p. The action of the cycle is usually given by

x ---> (((x + 1) * g) % p) - 1

As often p > n + 1, this might yield a number bigger than n. In that case the action is repeated.

About

Generates a not-so-pseudorandom cyclic permutation using modular exponentiation

Topics

Resources

Stars

Watchers

Forks

Packages

No packages published

Languages