C++ "bitowość" liczb.

Question

Witam,

Czy ktoś z forumowiczów byłby w stanie podpowiedzieć mi w temacie "bitowości" danej liczby ?

np.

#include <iostream>
#include <random>
#include <chrono>

int main()
{
    unsigned long long x_64;
    auto seed = std::chrono.high_resolution_clock::now().time_since_epoch().count();
    std::mt19937_64 mt_rand(seed);
    x_64 = mt_rand();
   return (0);
}

Generuje mi liczbę i zapisuje w zmiennej x_64 = 1974439852404796126

W jaki sposób mogę sprawdzić "bitowość" tej liczby ? 

W jaki sposób zwiększyć ją np do 256 bitów etc?

Korzystałem z mt19937_64 ( _64 czyli 64 bitowy Marsene Twister random number generator) w założeniu liczby generowane są 64 bitowe ale nie do końca rozumie co to oznacza etc...

Z gory dzęki za pomoc.

 

Answer 1

W jaki sposób mogę sprawdzić "bitowość" tej liczby ? 

sizeof zwraca liczbę bajtów danego typu lub wyrażenia, dla przykładu 8*sizeof(int) zwróci ilość bitów typu int.

W zależności od platformy podstawowe typy mogą mieć różną wielkość więc polecam używanie bilbioteki <cstdint> który definiuje typy takie jak: int8_t, int16_t, int32_t, int64_t i wiele więcej. Można łatwo się domyślić że liczba w nazwie tych typów odpowiada za liczbę bitów.

W jaki sposób zwiększyć ją np do 256 bitów etc?

Jeżeli chodzi ci o prosty typ to po prostu nie możesz. GCC dla niektórych platform wspiera typ liczbowy 128 bitowy __int128.

Możesz zaimplementować własny sposób przetrzymawania liczb np. za pomocą ciągów.

Korzystałem z mt19937_64...

Oznacza to tyle że może losować liczby z przedziału [0, 18446744073709551615]

Comments

W ramach uzupełnienia odpowiedzi. Zasadniczo wielkość liczb na których możemy w C++ operować jest ograniczona tylko przez ilość pamięci którą posiadamy: 

http://www.boost.org/doc/libs/1_63_0/libs/multiprecision/doc/html/index.html

---

Cześć,

Dzięki za odpowiedź w temacie.

Na pewno skorzystam/zapoznam się z <cstdint>.

Możesz zaimplementować własny sposób przetrzymawania liczb np. za pomocą ciągów.

Co masz dokładnie na myśli pod pojęciem ciągów ? Mógłbyś rozwinąć ?

Zastanawiam się w jaki sposób np. do kryptografii uzyskuje się klucze np. 2048 bitowe.

 

---

Odradzam używania tego kodu co nabazgrałem, ale dla celów edukacyjnych mniej więcej sie nadaje. Ów program generuje "klucze" publiczny i prywatny mniej więcej 2048 bitowe i używa tych kluczy do szyfracji i deszyfracji losowo wygenerowanej wiadomości.

#include <boost/math/common_factor.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/miller_rabin.hpp>
#include <iostream>

template <typename T>
T mul_inv(T a, T b) {
	T b0 = b, t, q;
	T x0 = 0, x1 = 1;
	if(b == 1) {
		return 1;
	}
	while(a > 1) {
		q = a / b;
		t = b, b = a % b, a = t;
		t = x0, x0 = x1 - q * x0, x1 = t;
	}
	if(x1 < 0) {
		x1 += b0;
	}
	return x1;
}

int main() {
	using namespace boost::random;
	using namespace boost::multiprecision;

	typedef cpp_int int_type;
	mt11213b base_gen(clock());
	independent_bits_engine<mt11213b, 2048, int_type> gen(base_gen);
	mt19937 gen2(clock());

	int_type p1 = 0, p2 = 0;

	for(unsigned i = 0; i < 100000; ++i) {
		int_type n = gen();
		if(miller_rabin_test(n, 25, gen2)) {
			(p1 ? p2 : p1) = n;
			if(p2) {
				break;
			}
		}
	}

	int_type n     = p1 * p2;
	int_type bound = lcm(p1 - 1, p2 - 1);

	int_type e;
	for(unsigned i = 0; i < 100000; ++i) {
		int_type x = gen();
		if(1 < x && x < bound && gcd(x, bound) == 1) {
			e = x;
			break;
		}
	}

	int_type d = mul_inv(e, bound);

	std::cout << "------------------- PRYWATNY" << std::endl;
	std::cout << n << " " << e << std::endl << std::endl;

	std::cout << "------------------- PUBLICZNY" << std::endl;
	std::cout << n << " " << d << std::endl << std::endl;

	std::cout << "------------------- PRZYKLAD" << std::endl;
	int_type msg = gen2();
	std::cout << "wiadomosc\t\t" << msg << std::endl;

	msg = powm(msg, e, n);
	std::cout << "zakodowana wiadomosc\t" << msg << std::endl;

	msg = powm(msg, d, n);
	std::cout << "zdekodowana wiadomosc\t" << msg << std::endl;

	return 1;
}

Odnoście własnej implementacji dużych liczb to możesz trzymać liczbę w postaci tablicy cyfr i wtedy musisz zaimplementować dla tej reprezentacji własną arytmetykę np. dodawanie robisz tak jak ręcznie się dodaje w słupku. Ogólnie nie polecam tego implementować samodzielnie bo jest już dużo tego na internecie i w dużo wydajniejszym wydaniu. Możesz po prostu użyć boosta tak jak napisał Dominik Kołacki.

---

Cześć,

Dzięki za info :)

Na pewno zapoznam się.

Nie udało mi się jeszcze boost'a na Win wgrać ;)