Модераторы: Daevaorn
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> помогите решить уравнение 
:(
    Опции темы
redwhite90
Дата 6.11.2011, 13:33 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

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



(a*x^b)%n=1
кроме x все переменные известны.
PM MAIL   Вверх
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 


PM MAIL   Вверх
math64
Дата 6.11.2011, 13:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


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

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



В целых числах ? ^ возведение в степень или xor ?
Если возведение в степень, см. учебник по алгебре для первого курса мехмата (если я не ошибаюсь, там такие уравнения решались, по крайней мере для простого n)
PM   Вверх
redwhite90
Дата 6.11.2011, 14:19 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

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



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

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

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

Добавлено через 5 минут и 53 секунды
а там условие такое - не ясно как его выполнить
PM MAIL   Вверх
borisbn
Дата 6.11.2011, 22:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


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

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



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

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


--------------------
Женщины отличаются от программистов тем, что у них чары состоят из стрингов
PM MAIL Jabber   Вверх
redwhite90
Дата 7.11.2011, 01:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

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



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

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

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

Добавлено через 4 минуты и 15 секунд
user posted image
PM MAIL   Вверх
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
PM   Вверх
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

PM MAIL   Вверх
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

Для решения без перебора обратитесь на математический форум.
PM   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn

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


 




[ Время генерации скрипта: 0.0852 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.