将数字存储为“随机”种子

Question

是否可以从给定的数字列表计算种子，以便该种子将导致数字生成函数（如

rand()

）输出该数字列表？

并且，在什么时候根本不可能找到这样的种子（例如，如果输入列表变得太大）？

当然，不一定是

rand()

。任何生成函数都可以，并且在计算时就已知。

例如：

int seed;
int myRand() // RAND_MAX assumed to be 32767
{
    seed = seed*1103515245 + 12345;
    return (seed/65536) % 32768;
}

// given numbers: 19098, -31546, 32637, 21910, -27300
// use black magic maths to find seed 75235

int main() {
    
    seed = 75235;
    
    printf("%d\n", myRand()); // 19098
    printf("%d\n", myRand()); // -31546
    printf("%d\n", myRand()); // 32637
    printf("%d\n", myRand()); // 21910
    printf("%d\n", myRand()); // -27300

    return 0;
}

谢谢！

Answer 1

对于线性同余生成器，我相信 rand() 是典型的实现，它相当简单。知道参数后，您可以计算模逆并反转公式。不知道您的平台，这是简单的例子

#include <stdint.h>
#include <stdio.h>

uint64_t m = 0xd1342543de82ef95ULL; // parameters from https://arxiv.org/pdf/2001.05304.pdf
uint64_t c = 0x1ULL;

uint64_t im = 6281218453581128637ULL; // modular inverse from m using Mathematica ModularInverse[m, 2^64]

uint64_t lcg(uint64_t xi) { // direct LCG
    return m*xi + c;
}

 uint64_t ilcg(uint64_t xp) { // inverse LCG, such that ilcq(lcg(q)) == q
    return (xp - c)*im;
}

int main() {
    
    uint64_t idx = 987610342345234534ULL;
    
    printf( "LCG is %llu\n", lcg(idx) );
    printf( "INV is %llu\n", ilcg(lcg(135797531ULL)) );

    return 0;
}

如果您不知道 rand() 是如何实现的，但仍然确定这是 LCG，那么这会更复杂，请参阅此处查看示例