// расширенный алгоритм евклида
void extended_euclid(mpz_t a, mpz_t b, mpz_t &x, mpz_t &y, mpz_t &d)
{
mpz_t q, r, x1, x2, y1, y2, t;
mpz_init2(q,2048);
mpz_init2(r,2048);
mpz_init2(x1,2048);
mpz_init2(x2,2048);
mpz_init2(y1,2048);
mpz_init2(y2,2048);
mpz_init2(t,2048);
if (mpz_cmp_ui(b,0) == 0) // if (b == 0)
{
mpz_set(d,a); // d = a
mpz_set_ui(x,1); // x = 1
mpz_set_ui(y,0); // y = 0
return;
}
mpz_set_ui(x2,1); // x2 = 1
mpz_set_ui(x1,0); // x1 = 0
mpz_set_ui(y2,0); // y2 = 0
mpz_set_ui(y1,1); // y1 = 1
while (mpz_cmp_ui(b,0)>0) // while (b > 0)
{
mpz_fdiv_q(q,a,b); // q = a / b
mpz_mul(t,q,b); //
mpz_sub(r,a,t); // r = a - q * b
mpz_mul(t,q,x1); //
mpz_sub(x,x2,t); // x = x2 - q * x1
mpz_mul(t,q,y1); //
mpz_sub(y,y2,t); // y = y2 - q * y1
mpz_set(a,b); // a = b
mpz_set(b,r); // b = r
mpz_set(x2,x1); // x2 = x1
mpz_set(x1,x); // x1 = x
mpz_set(y2,y1); // y2 = y1
mpz_set(y1,y); // y1 = y
}
mpz_set(d,a); // d = a
mpz_set(x,x2); // x = x2
mpz_set(y,y2); // y = y2
mpz_clear(q);
mpz_clear(r);
mpz_clear(x1);
mpz_clear(x2);
mpz_clear(y1);
mpz_clear(y2);
mpz_clear(t);
}
// обратное по модулю
void inverse(mpz_t a, mpz_t n, mpz_t &x)
{
mpz_t d, y;
mpz_init2(d,2048);
mpz_init2(y,2048);
extended_euclid(a, n, x, y, d);
}
|