Разное

есть выражение (a*x) mod b = 1
известно a и b (они взаимнопростые), как выцепить x (оно должно быть целым)... тупой перебор не подходит....

Уже весь мозг сточил, нид хелп...

mod - как я понимаю МОДУЛЬ.
А если так:
возвести всё в квадрат, получится
a2*x2*b=1 // 2- квадрат
a2*x2 =1/b
x2=1/(b*a2)
x=mod( 1/(b*a2) )

Что-то вроде этого...

Оригинальное рассуждение, если учесть, что модуль, это: модуль числа.

>mod - как я понимаю МОДУЛЬ.

неправильно понимаете.
P mod Q - это остаток от деления P на Q .


При известных целых a и b требуется найти такое целое x, что выражение
( a * x ) % b == 1
окажется истинным.

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

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

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

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

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

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

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

// расширенный алгоритм евклида 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)), правда данный алгоритм возвращает и отрицательные тоже =/

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

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

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