| Aptem |
| Отправлено: 05.11.2004, 07:05 |
|
Мастер участка
Группа: Участник
Сообщений: 349
|
Привет, всем !
Разрабатывая прогу по шифрованию столкнулся с огромными вычислениями, не могу программно реализовать вот такие вычисления
Диапазон вычислений не выходит за рамки размеров типа double, поэтому использую fmod, но все равно ничего не получается, выдает какую-то ерунду.
Помогите, чем можете !!! Спасибо за внимание !!!
|
|
| Aptem |
| Отправлено: 06.11.2004, 06:27 |
|
Мастер участка
Группа: Участник
Сообщений: 349
|
...неужели никто с fmod () не работал ???
|
|
| Doga |
| Отправлено: 06.11.2004, 12:36 |
|
Мастер участка
Группа: Участник
Сообщений: 575
|
Вообще то, не должно быть никаких проблем...
Нелзя ли поподробнее, с кодом?
|
|
| Aptem |
| Отправлено: 06.11.2004, 12:50 |
|
Мастер участка
Группа: Участник
Сообщений: 349
|
Ну хоть один человек откликнулся...
Попробуйте выполнить такое:
| CODE | | ShowMessage ( fmod ( pow ( 115, 101 ), 551 ) ); |
Что он вам покажет ???
Если посчитать на калькуляторе, то получается 115, а ShowMessage показывает какую-то ерунду.
|
|
| Doga |
| Отправлено: 06.11.2004, 14:13 |
|
Мастер участка
Группа: Участник
Сообщений: 575
|
514, если все перменные типа double
352, если все перменные типа long double или Extended
Очевидно из-за потери значащих разрядов. 
Наверное, стоит применить какой либо более хитрый способ расчёта...
|
|
| Doga |
| Отправлено: 06.11.2004, 14:17 |
|
Мастер участка
Группа: Участник
Сообщений: 575
|
Может поискать где-нить мат. библиотеку для расчётов с повышенной точностью — что то я про это слышал...
|
|
| Guest |
| Отправлено: 06.11.2004, 14:22 |
|
Не зарегистрирован
|
Используйте не pow(), а powl() |
|
| Doga |
| Отправлено: 06.11.2004, 14:27 |
|
Мастер участка
Группа: Участник
Сообщений: 575
|
Это не поможет 
Второй результат был получен с помощью
extern PACKAGE Extended __fastcall Power(constExtended Base, const Extended Exponent);
|
|
| Aptem |
| Отправлено: 06.11.2004, 19:01 |
|
Мастер участка
Группа: Участник
Сообщений: 349
|
Попробывал посчитать на калькуляторе windows, все нормально, показывает то, что нужно, значит расчеты произведены средствами win, кто-нибудь знате как работает калькулятор windows ???
|
|
| Doga |
| Отправлено: 07.11.2004, 17:04 |
|
Мастер участка
Группа: Участник
Сообщений: 575
|
Судя по всему калькулятор windows использует больше 80ти разрядов при расчётах, иначе была бы такая же петрушка 
А мат. библиотека для расчётов с повышенной точностью существует — называется "Rogue Wave® SourcePro™ С++", правда стоит бешенных баксов  Может есть где на халяву, но я пока не нашёл...
Можно попробовать подругому. Создать *.DLL c необходимыми мат. процедурами в среде Visual FORTRAN от MicroSoft (как известно, специализация FORTRANа — матрасчёты, там есть необходимые библиотеки) и исползовать её в своём проэкте...
|
|
| Aptem |
| Отправлено: 08.11.2004, 06:05 |
|
Мастер участка
Группа: Участник
Сообщений: 349
|
| QUOTE (Doga @ 07/11/2004, 18:06) | | Можно попробовать подругому. Создать *.DLL c необходимыми мат. процедурами в среде Visual FORTRAN от MicroSoft (как известно, специализация FORTRANа — матрасчёты, там есть необходимые библиотеки) и исползовать её в своём проэкте... |
Да уж... не лучший вариант, учитывая, что я ни черта не понимаю в Fortran'е !!!
|
|
| Boyko |
| Отправлено: 08.11.2004, 16:14 |
|
Станционный диспетчер
Группа: Участник
Сообщений: 88
|
| QUOTE (Aptem @ 06/11/2004, 19:03) | | Попробывал посчитать на калькуляторе windows, все нормально, показывает то, что нужно, значит расчеты произведены средствами win, кто-нибудь знате как работает калькулятор windows ??? |
Почемъ думаешь что калкулятор Винда всегда правильно работает? Калкулятор Линюкса ответил 352...
Еще, 115^101 = 10^209, а 2^64 = 10^19 (лонг)
Теперь, 101 = 1100101.
115^1 = 115 (mod 551)
115^2 = 13225 = 1 (mod 551)
115^100 = 1 (mod 551)
115^1 * 115 ^100 = 115 * 1^101 = 115 (mod 551)
Для 115 хорошо, для произвольное А:
А^1 = а1 (мод 551) 0<=а1<551
А^2 = а2 (мод 551) 0<=а2<551
А^3 = а3 (мод 551) 0<=а3<551
А^4 = а4 (мод 551) 0<=а4<551
А^5 = а5 (мод 551) 0<=а5<551
А^6 = а6 (мод 551) 0<=а6<551
А ^ 101 = А ^ 1100101 = А^1 * А^3 * А^5 * А^6 = а1 * а3 * а5 * а6 (мод 551)
Надеюсь что идея понятна. |
|
| Aptem |
| Отправлено: 08.11.2004, 18:33 |
|
Мастер участка
Группа: Участник
Сообщений: 349
|
| QUOTE (Boyko @ 08/11/2004, 17:16) | | QUOTE (Aptem @ 06/11/2004, 19:03) | | Попробывал посчитать на калькуляторе windows, все нормально, показывает то, что нужно, значит расчеты произведены средствами win, кто-нибудь знате как работает калькулятор windows ??? |
Почемъ думаешь что калкулятор Винда всегда правильно работает? Калкулятор Линюкса ответил 352...
Еще, 115^101 = 10^209, а 2^64 = 10^19 (лонг)
Теперь, 101 = 1100101.
115^1 = 115 (mod 551)
115^2 = 13225 = 1 (mod 551)
115^100 = 1 (mod 551)
115^1 * 115 ^100 = 115 * 1^101 = 115 (mod 551)
Для 115 хорошо, для произвольное А:
А^1 = а1 (мод 551) 0<=а1<551
А^2 = а2 (мод 551) 0<=а2<551
А^3 = а3 (мод 551) 0<=а3<551
А^4 = а4 (мод 551) 0<=а4<551
А^5 = а5 (мод 551) 0<=а5<551
А^6 = а6 (мод 551) 0<=а6<551
А ^ 101 = А ^ 1100101 = А^1 * А^3 * А^5 * А^6 = а1 * а3 * а5 * а6 (мод 551)
Надеюсь что идея понятна. |
Проблема в вычислении mod, а не возведения в степень...
...наверное
Но за вариант спасибо...
Отредактировано Aptem — 08/11/2004, 19:36
|
|
| Boyko |
| Отправлено: 09.11.2004, 15:51 |
|
Станционный диспетчер
Группа: Участник
Сообщений: 88
|
| QUOTE (Aptem @ 08/11/2004, 18:35) | Проблема в вычислении mod, а не возведения в степень...
...наверное
|
Неверно!
Проблема в том что
115^101 = 10^209
fmod работает с double long (64 bits)
2^64 = 10^19
Отсюда следует что надо редуцировать mod 551 ! |
|
| vvoid |
| Отправлено: 12.11.2004, 18:36 |
|
Машинист паровоза
Группа: Участник
Сообщений: 171
|
Ребята, всё проще гараздо!!!
Ошибочный результат возникает, естественно из-за того, что 115^101 — уж дюже большое число!!! (А виндовый калькулятор работает максимум с 64-битными числами)
Решение проблемы
Как известно возведение в степень — это некоторое количество умножений! Что мешает умножать в цикле и после каждого умножения брать модуль? (Долго конечно, но тут как никак присутствуют большие числа) Так что дерзайте и да пребудет с вами правильный результат!!!
Удачи!!!
|
|
| vvoid |
| Отправлено: 12.11.2004, 18:40 |
|
Машинист паровоза
Группа: Участник
Сообщений: 171
|
А для проверки результатов настоятельно рекомендую язык Pithon. Это скриптовый язык, достаточно простой и к тому же умеет работать с числами ЛЮБОЙ разрядности!!!
|
|
| Aptem |
| Отправлено: 13.11.2004, 13:29 |
|
Мастер участка
Группа: Участник
Сообщений: 349
|
Да в степень оно нормально возводится. А вот mod плохо считает !!! Если я буду после каждого умножения брать mod, то что с ним делать дальше, сложить или что ????
|
|
| vvoid |
| Отправлено: 15.11.2004, 16:11 |
|
Машинист паровоза
Группа: Участник
Сообщений: 171
|
Пример:
Функция, которая реализует нужные математические действия.
| CODE |
unsigned int BigPowMod (const unsigned int p,
const unsigned int r,
const unsigned int n)
{
// вычисление по формуле: s = (p ^ r) % n
unsigned __int64 s;
s = p;
for (unsigned int Index = 1; Index < r; Index++)
{
s = s * p;
s = s % n;
}
return((unsigned int)s);
}
|
Можно использовать и другие типы данных, но учти, что при умножении двух чисел, в общем случае получается число в двое большей разрядности. Поэтому при умножении двух int-ов я результат записывал в __int64. А так как после взятия модуля, разрядность результата получается равной разрядности модуля (опять же в общем случае), то при возврачении результата используется явно преобразование типов (хотя оно не обязательно, да и разрядность модуля может отличаться от разрядности аргументов).
Удачи!!!
Отредактировано vvoid — 15/11/2004, 17:15
|
|
| Ajgor |
| Отправлено: 15.11.2004, 16:33 |
|
Ученик-кочегар
Группа: Участник
Сообщений: 23
|
На Python получается 115:
>>> A = 115
>>> B = 101
>>> M = 551
>>> pow(A,B,M)
115 |
|
| Ajgor |
| Отправлено: 15.11.2004, 17:28 |
|
Ученик-кочегар
Группа: Участник
Сообщений: 23
|
| QUOTE (Doga @ 07/11/2004, 18:06) | Судя по всему калькулятор windows использует больше 80ти разрядов при расчётах, иначе была бы такая же петрушка
А мат. библиотека для расчётов с повышенной точностью существует — называется "Rogue Wave® SourcePro™ С++", правда стоит бешенных баксов Может есть где на халяву, но я пока не нашёл...
Можно попробовать подругому. Создать *.DLL c необходимыми мат. процедурами в среде Visual FORTRAN от MicroSoft (как известно, специализация FORTRANа — матрасчёты, там есть необходимые библиотеки) и исползовать её в своём проэкте... |
Зачем платная библиотека? Используй бесплатную Crypto++. Она поддерживает математические операции с числами любой розрядности. Crypto++ |
|
| Boyko |
| Отправлено: 16.11.2004, 13:06 |
|
Станционный диспетчер
Группа: Участник
Сообщений: 88
|
| QUOTE (Boyko @ 08/11/2004, 16:16) |
А^1 = а1 (мод 551) 0<=а1<551
А^2 = а2 (мод 551) 0<=а2<551
А^3 = а3 (мод 551) 0<=а3<551
А^4 = а4 (мод 551) 0<=а4<551
А^5 = а5 (мод 551) 0<=а5<551
А^6 = а6 (мод 551) 0<=а6<551
А ^ 101 = А ^ 1100101 = А^1 * А^3 * А^5 * А^6 = а1 * а3 * а5 * а6 (мод 551)
Надеюсь что идея понятна. |
Ошибку сделал. 
А^1 = а1 (мод 551) 0<=а1<551
А^2 = а1^2 = а2 (мод 551) 0<=а2<551
А^4 = а2^2 = а3 (мод 551) 0<=а3<551
А^8 = а3^2 = а4 (мод 551) 0<=а4<551
А^16 = а4^2 = а5 (мод 551) 0<=а5<551
А^32 = а5^2 = а6 (мод 551) 0<=а6<551
А^64 = а6^2 = а7 (мод 551) 0<=а7<551
А ^ 101 = А ^ 1100101 = А^1 * А^4 * А^32 * А^64= а1 * а3 * а6 * а7 (мод 551)
Надеюсь что теперь идея понятна. |
|
| Aptem |
| Отправлено: 18.11.2004, 14:12 |
|
Мастер участка
Группа: Участник
Сообщений: 349
|
| QUOTE (vvoid @ 15/11/2004, 17:13) | Пример:
Функция, которая реализует нужные математические действия.
| CODE |
unsigned int BigPowMod (const unsigned int p,
const unsigned int r,
const unsigned int n)
{
// вычисление по формуле: s = (p ^ r) % n
unsigned __int64 s;
s = p;
for (unsigned int Index = 1; Index < r; Index++)
{
s = s * p;
s = s % n;
}
return((unsigned int)s);
}
|
Можно использовать и другие типы данных, но учти, что при умножении двух чисел, в общем случае получается число в двое большей разрядности. Поэтому при умножении двух int-ов я результат записывал в __int64. А так как после взятия модуля, разрядность результата получается равной разрядности модуля (опять же в общем случае), то при возврачении результата используется явно преобразование типов (хотя оно не обязательно, да и разрядность модуля может отличаться от разрядности аргументов).
Удачи!!! |
Огромное спасибо за функцию, теперь работает как надо !
|
|
