Выберите a, c, m в линейном конгруэнтном генераторе

Question

Я ищу для реализации линейного конгруэнтного генератора в Excel.

Как известно, нужно выбрать параметр LCG - это a, c, m и Z0.

Википедия говорит, что

Период общего LCG составляет самое большее m, а для некоторых вариантов множителя намного меньше этого. У LCG будет полный период для всех начальных значений, если и только если:

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, а остальное - случайное. Нет, какие значения имеют указанный период и гарантируют отсутствие коллизий на протяжении этого периода?

Я попытался поставить некоторые значения, а =13, с =911, м =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

Например, в Промежуточном окне вы можете проверить:

?maxperiod(13,911,11584577)
True

так что тебе повезло