C++ Builder
| Главная | Уроки | Статьи | FAQ | Форум | Downloads | Литература | Ссылки | RXLib | Диски |

 
Модульная математика, Помогите вычислить !!!!
Aptem
Отправлено: 05.11.2004, 07:05


Мастер участка

Группа: Участник
Сообщений: 349



Привет, всем !

Разрабатывая прогу по шифрованию столкнулся с огромными вычислениями, не могу программно реализовать вот такие вычисления

CODE
115^101 mod 551


Диапазон вычислений не выходит за рамки размеров типа 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

Очевидно из-за потери значащих разрядов. wink.gif

Наверное, стоит применить какой либо более хитрый способ расчёта...
Doga
Отправлено: 06.11.2004, 14:17


Мастер участка

Группа: Участник
Сообщений: 575



Может поискать где-нить мат. библиотеку для расчётов с повышенной точностью — что то я про это слышал...
Guest
Отправлено: 06.11.2004, 14:22


Не зарегистрирован







Используйте не pow(), а powl()
Doga
Отправлено: 06.11.2004, 14:27


Мастер участка

Группа: Участник
Сообщений: 575



Это не поможет biggrin.gif

Второй результат был получен с помощью

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ти разрядов при расчётах, иначе была бы такая же петрушка smile.gif

А мат. библиотека для расчётов с повышенной точностью существует — называется "Rogue Wave® SourcePro™ С++", правда стоит бешенных баксов sad.gif Может есть где на халяву, но я пока не нашёл...

Можно попробовать подругому. Создать *.DLL c необходимыми мат. процедурами в среде Visual FORTRAN от MicroSoft (как известно, специализация FORTRANа — матрасчёты, там есть необходимые библиотеки) и исползовать её в своём проэкте... wink.gif
Aptem
Отправлено: 08.11.2004, 06:05


Мастер участка

Группа: Участник
Сообщений: 349



QUOTE (Doga @ 07/11/2004, 18:06)
Можно попробовать подругому.  Создать *.DLL c необходимыми мат. процедурами в среде Visual FORTRAN от MicroSoft (как известно, специализация FORTRANа — матрасчёты, там есть необходимые библиотеки) и исползовать её в своём проэкте... wink.gif

Да уж... не лучший вариант, учитывая, что я ни черта не понимаю в Fortran'е !!! sad.gif
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 (лонг) sad.gif

Теперь, 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)

Надеюсь что идея понятна. smile.gif
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 (лонг) sad.gif

Теперь, 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)

Надеюсь что идея понятна. smile.gif

Проблема в вычислении 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ти разрядов при расчётах, иначе была бы такая же петрушка smile.gif

А мат. библиотека для расчётов с повышенной точностью существует — называется "Rogue Wave® SourcePro™ С++", правда стоит бешенных баксов sad.gif Может есть где на халяву, но я пока не нашёл...

Можно попробовать подругому. Создать *.DLL c необходимыми мат. процедурами в среде Visual FORTRAN от MicroSoft (как известно, специализация FORTRANа — матрасчёты, там есть необходимые библиотеки) и исползовать её в своём проэкте... wink.gif

Зачем платная библиотека? Используй бесплатную 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)

Надеюсь что идея понятна.  smile.gif

Ошибку сделал. ohmy.gif

А^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)

Надеюсь что теперь идея понятна. smile.gif
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. А так как после взятия модуля, разрядность результата получается равной разрядности модуля (опять же в общем случае), то при возврачении результата используется явно преобразование типов (хотя оно не обязательно, да и разрядность модуля может отличаться от разрядности аргументов).
Удачи!!!

Огромное спасибо за функцию, теперь работает как надо ! biggrin.gif

Вернуться в Вопросы программирования в C++Builder