#pragma once

#include <cstdint>
#include "bigint.h"

Bigint gcd(Bigint a,Bigint b);
Bigint egcd(const Bigint &a,const Bigint &b,Bigint &x,Bigint &y);

Bigint expmod(const Bigint &base,const Bigint &exponent,const Bigint &modulus);

int jacobiSymbol(Bigint a,Bigint n);

// Returns sqrt(n), rounded down if necessary
Bigint isqrt(const Bigint &n);

int ilog2(uint64_t i);

Bigint cryptrandom_big(const Bigint &upperbound); //Return value in [0,upperbound]