#include <mpir.h>
#include <stdint.h>
#include <stdlib.h>
#include <math.h>

int compare(const void* a, const void* b){
    return ( *(uint64_t*)a - *(uint64_t*)b );
}

bool find_in_array(uint64_t* arr, size_t len, uint64_t x){
    size_t first = 0;
    size_t last = len;

    size_t mid;
    if(last == 0)
        return false;
    if(arr[0] > x)
        return false;
    if (arr[len - 1] < x)
        return false;
    while (first < last){
        mid = first + (last - first) / 2;
        if (x <= arr[mid]){
            last = mid;
        }else{
            first = mid + 1;
        }
    }
    if(arr[last] == x)
        return true;
    return false;
}

int main(){
        mpz_t a, b, m;
        mpz_init_set_str(a,"6511709995802996252529428210009069141516455100602512742258547866292839663070281213795462953359084389612327175129512390242393774885156190907043183764572298",10);
        mpz_init_set_str(b,"4016751268155181878780762958485595786864539552267966173503519872828650364102948010668074636189225260885467109630266705699778224615794326630829490560742794",10);
        mpz_init_set_str(m,"9913033868557133667485171584043308894354447793802229576147965224579616862439637051468618269920939124273132778910108308880842351094700094598897767100778663",10);
        const unsigned long long  n = 1048576;

        uint64_t* mem = (uint64_t*)calloc(n+1, sizeof(uint64_t));


        uint64_t* memp = mem;
        mpz_t tmp; mpz_init_set_ui(tmp,1);
        mpz_t tmp2; mpz_init(tmp2);
        mpz_powm_ui(tmp,a,n,m);
        for(uint64_t p = 0; p <= n ;++p){
            mpz_mul(tmp,tmp,a);
            mpz_mod(tmp,tmp,m);
            mpz_export(memp,NULL,0,sizeof(uint64_t),0,0,tmp);
            memp++;
        }
        printf("OK!\n");
        qsort(mem,n,sizeof(uint64_t),compare);
        printf("OK2!\n");
        uint64_t elem = 0;
        mpz_set(tmp, b);
        for(uint64_t q = 0; q!=UINT64_MAX ; ++q){
            //mpz_powm_ui(tmp, a, q, m);
            mpz_mul(tmp,tmp,a);
            mpz_mod(tmp, tmp, m);
            mpz_export(&elem,NULL,0,sizeof(uint64_t),0,0,tmp);
            if(find_in_array(mem,n,elem)){
                printf("OK2!\n");
                break;
            }
        }
        free(mem);
        return 0;
}