При работе с криптографией или с адресами IPv6 часто возникает потребность в арифметике с очень большими числами. В этой статье рассмотрим, как разные библиотеки C/C++ выполняют эту функцию на примере перемножения двух больших чисел и расскажем о ещё одном предложении рабочей группы.
Российская рабочая группа по стандартизации C++ разрабатывает предложения по улучшению работы с языком и выносит их на обсуждении Международного комитета по стандартизации. Уже шесть внесенных рабочей группой предложений приняты и будут внесены в стандарт, ещё 12 находятся на рассмотрении.
OpenSSL
В OpenSSL есть встроенный механизм работы с большими числами. Возвести большое число в квадрат можно так:
#include <climits>
#include <openssl/bn.h>
#include <stdio.h>
int main() {
BN_CTX *ctx = BN_CTX_new(); // контекст для вычислений
BIGNUM *mybignum = nullptr; // число, которое будем умножать
BIGNUM *mul = BN_new(); // результат умножения
BN_dec2bn(&mybignum, "18446744073709551615"); // 2^64-1
BN_mul(mul, mybignum, mybignum, ctx);
// распечатаем результат
char *dec = BN_bn2dec(mul);
if (dec) {
printf("%s\n", dec);
OPENSSL_free(dec);
}
// освободим выделенную память
BN_free(mybignum);
BN_free(mul);
}
Это скорее код на C, а не на C++. От этого работать с ним в среде с исключениями — небезопасно, и грозит утечками памяти.
Gcrypt
Библиотека libgcrypt родилась из проекта GnuPG и предоставляет базовые функции для работы с шифрованием, а в том числе и с большими числами. С этой библиотекой наш пример выглядел бы вот так:
#include <gcrypt.h>
#include <cassert>
int main() {
unsigned long long mybignum = 18446744073709551615ull; // 2^64-1
gcry_mpi_t max_ul = gcry_mpi_new(64); // представление mybignum в формате gcrypt
gcry_mpi_t mul = gcry_mpi_new(128); // результат умножения
// переводим mybignum в формат gcrypt
size_t scanned = 0;
gcry_mpi_scan(&max_ul, GCRYMPI_FMT_USG, &mybignum, sizeof(unsigned long long), &scanned);
assert(scanned==sizeof(unsigned long long) && "failed to scan the whole number");
// умножаем
gcry_mpi_mul(mul, max_ul, max_ul);
// выводим на экран
gcry_mpi_dump(mul);
// освобождаем ресурсы
gcry_mpi_release(mul);
gcry_mpi_release(max_ul);
}
Проблемы всё те же — мы получаем код на C, в котором самому нужно следить за ресурсами.
GMP
Предыдущие две библиотеки были заточены на использование в криптографии. GMP — специализированная библиотека, работающая только с числами. С её помощью возведение в квадрат можно было бы сделать так:
#include <stdio.h>
#include <gmp.h>
int main() {
mpz_t mybignum;
mpz_t mul;
mpz_init_set_str(mybignum, "18446744073709551615", 10);
mpz_init(mul);
mpz_mul(mul, mybignum, mybignum);
gmp_printf("%Zd\n", mul);
// освобождаем память
mpz_clear(mybignum);
mpz_clear(mul);
}
Выглядит уже лучше и понятнее, но это всё ещё код на C.
Boost.Multiprecision
Эта библиотека не реализует арифметику с большими числами сама, а лишь предоставляет удобный C++ интерфейс для работы с ними, используя сторонние библиотеки в качестве backend для вычислений. Насколько интерфейс удобен — судите сами:
#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>
int main() {
using namespace boost::multiprecision;
int128_t mybignum = 18446744073709551615ull;
std::cout << mybignum * mybignum << std::endl;
}
Предложение в стандарт
Использовать сторонние библиотеки для такой часто возникающей задачи затратно как по памяти, так и по производительности. Российские разработчики из Национальной рабочей группы по стандартизации C++ считают так же, поэтому они составили предложение по включению целочисленных типов произвольной ширины в стандартную библиотеку. В нашем случае пример выглядел бы так:
#include <wide_integer>
#include <iostream>
int main() {
auto mybignum = 18446744073709551615_int128;
std::cout << mybignum * mybignum << std::endl;
}
Хотите работать с числами, занимающими мегабайт памяти? Не проблема, вот так например можно подсчитать 100! :
#include <wide_integer>
#include <iostream>
using int_mb = std::wide_int<1024*1024>;
int main() {
int_mb factorial_100 = 1;
for (unsigned i = 2 ; i <= 100; ++i)
factorial_100 *= i;
std::cout << "100! is " << factorial_100 << std::endl;
}
Возможно, мы увидим это предложение в стандартной библиотеке уже в C++23. Прототип доступен по этой ссылке , а самые любопытные могут всегда прочесть самый свежий текст предложения здесь.
Игорь Клевенец, разработчик Яндекса
Антон Полухин, разработчик Яндекс.Такси