Edit on GitHub

Home

See here and here for an explanation of the functions in this package.

Randomness is very hard for a computer to get right. This is why there are many tools to produce what we call pseudo-random generators (from which pseudo-random strings and -numbers come). These look random; you would expect them to be somehow "patternless". But how would you test if these are random?

Kolmogorov proposed the following definition of a random string:

A sequence is random if it cannot be generated by an algorithm with a description much shorter than the sequence itself.

Obviously the sequence of all 1’s is not random according to the above definition, nor are the first n digits of π. In fact, it is very hard to describe a random string in Kolmogorov’s sense. An alternative is to try to generate a sequence that has some desirable features of a random string. Such sequences are often called pseudo-random sequences. What we would like is to be able to generate a sequence that could be used like a one-time pad without the inconvenience of having to store the whole sequence.

There are many different techniques to create pseudo-random generators. This repository gives just a couple of those methods, in a nice little package.

Contents

Adding LinearShiftRegisters.jl

julia> using Pkg

julia> Pkg.add("LinearShiftRegisters")
   Updating registry at `~/.julia/registries/General`
  Resolving package versions...
ERROR: expected package `LinearShiftRegisters [b377b9e1]` to be registered

Documentation

Main.LinearShiftRegisters.LCG_period — Method
LCG_period(m::Integer, a::Integer, b::Integer, x0::Integer) -> String

Given m, a, b, and x0, finds the period generated by these parameters from a Linear Congruential Generator, and returns this sequence as a string.

Note

As this method looks for recurring sequences, it is possible that this function does not terminate—or maybe it does terminate, but I haven't waited long enough to find out.

Description

Choose m, a positive integer. Choose a, b (mod m) integers.

The Linear Congruential Generator is given to us by

\[x_1 \equiv ax_0+b\mod m\\ x_2 \equiv ax_1+b\mod m\\ \vdots\\ x_{n + 1} \equiv ax_n + b \mod m\\ \vdots\]

Eventually, $x_n = x_i$ for some $n$, $i$ (let's suppose $n>i$ and $i$ is not necessarily $0$). Then, clearly,

\[x_{n+1} = x_{i+1},\ldots.\]

So

\[x_i, x_{i+1},\dots, x_{n-1}\]

Will be repeated forever.

From a cryptography point of view, LCG is too vulnerable (although all pseudorandom number generators are vulnerable), but it is still useful for other perposes that require pseudorandom numbers.

For essentially a more sophisticated version of LCG in the sense that it is based on recurring linear relations, see LSR_period.

Examples

julia> println(LinearShiftRegisters._LCG_period(9, 5, 2, 0))
[0, 2, 3, 8, 6, 5]

julia> LCG_period(9, 5, 2, 0)
"023865"
source
Main.LinearShiftRegisters.LSR_period — Method
LSR_period(const_str::AbstractVector{T}, init_str::AbstractVector{R}) where {T, R <: Integer} -> AbstractVector
LSR_period(const_str::AbstractString, init_str::AbstractString) -> String

Given a starting binary string (init_str) and a constant mutating string (const_str), LSR_period will find the repeating sequence generated from these.

Note

As this method looks for recurring sequences, it is possible that this function does not terminate—or maybe it does terminate, but I haven't waited long enough to find out.

Description

A (linear) shift register with feedback is an arrangement of registers in a row, each register being capable of holding either the digit 1 (on) or 0 (off). Suppose the system has $n$ registers, $R_1,\ldots,R_n$, and $X_i(t)$ denotes the content of register $R_i$ at time $t$. Initially, let the system be given

Given

Examples

julia> LSR_period("1001", "0100")
"001000111101011"

julia> LSR_period("1001", "0101")
"101011001000111"
source

Index