Topic: Bitcoin puzzle transaction ~32 BTC prize to who solves it - page 67. (Read 230409 times)

import math, os, sys, time


class S:            # Scalar field
    N = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

    @staticmethod
    def add(a, b):
        return (a + b) % S.N


class F:        # Curve field
    P = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f

    @staticmethod
    def add(a, b):
        return (a + b) % F.P

    @staticmethod
    def mul(a, b):
        return (a * b) % F.P

    @staticmethod
    def pow(b, e):
        return pow(b, e, F.P)

    @staticmethod
    def sqrt(a):
        return F.pow(a, (F.P + 1) // 4)

    @staticmethod
    def inv(a):
        if a == 0:
            return 0

        r = 1
        s = 0
        low = a % F.P
        high = F.P

        while low > 1:
            q = high // low
            nm = s - q * r
            nw = high - low * q
            high = low
            s = r
            low = nw
            r = nm

        return r % F.P


class Point:            # Affine point
    def __init__(self, x, y, parity=-1):
        self.x = x
        self.y = y if parity == -1 else Point.calc_y(x, parity)

    @classmethod
    def uncompress(cls, s):
        parity, xh = int(s[:2], 16), s[2:]
        if parity not in [2, 3]:
            raise Exception("Expected parity 02 or 03")
        return Point(int(xh, 16), 0, parity % 2)

    @staticmethod
    def calc_y(x, parity):
        y = F.sqrt(F.add(F.pow(x, 3), 7))   # y = sqrt(x**3 + 7)
        return y if parity == y % 2 else F.P - y


class JPoint:           # Jacobian point
    def __init__(self, x, y, z):
        self.x = x
        self.y = y
        self.z = z

    def affine(self):
        z = F.inv(self.z)
        z2 = F.mul(z, z)
        return Point(F.mul(self.x, z2), F.mul(self.y, F.mul(z, z2)))

    def mul(self, n):
        if self.y == 0 or n == 0:
            return JPoint(0, 0, 1)

        if n == 1:
            return self

        if n < 0 or n >= S.N:
            return self.mul(n % S.N)

        if (n % 2) == 0:
            return self.mul(n // 2).double()

        return self.mul(n // 2).double().add(self)

    def double(self):
        if self.y == 0:
            return JPoint(0, 0, 0)

        y2 = F.mul(self.y, self.y)
        s = F.mul(4 * self.x, y2)
        M = F.mul(3 * self.x, self.x)

        x = F.add(F.mul(M, M), - 2 * s)
        return JPoint(x, F.add(F.mul(M, s - x), -F.mul(8 * y2, y2)), F.mul(2 * self.y, self.z))

    def add(self, q):
        if self.y == 0:
            return q
        if q.y == 0:
            return self

        qz2 = F.mul(q.z, q.z)
        pz2 = F.mul(self.z, self.z)
        U1 = F.mul(self.x, qz2)
        U2 = F.mul(q.x, pz2)
        S1 = F.mul(self.y, F.mul(q.z, qz2))
        S2 = F.mul(q.y, F.mul(self.z, pz2))

        if U1 == U2:
            if S1 != S2:
                return JPoint(0, 0, 1)
            return self.double()

        H = F.add(U2, -U1)
        R = F.add(S2, -S1)
        H2 = F.mul(H, H)
        H3 = F.mul(H, H2)
        U1H2 = F.mul(U1, H2)
        nx = F.add(F.mul(R, R), -F.add(H3, 2 * U1H2))
        ny = F.add(F.mul(R, F.add(U1H2, -nx)), -F.mul(S1, H3))
        nz = F.mul(H * self.z, q.z)

        return JPoint(nx, ny, nz)


class Group:
    G = Point(
        0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,
        0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
    )

    @staticmethod
    def add(p, q):
        m = F.mul(F.add(p.y, -q.y), F.inv(F.add(p.x, -q.x)))
        x = F.add(F.add(F.mul(m, m), -p.x), -q.x)
        return Point(x, F.add(F.mul(m, F.add(q.x, -x)), -q.y))

    @classmethod
    def mul(cls, p, k):
        # [k]P point scalar multiplication
        return JPoint(p.x, p.y, 1).mul(k).affine()

    @classmethod
    def batch_add(cls, ga, gb):
        n = len(ga)
        d = [0] * n
        p = [0] * n
        z = 1
        for i in range(n):
            d[i] = F.add(ga[i].x, -gb[i].x)
            z = F.mul(z, d[i])
            p[i] = z

        t = F.inv(z)

        for i in range(n - 1, -1, -1):
            if i > 0:
                xi = F.mul(t, p[i - 1])
                t = F.mul(t, d[i])
            else:
                xi = t

            m = F.mul(F.add(ga[i].y, -gb[i].y), xi)
            ga[i].x = F.add(F.add(F.mul(m, m), -ga[i].x), -gb[i].x)
            ga[i].y = F.add(F.mul(m, F.add(gb[i].x, -ga[i].x)), -gb[i].y)


class TrueRandom:
    def __init__(self, max_value: int, num_bits: int, min_value: int = 0):
        self.upper_bound = max_value - min_value + 1
        self.min = min_value
        self.num_bits = num_bits
        self.domain = 2 ** num_bits
        self.num_bytes = math.ceil(num_bits / 8)
        self.shift = 8 * self.num_bytes - num_bits

    def get_next(self):
        random_bytes = os.urandom(self.num_bytes)

        # trim to num_bits
        random_int = int.from_bytes(random_bytes, byteorder='big') >> self.shift

        # normalize from domain range to target range
        sample = self.upper_bound * random_int // self.domain

        return sample + self.min


def kangaroo_with_results(k1, k2, P, dp, herd_size):
    k_cand, counter, tbl_size = kangaroo(k1, k2, P, dp, herd_size=herd_size)

    k = k_cand[0]
    if k1 <= k <= k2:
        P_check = Group.mul(Group.G, k)
        if P_check.x == P.x:
            print(f'Key: {hex(k)}\nGroup ops: {counter}')

    return k_cand, counter, tbl_size


def create_kangaroo(kang_type, pos: int, herd_pts, herd_distances, k1, k2, P, rnd: TrueRandom, v):
    if kang_type == 0:
        # d = rnd.get_next()                    # [0, k2 - k1)
        d = (k2 - k1 + 1) + pos * v        # b/2 + i*v
        # d = (k2 - k1 + 1) // 2
        herd_distances[pos] = d
        herd_pts[pos] = Group.mul(Group.G, k1 + d)
    else:
        # d = rnd.get_next() - (k2 - k1 + 1) // 2               # [-(k2-k1)/2, (k2-k1)/2]
        d = (k2 - k1 + 1) // 2 + pos * v                             # b + i*v
        # d = 0
        herd_distances[pos] = d
        herd_pts[pos] = Group.add(P, Group.mul(Group.G, d))


def check_col(kang_type, hashmap, herd, dist, pos, k1, k2, P, dp_mask, R, v_rnd,
              respawn_dead=True,
              stop_at_dp=True):
    x = herd[pos].x

    if x & dp_mask == 0:
        item = hashmap.get(x)

        if item is not None:
            if item[0] == kang_type ^ 1:
                # collision
                d_wild, d_tame = (item[1], dist[pos]) if kang_type == 0 else (dist[pos], item[1])
                return [S.add(k1 + d_tame, - d_wild)], 0
            else:
                # print(f'Dead kangaroo at {pos}')
                if respawn_dead:
                    # create_kangaroo(kang_type, pos, herd, dist, k1, k2, P, R)
                    # move along with a small random value
                    d = v_rnd.get_next()
                    dist[pos] += d
                    herd[pos] = Group.add(herd[pos], Group.mul(Group.G, d))

                    # this will recurse until a non-dead kangaroo is produced
                    k, created = check_col(kang_type, hashmap, herd, dist, pos, k1, k2, P, dp_mask, R, v_rnd)
                    return k, 1 + created
        else:
            hashmap[x] = (kang_type, dist[pos])

    return 0, 0


def build_jump_distances(alpha, with_points=False):
    jump_points = []
    jump_distances = []

    # compute A (jump distances) such that average(A) is closest to expected alpha
    # Pollard says choosing A as powers of two feels like "needs more investigation"
    min_diff = 1
    while True:
        jump_distance = 2 ** len(jump_distances)
        jump_distances.append(jump_distance)
        if with_points:
            jump_points.append(Group.mul(Group.G, jump_distance))

        alpha_real = sum(jump_distances) / len(jump_distances)
        diff = abs(1 - alpha_real / alpha)
        if alpha_real >= alpha:
            if diff > min_diff:
                jump_distances.pop()
            break
        if diff < min_diff:
            min_diff = diff

    return jump_distances, jump_points


def kangaroo(k1, k2, P, dp: int, herd_size: int = 128):
    b = k2 - k1 + 1                                                 # size of search interval
    m = herd_size + herd_size                                       # m/2 + m/2
    # parallel case - minimize alpha for total number of jumps
    alpha = m * math.sqrt(b) / 4                                    # m * sqrt(b) / 4

    jump_distances, jump_points = build_jump_distances(alpha, with_points=True)
    alpha_real = sum(jump_distances) / len(jump_distances)

    n = len(jump_distances)

    # adjust alpha to the actual average jump distance
    alpha_expected = alpha
    alpha = alpha_real

    # expected total number of jumps for each trailing kangaroo (1 per processor)
    expected_trailing_jumps = 2 * math.sqrt(b) / m                  # 2 * sqrt(b) / m

    # beta = 0.553                      # serial case
    # ab_jumps = int(alpha * beta)      # serial case
    # max_tame_distance = int(alpha * alpha * beta + b // 2)

    # expected number of jumps done by a trailing kangaroo after it enters the [b, ...] region
    # this would equal the number of jumps done by a tame kangaroo that starts from b
    num_tame_jumps = 4 * alpha / (m * m)                        # 4 * alpha / (m**2)
    max_tame_distance = int(alpha * num_tame_jumps + b)         # average jump size * num jumps + start
    # max_wild_distance = int(alpha * num_tame_jumps + b/2)       # average jump size * num jumps + start
    # = (2*a/m)**2 = (sqrt(b) / 2)**2

    # set v to the "partition" size for a processor, and not a power of two
    v = b // m - 1                          # (b/2) / (m/2)
    # v = herd_size
    v_rnd = TrueRandom(v, 256)

    hashmap = {}
    wilds: list = [None] * herd_size
    tames: list = [None] * herd_size
    w_dist = [0] * herd_size
    t_dist = [0] * herd_size
    counter = 0
    done_ab_jumps = 0

    expected_total_jumps = math.ceil((num_tame_jumps + expected_trailing_jumps) * herd_size)
    print(
        f'processors: {m}'
        f'\n         num jump distances: {n}'
        f'\nmax jumps per tame kangaroo: {math.ceil(num_tame_jumps)}'
        f'\nmax jumps per wild kangaroo: {math.ceil(expected_trailing_jumps)}'
        f'\n       expected total jumps: {expected_total_jumps} {math.log2(expected_total_jumps):.2f} bits'
        f'\n     avg real jump distance: {round(alpha_real)} {math.log2(alpha_real):.2f} bits'
        f'\n avg expected jump distance: {round(alpha_expected)} {math.log2(alpha_expected):.2f} bits'
        f'\n expected max tame distance: {max_tame_distance} {math.log2(max_tame_distance):.2f} bits'
        # f'\n expected max wild distance: {max_wild_distance} {math.log2(max_wild_distance):.2f} bits'
    )

    R = TrueRandom(k2 - k1, 256, 0)
    dp_mask = (1 << dp) - 1

    for idx in range(herd_size):
        create_kangaroo(0, idx, tames, t_dist, k1, k2, P, R, v)
        counter += 1

        k, born = check_col(0, hashmap, tames, t_dist, idx, k1, k2, P, dp_mask, R, v_rnd)
        counter += born
        if k:
            return k, counter, len(hashmap)

        create_kangaroo(1, idx, wilds, w_dist, k1, k2, P, R, v)
        counter += 1

        k, born = check_col(1, hashmap, wilds, w_dist, idx, k1, k2, P, dp_mask, R, v_rnd)
        counter += born
        if k:
            return k, counter, len(hashmap)

    batch_jp: list = [None] * herd_size

    start_time = time.time()
    last_p_time = 0
    while True:
        if done_ab_jumps < num_tame_jumps:
            # jump tames
            for idx in range(herd_size):
                d = tames[idx].x % n
                # tames[idx] = Group.add(tames[idx], jump_points[d])        # un-batched addition
                batch_jp[idx] = jump_points[d]
                t_dist[idx] += jump_distances[d]

            Group.batch_add(tames, batch_jp)

            for idx in range(herd_size):
                counter += 1

                k, born = check_col(0, hashmap, tames, t_dist, idx, k1, k2, P, dp_mask, R, v_rnd)
                counter += born
                if k:
                    return k, counter, len(hashmap)

            done_ab_jumps += 1
            if done_ab_jumps >= num_tame_jumps:
                # new_max = max(t_dist)
                # avg_dist = sum(t_dist) / len(t_dist)
                # print(
                #     f'Tames are done.'
                #     f'\nExpected max tame distance: {max_tame_distance} {math.log2(max_tame_distance):.2f} bits'
                #     f'\nAverage max tame distance:  {avg_dist}  {math.log2(avg_dist):.2f} bits'
                #     f'\nActual max tame distance:   {new_max}  {math.log2(new_max):.2f} bits'
                # )
                # max_tame_distance = max(max_tame_distance, new_max)
                # max_wild_distance = int(max_tame_distance + b / 2)      # add initial tame - wild gap

                # create new tames herd
                for idx in range(herd_size):
                    d = b + idx * v + v_rnd.get_next()    # b/2 + i*v + z

                    t_dist[idx] = d
                    tames[idx] = Group.mul(Group.G, k1 + d)
                    counter += 1

                done_ab_jumps = 0

        for idx in range(herd_size):
            d = wilds[idx].x % n
            # wilds[idx] = Group.add(wilds[idx], jump_points[d])    # unbatched addition
            batch_jp[idx] = jump_points[d]
            w_dist[idx] += jump_distances[d]

        Group.batch_add(wilds, batch_jp)

        for idx in range(herd_size):
            counter += 1

            k, born = check_col(1, hashmap, wilds, w_dist, idx, k1, k2, P, dp_mask, R, v_rnd)
            counter += born
            if k:
                return k, counter, len(hashmap)

            if w_dist[idx] > max_tame_distance:
                # create_kangaroo(1, idx, wilds, w_dist, k1, k2, P, R)
                z = v_rnd.get_next()
                d = b // 2 + idx * v + z        # b + i*v + z

                w_dist[idx] = d
                wilds[idx] = Group.add(P, Group.mul(Group.G, d))

                counter += 1

        total_time = time.time() - start_time
        if total_time - last_p_time > 3:
            last_p_time = total_time
            print(f'Ops: {counter} Table size: {len(hashmap)} Speed: {counter / total_time:.0f} ops/s')


def run_puzzle(idx: int, pub_key, dp: int = 0, herd_size: int = 128, benchmark=0):
    # puzzle #X has (X - 1) unknown bits
    k1 = 1 << (idx - 1)
    k2 = (k1 << 1) - 1

    # subtract k1 to search in a [0, k2 - k1) interval
    k2 -= k1
    k1 = 0

    P = Point.uncompress(pub_key)

    # subtract (k2 - k1)G from P to bring target point's k to [0, k2 - k1) interval
    P = Group.add(P, Group.mul(Group.G, -(k2 + 1)))

    now = time.time()
    _, ops, hashmap_size = kangaroo_with_results(k1, k2, P, dp, herd_size)
    total_time = time.time() - now
    print(f'Ops: {ops} Stored: {hashmap_size}')
    print(f'Speed: {ops / total_time:.0f} ops/s')


if __name__ == '__main__':
    # r, p = int(sys.argv[1]), sys.argv[2]
    # run_puzzle(r, p, dp=0, herd_size=128)

    # run_puzzle(32, '0209c58240e50e3ba3f833c82655e8725c037a2294e14cf5d73a5df8d56159de69',
    #            herd_size=512)

    run_puzzle(48, '0291bee5cf4b14c291c650732faa166040e4c18a14731f9a930c1e87d3ec12debb',
               dp=8, herd_size=1024)

processors: 2048
         num jump distances: 38
max jumps per tame kangaroo: 6899
max jumps per wild kangaroo: 11586
       expected total jumps: 18927375 24.17 bits
     avg real jump distance: 7233629130 32.75 bits
 avg expected jump distance: 6074001000 32.50 bits
 expected max tame distance: 190638869267657 47.44 bits
...
Ops: 17607859 Table size: 68719 Speed: 225400 ops/s
Key: 0x2de6d7ce3b9b
Group ops: 18288933
Ops: 18288933 Stored: 71317
Speed: 222616 ops/s

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;

typedef array Point;

const mpz_class modulo("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", 16);
const mpz_class Gx("79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", 16);
const mpz_class Gy("483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8", 16);
const Point PG = {Gx, Gy};
const Point Z = {0, 0};

auto starttime = chrono::high_resolution_clock::now();

Point add(const Point& P, const Point& Q, const mpz_class& p = modulo) {
    if (P == Z) return Q;
    if (Q == Z) return P;
    const mpz_class& P0 = P[0];
    const mpz_class& P1 = P[1];
    const mpz_class& Q0 = Q[0];
    const mpz_class& Q1 = Q[1];
    mpz_class lmbda, num, denom, inv;
    if (P != Q) {
        num = Q1 - P1;
        denom = Q0 - P0;
    } else {
        if (P1 == 0) return Z;
        num = 3 * P0 * P0;
        denom = 2 * P1;
    }
    mpz_invert(inv.get_mpz_t(), denom.get_mpz_t(), p.get_mpz_t());
    lmbda = (num * inv) % p;
    mpz_class x = (lmbda * lmbda - P0 - Q0) % p;
    if (x < 0) x += p;
    mpz_class y = (lmbda * (P0 - x) - P1) % p;
    if (y < 0) y += p;
    return {x, y};
}

Point mul(const mpz_class& k, const Point& P = PG, const mpz_class& p = modulo) {
    Point R = Z;
    Point current = P;
    mpz_class k_copy = k;
    while (k_copy > 0) {
        if (k_copy % 2 == 1) {
            R = add(R, current, p);
        }
        current = add(current, current, p);
        k_copy >>= 1;
    }
    return R;
}

mpz_class X2Y(const mpz_class& X, int y_parity, const mpz_class& p = modulo) {
    mpz_class X_cubed = (X * X * X) % p;
    mpz_class tmp = (X_cubed + mpz_class(7)) % p;
    mpz_class Y;
    mpz_class exp = (p + mpz_class(1)) / mpz_class(4);
    mpz_powm(Y.get_mpz_t(), tmp.get_mpz_t(), exp.get_mpz_t(), p.get_mpz_t());
    if ((Y % 2) != y_parity) {
        Y = p - Y;
    }
    return Y;
}

bool comparator(const Point& P, const mpz_class& Pindex, const mpz_class& DP_rarity,
                std::vector& T, std::vector& t, const std::vector& W,
                const std::vector& w) {
    mpz_class result;
    mpz_fdiv_r(result.get_mpz_t(), P[0].get_mpz_t(), DP_rarity.get_mpz_t());
  
    if (result != 0) return false;

    T.push_back(P);
    t.push_back(Pindex);

    // Create a set of Points from T for fast lookup
    std::set T_set(T.begin(), T.end());

    // Create a set of Points from W for quick existence check
    std::set W_set(W.begin(), W.end());

    // Iterate through W and check if each element is in T
    for (const auto& match : W_set) {
        if (T_set.find(match) != T_set.end()) {
            auto it = find(T.begin(), T.end(), match);
            int index = distance(T.begin(), it);
            mpz_class tP = t[index];
            mpz_class wP = w[distance(W.begin(), find(W.begin(), W.end(), match))];
            mpz_class dec = abs(tP - wP);

            // Measure time once and reuse it
            auto end = chrono::system_clock::now();
            time_t end_time = chrono::system_clock::to_time_t(end);
            cout << "\n\033[01;33m[+]\033[32m PUZZLE SOLVED: \033[32m" << ctime(&end_time) << "\r";
            cout << "\r\033[01;33m[+]\033[32m Private key (dec): \033[32m" << dec << "\033[0m" << endl;

            // Open file once, write all data, and close it
            static std::ofstream file("KEYFOUNDKEYFOUND.txt", std::ios::app);
            file << "\n" << string(140, '-') << endl;
            file << "SOLVED " << ctime(&end_time);
            file << "Private Key (decimal): " << dec << endl;
            file << "Private Key (hex): " << dec.get_str(16) << endl;
            file << string(140, '-') << endl;

            return true;
        }
    }

    return false;
}


vector generate_powers_of_two(int hop_modulo) {
    vector powers(hop_modulo);
    for (int pw = 0; pw < hop_modulo; ++pw) {
        powers[pw] = mpz_class(1) << pw;
    }
    return powers;
}

string search(const vector& P, const Point& W0, const mpz_class& DP_rarity, int Nw, int Nt, int hop_modulo,
              const mpz_class& upper_range_limit, const mpz_class& lower_range_limit, const vector&
powers_of_two) {
    vector T(Nt, Z), W(Nw, Z);
    vector t(Nt), w(Nw);

    gmp_randclass rand(gmp_randinit_default);

    for (int k = 0; k < Nt; ++k) {
        t[k] = lower_range_limit + rand.get_z_range(upper_range_limit - lower_range_limit);
        T[k] = mul(t[k]);
    }

    for (int k = 0; k < Nw; ++k) {
        w[k] = rand.get_z_range(upper_range_limit - lower_range_limit);
        W[k] = add(W0, mul(w[k]));
    }

    long long Hops = 0, Hops_old = 0;
    auto t0 = chrono::high_resolution_clock::now();
    vector memo(hop_modulo);

    for (int pw = 0; pw < hop_modulo; ++pw) {
        memo[pw] = powers_of_two[pw];
    }

    bool solved = false;
    while (!solved) {
        for (int k = 0; k < (Nt + Nw); ++k) {
            ++Hops;
            if (k < Nt) {
                mpz_class pw = T[k][0] % hop_modulo;
                solved = comparator(T[k], t[k], DP_rarity, T, t, W, w);
                if (solved) break;
                t[k] += memo[pw.get_ui()];
                T[k] = add(P[pw.get_ui()], T[k], modulo);
            } else {
                int n = k - Nw;
                mpz_class pw = W[n][0] % hop_modulo;
                solved = comparator(W[n], w[n], DP_rarity, W, w, T, t);
                if (solved) break;
                w[n] += memo[pw.get_ui()];
                W[n] = add(P[pw.get_ui()], W[n], modulo);
            }
        }

        auto t1 = chrono::high_resolution_clock::now();
        double elapsed_seconds = chrono::duration_cast>(t1 - t0).count();
        if (elapsed_seconds > 1.0) {
            double hops_per_second = static_cast(Hops - Hops_old) / elapsed_seconds;
            auto elapsed_time = chrono::duration_cast(t1 - starttime);
            int hours = chrono::duration_cast(elapsed_time).count();
            int minutes = chrono::duration_cast(elapsed_time % chrono::hours(1)).count();
            int seconds = (elapsed_time % chrono::minutes(1)).count();
            stringstream elapsed_time_str;
            elapsed_time_str << setfill('0') << setw(2) << hours << ":"
                             << setfill('0') << setw(2) << minutes << ":"
                             << setfill('0') << setw(2) << seconds;
            double p_2 = log2(Hops);
            cout << "\r[+] [Hops: 2^" << fixed << setprecision(2) << p_2 << " <-> " << fixed << setprecision(0)
                 << hops_per_second << " h/s] ["
                 << elapsed_time_str.str() << "]" << flush;
            t0 = t1;
            Hops_old = Hops;
        }
    }

    cout << "\r[+] Hops: " << Hops << endl;
    auto end = chrono::high_resolution_clock::now();
    double elapsed_seconds = chrono::duration_cast>(end - starttime).count();
    return "\r[+] Solution time: " + to_string(elapsed_seconds) + " sec";
}

int main() {
    int puzzle = 50;
    string compressed_public_key =
    "03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6";
    int kangaroo_power = 6;
    mpz_class lower_range_limit = mpz_class(1) << (puzzle - 1);
    mpz_class upper_range_limit = (mpz_class(1) << puzzle) - 1;

    mpz_class DP_rarity = mpz_class(1) << ((puzzle - 2 * kangaroo_power) / 2 - 2);
    int hop_modulo = ((puzzle - 1) / 2) + kangaroo_power;

    int Nt = 1 << kangaroo_power;
    int Nw = 1 << kangaroo_power;

    vector powers_of_two = generate_powers_of_two(hop_modulo);

    mpz_class X, Y;
    if (compressed_public_key.length() == 66) {
        X = mpz_class(compressed_public_key.substr(2), 16);
        Y = X2Y(X, stoi(compressed_public_key.substr(0, 2)) - 2);
    } else {
        cout << "[error] pubkey len(66/130) invalid!" << endl;
        return 1;
    }

    Point W0 = {X, Y};
    auto starttime = chrono::high_resolution_clock::now();
    time_t currentTime = time(nullptr);
    cout << "\r\033[01;33m[+]\033[32m KANGAROO: \033[01;33m" << ctime(¤tTime) << "\033[0m" << "\r";
    cout << "[+] [Puzzle]: " << puzzle << endl;
    cout << "[+] [Lower range limit]: " << lower_range_limit << endl;
    cout << "[+] [Upper range limit]: " << upper_range_limit << endl;
    cout << "[+] [EC Point Coordinate X]: " << X << endl;
    cout << "[+] [EC Point Coordinate Y]: " << Y << endl;
    mpz_class expected_hops = 2.2 * sqrt(mpz_class(1) << (puzzle - 1));
    double log_expected_hops = log2(expected_hops.get_d());
    cout << "[+] [Expected Hops: 2^" << fixed << setprecision(2)
            << log_expected_hops << " (" << expected_hops << ")]" << endl;

    vector P = {PG};
    P.reserve(256);
    for (int k = 0; k < 255; ++k) {
        P.push_back(add(P[k], P[k]));
    }

    unsigned long seed = static_cast(time(nullptr));
    gmp_randclass rand(gmp_randinit_default);
    rand.seed(seed);

    search(P, W0, DP_rarity, Nw, Nt, hop_modulo, upper_range_limit, lower_range_limit, powers_of_two);

    cout << "\r[+] Average time to solve: " <<
chrono::duration_cast(chrono::high_resolution_clock::now() - starttime).count() << " sec" << endl;

    return 0;
}

g++ -o kangaroo kangaroo.cpp -m64 -march=native -mtune=native -mssse3 -Wall -Wextra -ftree-vectorize -flto -O3 -funroll-loops -ffast-math -fopenmp -lgmp -lgmpxx

clang++ -std=c++11 -o kangaroo kangaroo.cpp -m64 -march=native -mtune=native -mssse3 -Wall -Wextra -ftree-vectorize -flto -O3 -funroll-loops -ffast-math -lgmp -lgmpxx