How to handle large integers in C

Question

I want to implement cryptographic algorithms. Therefore, I need a suitable data type for processing integers with a large number of digits.

Many newer languages, such as Java, Python, and Ruby, provide their own ways to do this. However, I program in C, and I was wondering what is the best way and easiest way to implement elementary operations there.

I would like to write it without any external library. I thought of two options:

• Using a char array (e.g. strings that would be good for encryption / decryption keys)
• Using a bit array (I don't know how to do this, but I think it depends on the compiler)

What would you do?

Answer 1

If you are interested in cryptography, then everything should be right. Either you write, test, test, and test for many months ... your own arithmetic functions of a large number, or use the existing library.

It's hard enough to get a cryptogram to work correctly when you know that the methods you use are correct. This is almost impossible if the methods you use have subtle errors.

For cryptography, use GMP and concentrate on cryptography.

If you want to write your own arithmetic package of large quantities, then by all means do it. I did the same, and it is an interesting and rewarding experience. But do not use your own work for something critical.

Answer 2

The obvious choice for me was GMP , whose chief developer Torbjörn Granlund was a member of the Swedish five-person team who won the Simon Singh "Cipher Challenge" in 2000.

According to the website, the code can be used to calculate 1,000,000,000 pi digits in 1957 seconds on an AMD Phenom II 3.2 GHz.

The code has been developed since 1991.

Answer 3

I would first suggest using an existing library.

However, I did this earlier in the past as an experiment. I choose option 2. Representing a value of type "1,000,000,000,000,000,000" as

int array[2] = { 1000000000, 2000000000 } 

and performs operations and transfers values ​​one int at a time. Not very effective, but functional sound.

Answer 4

An array of characters will be easier to handle. Its a good idea to create your own class (/ data type), defining functions for working with all arithmetic operations for future use. You can use this one developed by ACRush for reference.

Answer 5

a variable in the main function can store even 100 factorials in C ++

 #include <iostream> #include <cstdio> #include <vector> #include <cstring> #include <string> #include <map> #include <functional> #include <algorithm> #include <cstdlib> #include <iomanip> #include <stack> #include <queue> #include <deque> #include <limits> #include <cmath> #include <numeric> #include <set> using namespace std; //template for BIGINIT // base and base_digits must be consistent const int base = 10; const int base_digits = 1; struct bigint { vector<int> a; int sign; bigint() : sign(1) { } bigint(long long v) { *this = v; } bigint(const string &s) { read(s); } void operator=(const bigint &v) { sign = v.sign; a = va; } void operator=(long long v) { sign = 1; if (v < 0) sign = -1, v = -v; for (; v > 0; v = v / base) a.push_back(v % base); } bigint operator+(const bigint &v) const { if (sign == v.sign) { bigint res = v; for (int i = 0, carry = 0; i < (int) max(a.size(), vasize()) || carry; ++i) { if (i == (int) res.a.size()) res.a.push_back(0); res.a[i] += carry + (i < (int) a.size() ? a[i] : 0); carry = res.a[i] >= base; if (carry) res.a[i] -= base; } return res; } return *this - (-v); } bigint operator-(const bigint &v) const { if (sign == v.sign) { if (abs() >= v.abs()) { bigint res = *this; for (int i = 0, carry = 0; i < (int) vasize() || carry; ++i) { res.a[i] -= carry + (i < (int) vasize() ? va[i] : 0); carry = res.a[i] < 0; if (carry) res.a[i] += base; } res.trim(); return res; } return -(v - *this); } return *this + (-v); } void operator*=(int v) { if (v < 0) sign = -sign, v = -v; for (int i = 0, carry = 0; i < (int) a.size() || carry; ++i) { if (i == (int) a.size()) a.push_back(0); long long cur = a[i] * (long long) v + carry; carry = (int) (cur / base); a[i] = (int) (cur % base); //asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base)); } trim(); } bigint operator*(int v) const { bigint res = *this; res *= v; return res; } friend pair<bigint, bigint> divmod(const bigint &a1, const bigint &b1) { int norm = base / (b1.a.back() + 1); bigint a = a1.abs() * norm; bigint b = b1.abs() * norm; bigint q, r; qaresize(aasize()); for (int i = aasize() - 1; i >= 0; i--) { r *= base; r += aa[i]; int s1 = rasize() <= basize() ? 0 : ra[basize()]; int s2 = rasize() <= basize() - 1 ? 0 : ra[basize() - 1]; int d = ((long long) base * s1 + s2) / baback(); r -= b * d; while (r < 0) r += b, --d; qa[i] = d; } q.sign = a1.sign * b1.sign; r.sign = a1.sign; q.trim(); r.trim(); return make_pair(q, r / norm); } bigint operator/(const bigint &v) const { return divmod(*this, v).first; } bigint operator%(const bigint &v) const { return divmod(*this, v).second; } void operator/=(int v) { if (v < 0) sign = -sign, v = -v; for (int i = (int) a.size() - 1, rem = 0; i >= 0; --i) { long long cur = a[i] + rem * (long long) base; a[i] = (int) (cur / v); rem = (int) (cur % v); } trim(); } bigint operator/(int v) const { bigint res = *this; res /= v; return res; } int operator%(int v) const { if (v < 0) v = -v; int m = 0; for (int i = a.size() - 1; i >= 0; --i) m = (a[i] + m * (long long) base) % v; return m * sign; } void operator+=(const bigint &v) { *this = *this + v; } void operator-=(const bigint &v) { *this = *this - v; } void operator*=(const bigint &v) { *this = *this * v; } void operator/=(const bigint &v) { *this = *this / v; } bool operator<(const bigint &v) const { if (sign != v.sign) return sign < v.sign; if (a.size() != vasize()) return a.size() * sign < vasize() * v.sign; for (int i = a.size() - 1; i >= 0; i--) if (a[i] != va[i]) return a[i] * sign < va[i] * sign; return false; } bool operator>(const bigint &v) const { return v < *this; } bool operator<=(const bigint &v) const { return !(v < *this); } bool operator>=(const bigint &v) const { return !(*this < v); } bool operator==(const bigint &v) const { return !(*this < v) && !(v < *this); } bool operator!=(const bigint &v) const { return *this < v || v < *this; } void trim() { while (!a.empty() && !a.back()) a.pop_back(); if (a.empty()) sign = 1; } bool isZero() const { return a.empty() || (a.size() == 1 && !a[0]); } bigint operator-() const { bigint res = *this; res.sign = -sign; return res; } bigint abs() const { bigint res = *this; res.sign *= res.sign; return res; } long long longValue() const { long long res = 0; for (int i = a.size() - 1; i >= 0; i--) res = res * base + a[i]; return res * sign; } friend bigint gcd(const bigint &a, const bigint &b) { return b.isZero() ? a : gcd(b, a % b); } friend bigint lcm(const bigint &a, const bigint &b) { return a / gcd(a, b) * b; } void read(const string &s) { sign = 1; a.clear(); int pos = 0; while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) { if (s[pos] == '-') sign = -sign; ++pos; } for (int i = s.size() - 1; i >= pos; i -= base_digits) { int x = 0; for (int j = max(pos, i - base_digits + 1); j <= i; j++) x = x * 10 + s[j] - '0'; a.push_back(x); } trim(); } friend istream& operator>>(istream &stream, bigint &v) { string s; stream >> s; v.read(s); return stream; } friend ostream& operator<<(ostream &stream, const bigint &v) { if (v.sign == -1) stream << '-'; stream << (vaempty() ? 0 : vaback()); for (int i = (int) vasize() - 2; i >= 0; --i) stream << setw(base_digits) << setfill('0') << va[i]; return stream; } static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) { vector<long long> p(max(old_digits, new_digits) + 1); p[0] = 1; for (int i = 1; i < (int) p.size(); i++) p[i] = p[i - 1] * 10; vector<int> res; long long cur = 0; int cur_digits = 0; for (int i = 0; i < (int) a.size(); i++) { cur += a[i] * p[cur_digits]; cur_digits += old_digits; while (cur_digits >= new_digits) { res.push_back(int(cur % p[new_digits])); cur /= p[new_digits]; cur_digits -= new_digits; } } res.push_back((int) cur); while (!res.empty() && !res.back()) res.pop_back(); return res; } typedef vector<long long> vll; static vll karatsubaMultiply(const vll &a, const vll &b) { int n = a.size(); vll res(n + n); if (n <= 32) { for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) res[i + j] += a[i] * b[j]; return res; } int k = n >> 1; vll a1(a.begin(), a.begin() + k); vll a2(a.begin() + k, a.end()); vll b1(b.begin(), b.begin() + k); vll b2(b.begin() + k, b.end()); vll a1b1 = karatsubaMultiply(a1, b1); vll a2b2 = karatsubaMultiply(a2, b2); for (int i = 0; i < k; i++) a2[i] += a1[i]; for (int i = 0; i < k; i++) b2[i] += b1[i]; vll r = karatsubaMultiply(a2, b2); for (int i = 0; i < (int) a1b1.size(); i++) r[i] -= a1b1[i]; for (int i = 0; i < (int) a2b2.size(); i++) r[i] -= a2b2[i]; for (int i = 0; i < (int) r.size(); i++) res[i + k] += r[i]; for (int i = 0; i < (int) a1b1.size(); i++) res[i] += a1b1[i]; for (int i = 0; i < (int) a2b2.size(); i++) res[i + n] += a2b2[i]; return res; } bigint operator*(const bigint &v) const { vector<int> a6 = convert_base(this->a, base_digits, 6); vector<int> b6 = convert_base(va, base_digits, 6); vll a(a6.begin(), a6.end()); vll b(b6.begin(), b6.end()); while (a.size() < b.size()) a.push_back(0); while (b.size() < a.size()) b.push_back(0); while (a.size() & (a.size() - 1)) a.push_back(0), b.push_back(0); vll c = karatsubaMultiply(a, b); bigint res; res.sign = sign * v.sign; for (int i = 0, carry = 0; i < (int) c.size(); i++) { long long cur = c[i] + carry; res.a.push_back((int) (cur % 1000000)); carry = (int) (cur / 1000000); } res.a = convert_base(res.a, 6, base_digits); res.trim(); return res; } }; //use : bigint var; //template for biginit over int main() { bigint var=10909000890789; cout<<var; return 0; }