C ++ обрабатывает очень большие целые числа - PullRequest
Новая
       78

C ++ обрабатывает очень большие целые числа

20 голосов
/ 24 сентября 2008

Я использую алгоритм RSA для шифрования / дешифрования, и для расшифровки файлов приходится иметь дело с некоторыми довольно большими значениями. В частности, такие вещи, как 

P = C^d % n
  = 62^65 % 133

Теперь это действительно единственные вычисления, которые я буду делать. Я пытался использовать библиотеку Мэтта Маккатчена BigInteger, но во время компоновки получаю много ошибок компилятора, например: 

encryption.o(.text+0x187):encryption.cpp: undefined reference to `BigInteger::BigInteger(int)'

encryption.o(.text+0x302):encryption.cpp: undefined reference to `operator<<(std::ostream&, BigInteger const&)'

encryption.o(.text$_ZNK10BigIntegermlERKS_[BigInteger::operator*(BigInteger const&) const]+0x63):encryption.cpp: undefined reference to `BigInteger::multiply(BigInteger const&, BigInteger const&)'

Так что мне было интересно, как лучше всего обращаться с действительно большими целыми числами, которые возникают из алгоритма RSA.

Я слышал, что есть возможность объявить ваши переменные как двойные, так что ... 

long long decryptedCharacter;

но я не уверен точно, насколько велико целое число, которое можно хранить.

Ну, например, я пытаюсь скомпилировать и запустить следующую программу, используя dev C ++: 

#include iostream

#include "bigint\BigIntegerLibrary.hh"

using namespace std;

int main()
{
    BigInteger a = 65536;
    cout << (a * a * a * a * a * a * a * a);
    return 0;
}

тогда я получаю эти ошибки.

Дерек, я думал, что, включив файл BigIntegerLibrary.hh, компилятор сможет выполнить все необходимые ему файлы.

Как мне попытаться скомпилировать программу выше для устранения ошибок компоновки?

Ответы [ 16 ]

1 голос
/ 24 сентября 2008

Я добился большого успеха, используя библиотеку LibTomCrypt для своих криптографических нужд. Это быстро, компактно и портативно. Он может сделать ваш RSA за вас, или просто заниматься математикой, если хотите.

1 голос
/ 24 сентября 2008

Замечание: __int64 и long long - это нестандартные расширения. Ни один из них не гарантированно поддерживается всеми компиляторами C ++. C ++ основан на C89 (он вышел в 98 году, поэтому он не мог быть основан на C99)

(C поддерживает 'long long' с C99)

Кстати, я не думаю, что 64-битные целые решают эту проблему.

1 голос
/ 24 сентября 2008

Проверьте документацию вашего компилятора. Некоторые компиляторы имеют определенные типы, такие как __int64, которые дают вам их размер. Может быть, у вас есть некоторые из них в наличии.

1 голос
/ 24 сентября 2008

Длинное int обычно составляет 64 бита, что, вероятно, будет недостаточно для обработки такого большого целого числа. Вам, вероятно, понадобится какая-нибудь библиотека bigint.

См. Также этот вопрос о переполнении стека

0 голосов
/ 18 мая 2009

Я использовал GMP, когда писал реализацию RSA.

0 голосов
/ 24 сентября 2008

Тот факт, что у вас есть проблемы с использованием какой-либо библиотеки biginteger, не означает, что это плохой подход.

Использование long long - определенно плохой подход.

Как уже говорили другие, использование библиотеки biginteger, вероятно, является хорошим подходом, но вы должны опубликовать более подробную информацию о том, как вы используете упомянутую библиотеку, чтобы мы могли помочь Вам устранить эти ошибки.

Страница:
...