Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > помогите решить уравнение

Автор: redwhite90 6.11.2011, 13:33

(a*x^b)%n=1
кроме x все переменные известны.

Автор: volatile 6.11.2011, 13:53

Цитата(redwhite90 @ 6.11.2011, 13:33

)

Раз вопрос задан в С разделе, это я так понимаю XOR ?

Уравнение может иметь много решений.

Для начала расставим скобки
Умножение имеет более высокий приоритет чем xor, значит
((a*x)^b)%n=1

Первое решение
((a*x)^b)= n+1
(a*x)= (n+1)^b
x = ((n+1)^b)/a

в принципе все решения запишутся так:
x = ((k*n+1)^b)/a, где k целое, 1,2,3...inf
smile

Автор: math64 6.11.2011, 13:57

В целых числах ? ^ возведение в степень или xor ?
Если возведение в степень, см. учебник по алгебре для первого курса мехмата (если я не ошибаюсь, там такие уравнения решались, по крайней мере для простого n)

Автор: redwhite90 6.11.2011, 14:19

возведение в степень!

Добавлено через 15 секунд
в целых числах

Добавлено через 4 минуты и 30 секунд
просто надо запрограммировать схему идентификации гилу-кискатра

Добавлено через 5 минут и 53 секунды
а там условие такое - не ясно как его выполнить

Автор: borisbn 6.11.2011, 22:02

volatile, math64, странно, что у вас возник вопрос, что такое ^ - степень или XOR, но не возникло вопроса, что такое % - остаток от деления или .... а вот или я хз что...

2 ТС: потрудитесь сделать картинку с принятыми в математике символами. Вот, хотя бы, http://www.codecogs.com/latex/eqneditor.php

Автор: redwhite90 7.11.2011, 01:18

http://rghost.ru/28864241/image.png

Добавлено через 3 минуты и 40 секунд
это так в первоисточнике(Шнайер)

только тут неизвестно B

Добавлено через 4 минуты и 15 секунд
http://rghost.ru/28864241.view

Автор: math64 7.11.2011, 07:58

В принципе, можно перебором

Код


for (x = 0; x < n-1; x++) {
  if (a*pow(x,b)%n == 1)
    cout << x << endl;
}

Если это медленно, нужно разложить n на простые множители, n = pow(p1,k1)*pow(p2,k2)*... pow(pm,km)
и решать и уравнения
a*pow(x,b) % pow(pi,ki) == 1;

pow() естественно, написать самому, а не использовать из math.h - там будут ошибки округлений
Чтобы избежать переполнений нужно при переборе считать по модулю n:

Код


class modulus {
int val, n;
public:
modulus(int _val, int _n) : val(_val), n(_n) {}
modulus(modulus& m);
operator int() { return val; }
modulus operator *(const modulus& m) const { return modulus((int64)val*m.val%n, n); }
...
};

Автор: redwhite90 7.11.2011, 23:38

math64, n как раз таки произведение двух простых чисел.

Цитата(math64 @ 7.11.2011, 07:58

)

Если это медленно, нужно разложить n на простые множители, n = pow(p1,k1)*pow(p2,k2)*... pow(pm,km)и решать и уравненияa*pow(x,b) % pow(pi,ki) == 1;

не могли бы поподробней объяснить что и как ракладывать.
вот например n= 77 т.е. можно разложить как 11*7

Автор: math64 9.11.2011, 10:53

Например n=28 разложми на множители 28=2 * 2 * 7=4 * 7
решаем уравнения a * x4 ^ b = 1 (mod 4) и a * x7 ^ b = 1 (mod 7) , получаем x4 и x7
Тогда x == x4 (mod 4) и x = x7 (mod 7)
x = 7 * k + x7; 7 * k + x7 = x4 (mod 4)
3 * k = x4 - x7 (mod 4) , находим обратное к 3: 3 * 3 = 1 (mod 4)
k = 3*(x4-x7) (mod 4)
Получаем
x = 7 * (3 * (x4-x7) % 4) + x7

Для решения без перебора обратитесь на математический форум.