Choose a, c, m in Linear Congruential Generator

Question

I am looking to implement a linear congruential generator in Excel.

As we know, we must choose the parameter of LCG is a, c, m, and Z0.

Wikipedia says that

The period of a general LCG is at most m, and for some choices of factor a much less than that. The LCG will have a full period for all seed values if and only if:

m and the offset c are relatively prime,
a - 1 is divisible by all prime factors of m,
a - 1 is divisible by 4 if m is divisible by 4.

Also,

 m, 0 < m  – the "modulus"
 a, 0 < a < m – the "multiplier"
 c, 0 < c < m – the "increment"
 Z0, 0 < Z0 < m – the "seed" or "start value"

I need to choose those values, I want Z0 initial value is 10113383, and the rest is random. Nah, what values that has a specified period and guaranteed no collisions for the duration of that period?

I've tried to put some values, a=13, c=911, m=11584577 and it looks no collisions. But I'm not sure if I break the rules or not.

Answer 1

I regularly teach a number theory and cryptography course so have built up a library of programs in VBA and Python. Using these, I only needed to write one more:

Function GCD(num1 As Long, num2 As Long) As Long
    Dim a As Long
    Dim b As Long
    a = num1
    b = num2
    Dim R As Long
    R = 1
    Do Until R = 0
        R = a Mod b
        a = b
        b = R
    Loop
    GCD = a
End Function

Sub Helper_Factor(ByVal n As Long, ByVal p As Long, factors As Collection)
    'Takes a passed collection and adds to it an array of the form
    '(q,k) where q >= p is the smallest prime divisor of n
    'p is assumed to be odd
    'The function is called in such a way that
    'the first divisor found is automatically prime

    Dim q As Long, k As Long

    q = p
    Do While q <= Sqr(n)
        If n Mod q = 0 Then
            k = 1
            Do While n Mod q ^ k = 0
                k = k + 1
            Loop
            k = k - 1 'went 1 step too far
            factors.Add Array(q, k)
            Helper_Factor n / q ^ k, q + 2, factors
            Exit Sub
        End If
        q = q + 2
    Loop
    'if we get here then n is prime - add it as a factor
    factors.Add Array(n, 1)
End Sub

Function Factor(ByVal n As Long) As Collection
    Dim factors As New Collection
    Dim k As Long

    Do While n Mod 2 ^ k = 0
        k = k + 1
    Loop
    k = k - 1
    If k > 0 Then
        n = n / 2 ^ k
        factors.Add Array(2, k)
    End If
    If n > 1 Then Helper_Factor n, 3, factors
    Set Factor = factors
End Function

Function DisplayFactors(n As Long) As String
    Dim factors As Collection
    Dim i As Long, p As Long, k As Long
    Dim sfactors As Variant

    Set factors = Factor(n)
    ReDim sfactors(1 To factors.Count)
    For i = 1 To factors.Count
        p = factors(i)(0)
        k = factors(i)(1)
        sfactors(i) = p & IIf(k > 1, "^" & k, "")
    Next i
    DisplayFactors = Join(sfactors, "*")
End Function

Function MaxPeriod(a As Long, c As Long, m As Long) As Boolean
    'assumes 0 < a,c < m
    Dim factors As Collection
    Dim p As Long, i As Long

    If GCD(c, m) > 1 Then Exit Function 'with default value of False
    If m Mod 4 = 0 And (a - 1) Mod 4 > 0 Then Exit Function
    'else:
    Set factors = Factor(m)
    For i = 1 To factors.Count
        p = factors(i)(0)
        If p < m And (a - 1) Mod p > 0 Then Exit Function
    Next i
    'if you survive to here:
    MaxPeriod = True
End Function

For example, in the Intermediate Window you can check:

?maxperiod(13,911,11584577)
True

so you seem to be in luck