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

Ошибка в настройках сайта