64bit-lcg-crack.cpp

#include <cstdio>
#include <cstdint>
#include <cmath>
#include <algorithm>
#include <chrono>
#include <random>

typedef int64_t s64;
typedef uint64_t u64;
typedef __int128 s128;

const u64 A = 0x5d588b656c078965ll;
const u64 B = 0x269ec3ll;
const s128 M = (s128)1 << 64;
const int BITS = 64;
const int P = 16;

class LCGOperator {
public:
    u64 a, b;
    LCGOperator(u64 aa, u64 bb) : a(aa), b(bb) {}

    LCGOperator o(LCGOperator y) {
        LCGOperator x = *this;
        LCGOperator res(x.a * y.a, x.a * y.b + x.b);
        return res;
    }

    LCGOperator pow(u64 n) {
        LCGOperator x = *this;
        if (n == 0) {
            return LCGOperator(1, 0);
        } else if (n % 2 == 1) {
            return x.o(x).pow(n / 2).o(x);
        } else {
            return x.o(x).pow(n / 2);
        }
    }

    u64 apply(u64 s) {
        return a * s + b;
    }
};

void search(u64 s0, u64 s1, u64 s2, u64 s10, bool check) {
    LCGOperator op0(A, B);
    LCGOperator op = op0.pow(10);
    const u64 xstep = 0x05114191;
    const u64 ystep = (xstep * op.a) % M;

    const s128 xstart = (s128)s0 << (BITS - P);
    const s128 xend = (s128)(s0 + 1) << (BITS - P);
    const s128 ystart = (s128)s10 << (BITS - P);
    const s128 yend = (s128)(s10 + 1) << (BITS - P);
    u64 found_count = 0;

    for (u64 i = 0; i < xstep; i ++) {
        s128 x = xstart + i;
        s128 y = op.apply(x);
        s128 s;

        while (x < xend) {
            while (ystart <= y && y < yend && x < xend) {
                if ((y % M) >> (BITS - P) == s10 && (!check || ((op0.apply(x) >> (BITS - P)) == s1 && (op0.pow(2).apply(x) >> (BITS - P)) == s2))) {
                    if (check) printf("found %016lx\n", (u64)x);
                    found_count ++;
                }
                x += xstep;
                y += ystep;
            }

            s128 ynext = (y >= ystart ? M : 0) + ystart - y;
            s = ynext / ystep + (ynext % ystep != 0 ? 1 : 0);

            y = (y + ystep * s) % M;
            x += xstep * s;
        }
    }
    printf("found_count=%ld\n", found_count);
}

int main() {
    std::mt19937 rnd;
    for (int i = 0; i < 10; i ++) {
        u64 seed = 0(u64)rnd() << 32 | rnd();
        printf("seed=%016lx\n", seed);
        LCGOperator op0(A, B);
        LCGOperator op = op0.pow(10);
        u64 s0 = seed >> (BITS - P);
        u64 s1 = op0.apply(seed) >> (BITS - P);
        u64 s2 = op0.pow(2).apply(seed) >> (BITS - P);
        u64 s10 = op.apply(seed) >> (BITS - P);
        auto start = std::chrono::system_clock::now();
        search(s0, s1, s2, s10, true);
        auto end = std::chrono::system_clock::now();
        printf("time=%ld\n", std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count());
    }
    return 0;
}