在线性同余生成器中选择 a, c, m

Question

我希望在 Excel 中实现线性同余生成器。

我们知道，必须选择LCG的参数是a,c,m,Z0

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.

此外，

 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"

我需要选择那些值，我希望Z0初始值为10113383，其余随机。不，什么值具有指定的时间段并保证在该时间段内不会发生冲突？

我尝试输入一些值，a=13、c=911、m=11584577，看起来没有冲突。但是我不确定我是否违反了规则。

Answer 1

我经常教授数论和密码学课程，因此在 VBA 和 Python 中建立了一个程序库。使用这些，我只需要再写一个：

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

例如，在中级 Window 你可以检查：

?maxperiod(13,911,11584577)
True

看来你运气不错

在线性同余生成器中选择 a, c, m

Choose a, c, m in Linear Congruential Generator

random

math

excel

vba

lcg