64bit-lcg-crack3.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 = 8;

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 sy, u64 sz, u64 sw, u64 s1, u64 s2, u64 s3, u64 s4) {
    LCGOperator op0(A, B);
    LCGOperator opy = op0.pow(640);
    LCGOperator opz = op0.pow(671);
    LCGOperator opw = op0.pow(752);
    const u64 xstep = 0xb52da7e9;
    const u64 ystep = (xstep * opy.a) % M;
    const u64 zstep = (xstep * opz.a) % M;
    const u64 wstep = (xstep * opw.a) % M;

    const s128 xstart = (s128)s0 << (BITS - P);
    const s128 xend = (s128)(s0 + 1) << (BITS - P);
    const s128 ystart = (s128)sy << (BITS - P);
    const s128 yend = (s128)(sy + 1) << (BITS - P);
    const s128 zstart = (s128)sz << (BITS - P);
    const s128 zend = (s128)(sz + 1) << (BITS - P);
    const s128 wstart = (s128)sw << (BITS - P);
    const s128 wend = (s128)(sw + 1) << (BITS - P);
    u64 found_count = 0;

    for (u64 i = 0; i < xstep; i ++) {
        s128 x = xstart + i;
        s128 y = opy.apply(x);
        s128 z = opz.apply(x);
        s128 w = opw.apply(x);

        while (x < xend) {
            while (x < xend && ystart <= y && y < yend && zstart <= z && z < zend && wstart <= w && w < wend) {
                if ((y % M) >> (BITS - P) == sy && (z % M) >> (BITS - P) == sz && (w % M) >> (BITS - P) == sw &&
                    op0.apply(x) >> (BITS - P) == s1 && op0.pow(2).apply(x) >> (BITS - P) == s2 &&
                    op0.pow(3).apply(x) >> (BITS - P) == s3 && op0.pow(4).apply(x) >> (BITS - P) == s4) {
                    printf("found %016lx\n", (u64)x);
                    found_count ++;
                }
                x += xstep;
                y = (y + ystep) % M;
                z = (z + zstep) % M;
                w = (w + wstep) % M;
            }

            s128 ynext = std::max((y >= yend ? M : 0) + ystart - y, (s128)0);
            s128 sy = ynext / ystep + (ynext % ystep ? 1 : 0);
            s128 znext = std::max((z >= zend ? M : 0) + zstart - z, (s128)0);
            s128 sz = znext / zstep + (znext % zstep ? 1 : 0);
            s128 wnext = std::max((w >= wend ? M : 0) + wstart - w, (s128)0);
            s128 sw = wnext / wstep + (wnext % wstep ? 1 : 0);
            //printf("sy = %016lx, sz = %016lx\n", (u64)sy, (u64)sz);
            s128 s = std::max(std::max(sy, sz), sw);

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

int main() {
    std::mt19937 rnd;
    for (int i = 0; i < 10; i ++) {
        u64 seed = (u64)rnd() << 32 | rnd();
        printf("seed=%016lx\n", seed);
        LCGOperator op0(A, B);
        LCGOperator opy = op0.pow(640);
        LCGOperator opz = op0.pow(671);
        LCGOperator opw = op0.pow(752);
        u64 s0 = seed >> (BITS - P);
        u64 s1 = op0.apply(seed) >> (BITS - P);
        u64 s2 = op0.pow(2).apply(seed) >> (BITS - P);
        u64 s3 = op0.pow(3).apply(seed) >> (BITS - P);
        u64 s4 = op0.pow(4).apply(seed) >> (BITS - P);
        u64 sy = opy.apply(seed) >> (BITS - P);
        u64 sz = opz.apply(seed) >> (BITS - P); 
        u64 sw = opw.apply(seed) >> (BITS - P); 
        auto start = std::chrono::system_clock::now();
        search(s0, sy, sz, sw, s1, s2, s3, s4);
        auto end = std::chrono::system_clock::now();
        printf("time=%ld\n", std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count());
    }
    return 0;
}