Разное

Интересно конечно, тем более как это обратное по модулю (имею ввиду не диапазон), если это не "чистое деление".

> возвести всё в квадрат, получится
> a2*x2*b=1 // 2- квадрат
|b|^2 = b? :)))

// расширенный алгоритм евклида 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); }

если кому интересно, то вот нахождение обратного по модулю (адаптировано под большие числа (gmplib)), правда данный алгоритм возвращает и отрицательные тоже =/

Всем спасибо за участие.

У автора не получается нати обратное по модулю, поэтому автор и попросил помощи...

У меня такое чувство, что автор пытается навесить нам что-то связанное с RSA. То ли задачу генерации ключей, то ли задачу взлома... :))

Ну да, я и забыл (хотя и читал):). С другой стороны, нет логики в этом поиске, я смысла не могу уловить. Автор то ведь пытается, вроде бы, найти не диапазон.

я так понял, что известны и а и b
Суть не в том, делится или не делится. Суть в том, чтоб остаток равнялся бы именно единице.

Вот меня и поразила "железная" логика рассуждения.) Стит ли искать, если мы узнаем, собственно говоря, делится ли произведение без остатка или нет? Ведь чтобы получить более менее логичный ответ, нам нужно знать еще и b, а известно ли оно...

надо полагать, автора устроит любое от 0 < x < b
:)

А таких значений может быть не одно.)