Помогите ктонибудь пожалуйста понять как например найти
(тоесть какие действия нужно выполнить)| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Центр помощи > [Теория чисел] Сравнение |
| Автор: Ak47black 7.3.2009, 22:20 |
| Здравствуйте. Помогите ктонибудь пожалуйста понять как например найти (тоесть какие действия нужно выполнить) |
| Автор: Akina 8.3.2009, 00:21 |
| Ну скажем так... 3070^19661 mod 49601 = (3070^2)^9830 * 3070 mod 49601 = (9424900)^9830 * 3070 mod 49601 = (9424900 mod 49601)^9830 * 3070 mod 49601 = 710^9830 * 3070 mod 49601 = и так далее... в общем x^y mod z = (x mod z)^y mod z |
| Автор: Ak47black 8.3.2009, 02:00 |
Не так я не пойму  Если-ли гдето описание что нужно делать, на что нужно смотреть, как решать примеры такого рода? И мне очень интересно ещё узнать, как компьютер справляется с этой задачей, например когда расшифровывает закодированный текст с помошью RSA? Можете ктото своими словами объяснить? (Ато туго у меня с этим) |
| Автор: Kakadu 8.3.2009, 10:22 |
| Попробуй понять на подсознательном уровне, что такое сравнение. помню, что я на первом курсе тоже с этим попарился, когда получал зачет по АТЧ. Формулу тебе дали правильную. Попробуй поднять с потолка маленькие числа, и попробовать поразвлекаться с этой формулой. Потом уже переход к большим числам. |
| Автор: Ak47black 8.3.2009, 13:49 |
| А как эта формула называется? |
| Автор: Kakadu 8.3.2009, 14:39 |
| никак. она настолько очевидна, что не имеет названия. |
| Автор: Ak47black 8.3.2009, 15:46 |
| А есть-ли какието другие алгоритмы, с которыми быстрей можно решить? |
| Автор: Irdis 8.3.2009, 16:10 |
| я их не знаю |
| Автор: Ak47black 8.3.2009, 18:06 |
| А может быть ктото знает как можно решить например этот пример С минимум писанины при этом используя обычный калькулятор?  |
| Автор: Kakadu 8.3.2009, 18:57 |
| решай тем способом, что тебе дали. Я на зачете это писал и решал без калькулятора. Чем ты хуже? |
| Автор: Ak47black 8.3.2009, 19:33 | ||
| Проблема заключается в следующем моменте Попробую её объяснить на том решении которое вверху
Так как 19661 делится на 2 с остатком 1 то мы домнажаем на 3070. Если число достаточно большое и если делить каждый раз показатель на 2 то приходится домнажать кучу раз и в результате если умножить все эти множетели то калькулятор небурёт Вот что с ними делать при решении? |
| Автор: Akina 8.3.2009, 22:10 | ||
a*b*c mod x = (a*b mod x)*c mod x = a*(b*c mod x) mod x Везде, где можно, вместо чисел используем остаток. Для чего, собсно, порой и приходится умножать. И вовсе не обязательно те числа, что в самом начале выражения. да ещё транзитивность умножения вспомни. |
| Автор: Ak47black 9.3.2009, 02:00 |
А теперь уловил суть, вроде получается  Akina, спасибо огромное! |
