![]() |
Модераторы: Daevaorn |
![]() ![]() ![]() |
|
redwhite90 |
|
|||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 332 Регистрация: 14.7.2011 Репутация: нет Всего: нет |
(a*x^b)%n=1
кроме x все переменные известны. |
|||
|
||||
volatile |
|
|||
![]() Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 2107 Регистрация: 7.1.2011 Репутация: 37 Всего: 85 |
Раз вопрос задан в С разделе, это я так понимаю 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 ![]() |
|||
|
||||
math64 |
|
|||
Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 2505 Регистрация: 12.4.2007 Репутация: 8 Всего: 72 |
В целых числах ? ^ возведение в степень или xor ?
Если возведение в степень, см. учебник по алгебре для первого курса мехмата (если я не ошибаюсь, там такие уравнения решались, по крайней мере для простого n) |
|||
|
||||
redwhite90 |
|
|||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 332 Регистрация: 14.7.2011 Репутация: нет Всего: нет |
возведение в степень!
Добавлено через 15 секунд в целых числах Добавлено через 4 минуты и 30 секунд просто надо запрограммировать схему идентификации гилу-кискатра Добавлено через 5 минут и 53 секунды а там условие такое - не ясно как его выполнить |
|||
|
||||
borisbn |
|
|||
![]() Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 4875 Регистрация: 6.2.2010 Где: Ростов-на-Дону Репутация: 22 Всего: 135 |
volatile, math64, странно, что у вас возник вопрос, что такое ^ - степень или XOR, но не возникло вопроса, что такое % - остаток от деления или .... а вот или я хз что...
2 ТС: потрудитесь сделать картинку с принятыми в математике символами. Вот, хотя бы, здесь -------------------- Женщины отличаются от программистов тем, что у них чары состоят из стрингов |
|||
|
||||
redwhite90 |
|
|||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 332 Регистрация: 14.7.2011 Репутация: нет Всего: нет |
http://rghost.ru/28864241/image.png
Добавлено через 3 минуты и 40 секунд это так в первоисточнике(Шнайер) только тут неизвестно B Добавлено через 4 минуты и 15 секунд ![]() |
|||
|
||||
math64 |
|
||||
Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 2505 Регистрация: 12.4.2007 Репутация: 8 Всего: 72 |
В принципе, можно перебором
Если это медленно, нужно разложить n на простые множители, n = pow(p1,k1)*pow(p2,k2)*... pow(pm,km) и решать и уравнения a*pow(x,b) % pow(pi,ki) == 1; pow() естественно, написать самому, а не использовать из math.h - там будут ошибки округлений Чтобы избежать переполнений нужно при переборе считать по модулю n:
Это сообщение отредактировал(а) math64 - 7.11.2011, 08:00 |
||||
|
|||||
redwhite90 |
|
|||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 332 Регистрация: 14.7.2011 Репутация: нет Всего: нет |
math64, n как раз таки произведение двух простых чисел.
не могли бы поподробней объяснить что и как ракладывать. вот например n= 77 т.е. можно разложить как 11*7 |
|||
|
||||
math64 |
|
|||
Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 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 Для решения без перебора обратитесь на математический форум. |
|||
|
||||
![]() ![]() ![]() |
Правила форума "С++:Общие вопросы" | |
|
Добро пожаловать!
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn |
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |