Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.56/9: Рейтинг темы: голосов - 9, средняя оценка - 4.56
gustav21
20 / 20 / 4
Регистрация: 23.10.2009
Сообщений: 139
1

Операции с большими числами

29.11.2009, 23:03. Просмотров 1823. Ответов 1
Метки нет (Все метки)

Всем доброго времени суток! Меня интересует такая проблема. В известном алгоритме электронной цифровой подписи Эль-Гамаля для проверки подписи необходимо проверять следующее равенство:

y^r * r^s = g^m (mod p)
^ - значок степени (не знаю как здесь вставлять нормальные степени)

Проверка, очевидно, сводится к вычислению сначала левой части по модулю p, затем правой части по модулю p, ну и если они равны, то подпись правильная. Но дело не в этом ... числа y, r, s большие, порядка 10-20 знаков. Программу пишу на C#, пытался возводить в степень с помощью Math.Pow(), но уже только для первой степени (y^r) результат возведения получается infinity (бесконечность). Для вычисления правой части (возведение в степень по модулю) есть быстрые алгоритмы, здесь все хорошо, но как вычислить левую часть (произведение степеней по модулю) не представляется понятным. Может кто-нибудь сталкивался с этим ... наверняка, так как подпись Эль-Гамаля достаточно известна и как-то реализуется.
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.11.2009, 23:03
Ответы с готовыми решениями:

Операции над большими числами
Всем доброго времени суток!Подскажите,пожалуйста,как на c# написать в консольном приложении...

mega16 операции с большими числами
Доброго всем дня! Собираю дрыгалку ногами, ничего серьезного, вроде все просто. Но вот как дошло...

Операции над большими числами
Здравствуйте. Хочу создать класс выполняющий арифметические операции над большие числа (знаю что...

Операции с большими дробными числами
Доброго времени суток! Мне нужно реализовать калькулятор больших(целых и дробных) чисел....

Математические операции над очень большими числами.
мне нужно выполнить мат. операции над большими числами. Опрерация имеет вид a^51 mod 319 гда...

1
gustav21
20 / 20 / 4
Регистрация: 23.10.2009
Сообщений: 139
30.11.2009, 16:34  [ТС] 2
Проблему решил как всегда до того, как что-то посоветовали на форуме ) ... В общем, нашел, что произведение чисел по модулю равно произведению модулей по модулю ... то есть для моего случая:

( y^r * r^s ) mod p = ( (y^r mod p) * (r^s mod p) ) mod p ... то есть каждый промеежуточный результат приводится по модулю. Это характерно, кстати, для всех операций арифметики вычетов. Эту информацию нашел в инете здесь http://window.edu.ru/window_catalog/pdf2txt?p_id=28771&p_page=9. Вообще эта теория чисел интересная штука )

P.S. PDF-версию документа, расположенного по ссылке, прикрепляю ... Ее можно скачать и непосредственно на той странице.
0
Вложения
Тип файла: pdf 10.pdf (1.35 Мб, 85 просмотров)
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.11.2009, 16:34

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Операции с большими массивами данных
Доброе время суток! Мне нужно оперировать большими объемами данных - массивы до 4 Гб....

Работа с большими числами
var a,b:double; begin assign(input, 'input.txt'); reset(input); assign(output,...

Проблемы с большими числами
Здравствуйте. Решил написать калькулятор для перевода чисел из одной системы счисления в другую....


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.