VPF::помогите решить уравнение - Форум программистов

redwhite90

Дата 6.11.2011, 13:33 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 332
Регистрация: 14.7.2011

Репутация: нет
Всего: нет

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

volatile

Дата 6.11.2011, 13:53 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 37
Всего: 85

Цитата(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 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 8
Всего: 72

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

redwhite90

Дата 6.11.2011, 14:19 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 332
Регистрация: 14.7.2011

Репутация: нет
Всего: нет

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

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

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

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

borisbn

Дата 6.11.2011, 22:02 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 22
Всего: 135

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

2 ТС: потрудитесь сделать картинку с принятыми в математике символами. Вот, хотя бы, здесь

--------------------

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

redwhite90

Дата 7.11.2011, 01:18 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 332
Регистрация: 14.7.2011

Репутация: нет
Всего: нет

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

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

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

Добавлено через 4 минуты и 15 секунд

math64

Дата 7.11.2011, 07:58 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 8
Всего: 72

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

Код


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); }
...
};

Это сообщение отредактировал(а) math64 - 7.11.2011, 08:00

redwhite90

Дата 7.11.2011, 23:38 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 332
Регистрация: 14.7.2011

Репутация: нет
Всего: нет

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 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 8
Всего: 72

Например 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

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

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »