Большие числа, общие алгоритмы?

Question

Мне было интересно, что такое большие числа и какие распространенные алгоритмы используются для их обработки. Я слышал, как этот термин упоминается в «Кодировщиках на работе», где в одном из интервью кто-то попросил создать библиотеку для работы с большими числами.

Answer 1

Большие числа обычно представляют собой целые числа или десятичные числа с полной точностью, в отличие от чисел с плавающей запятой (которые могут также хранить очень большие числа, но с очень ограниченной точностью). Они в основном используются в криптографии. Возьмем, к примеру, ключи RSA: это целые числа с 1024 или 2048 битами (примерно 300 или 600 десятичных цифр). Они должны быть длинными, чтобы сделать невозможным взлом шифрования с помощью грубых вычислений.

Библиотеке нужно предоставить поддержку для хранения этих чисел и выполнения с ними вычислений (например, сложение, умножение, целочисленное деление на остальные)

Answer 2

Существуют библиотеки bignum, такие как gmp - некоторые обеспечивают произвольную точность (... настолько, насколько может справиться ваша память), некоторые имеют просто нелепые ограничения - переменные с плавающей запятой с 256-байтовой базой, 256-байтовой мантиссой.

Методы очень похожи на обычную программную эмуляцию FPU, просто итерируя по большему количеству байтов данных для каждого вычисления, операции напоминают то, как вы вычисляете это на бумаге. Если у вас есть 256-байтовое целое число, его можно рассматривать как обычное число из 256 базовых256 цифр ...

простое сложение целых 256-байтовых чисел (полностью неоптимизировано ... числа должны сохранять длину и т. Д.)

unsigned char x[256];
unsigned char y[256];
unsigned char sum[256];
int overflow=0,tmp;
for(unsigned char i=0;i<256;i++)
{
  tmp = x[i] + y[i] + ovr;
  sum[i] = tmp % 256;
  overflow = tmp / 256;
}

Answer 3

Это числа с переменной битовой длиной, в отличие от чисел с предопределенным размером (например, 4-битный целочисленный тип).

Пример быстрой библиотеки C ++, работающей с большими числами, - NTL , также используемой специально для теории чисел и криптографии. Другим известным инструментом является калькулятор unix bc , который по умолчанию работает с неограниченной точностью. Некоторые функциональные языки, такие как Haskell, также используют этот тип чисел.

Примером подходов, используемых для работы с арифметикой большого числа, является Алгоритм Карацубы , используемый для умножения. В документации по NTL вы можете найти гораздо больше, если вам интересно;)