已知线性同余的模数为945

Question

已知线性同余的模数为945，怎么取a值和增量c值大最大周期呢

Answer 1

参考一下
a和m互质，即它们的最大公约数为1；
c与m无公因数，即它们的最大公约数为1；
a-1能够被m的所有质因子整除；
如果m是4的倍数，则a-1也必须是4的倍数。

#include <stdio.h>
#include <stdlib.h>

int main() {
    int m = 945; // 模数
    int a = 2; // a值
    int c = 1; // c值
    int max_period = 0; // 最大周期

    for (int i = 2; i < m; i++) { // 遍历a值
        if (m % i == 0 && (i - 1) % 4 == 0) { // 判断是否满足条件3和4
            a = i;
            break;
        }
    }

    for (int i = 1; i < m; i++) { // 遍历c值
        if (m % i != 0) { // 判断是否满足条件2
            c = i;
            break;
        }
    }

    int x = 1; // 初始值
    int period = 0; // 周期

    do { // 计算随机数序列的周期
        x = (a * x + c) % m;
        period++;
    } while (x != 1);

    max_period = m - 1; // 最大周期为m-1

    printf("a=%d, c=%d, max period=%d\n", a, c, max_period);

    return 0;
}