Watch
1
0
Fork
You've already forked bigint
0
mirror of https://codeberg.org/r4gus/bigint.git synced 2026-11-17 03:20:31 +00:00
No description
Find a file
Repository files (latest commit first)
Filename Latest commit message Latest commit date
2026-02-05 00:12:38 +01:00
src added legendre method 2026-02-05 00:12:38 +01:00
.gitignore initial commit 2026-01-31 12:24:37 +01:00
build.zig initial commit 2026-01-31 12:24:37 +01:00
build.zig.zon initial commit 2026-01-31 12:24:37 +01:00
README.md added README 2026-02-03 22:43:49 +01:00

Big Integer Package for Zig

A neither feature complete nor bug free (at least it's very unlikely) big integer package written in Zig.

Memory for integers is always dynamically allocated and must be freed using deinit.

Integer De-/ Serialization

Integers from Strings

To create a new integer from a string one can use the fromStringAlloc function.

const i = try BigInt.fromStringAlloc("0xaabbccdd", 0, allocator);
defer i.deinit(std.testing.allocator);

The first argument is a string representing an integer. Currently, only binary (0b), octal (0o) and hexadecimal (0x) are supported. The second argument is the base. Use 0 if the base should be derived from the string. The third argument is an allocator used to allocate the memory required to store the integer in memory.

Integers to Strings

To serialize a BigInt into a string, use the formatAlloc method.

const str = try i.formatAlloc(16, allocator);
defer allocator.free(str);

The first argument is the base that should be used to format the integer string and the second argument is an allocator used to allocated the memory required for the string.

Arithmetic Operations

Addition

var i1 = try BigInt.fromStringAlloc("-0xd7b3f9b6be6d0ba69561e026d1a71713f000da0eebcdf648d2f3651614f37f04bf", 0, allocator);
defer i1.deinit(allocator);

var i2 = try BigInt.fromStringAlloc("0xd5612187a8fd23f35e21b1f7d63e224244c37658d6e020657c494a59d52e69b1355ee2b3ec44397b67", 0, allocator);
defer i2.deinit(allocator);

// "0xd5612187a8fd23f2866db84117d1169baf619632053909518c48704ae9607368626b7d9dd750ba76a8"
const i3 = try i1.add(i2, std.testing.allocator);
defer i3.deinit(allocator);

Subtraction

var i1 = try BigInt.fromStringAlloc("0xc9f2c9cd04674edea3fffffff", 0, allocator);
defer i1.deinit(allocator);

var i2 = try BigInt.fromStringAlloc("0xab54a98ceb1f0ad2", 0, allocator);
defer i2.deinit(allocator);

// "0xc9f2c9ccf9b20445d54e0f52d"
const i3 = try i1.sub(i2, std.testing.allocator);
defer i3.deinit(allocator);

Multiplication

var i1 = try BigInt.fromStringAlloc("0xd7b3f9b6be6d0ba69561e026d1a71713f000da0eebcdf648d2f3651614f37f04bf", 0, allocator);
defer i1.deinit(allocator);

var i2 = try BigInt.fromStringAlloc("0xd7b3f9b6be6d0ba69561e026d1a71713f000da0eebcdf648d2f3651614f37f04bf", 0, allocator);
defer i2.deinit(allocator);

// "0xb5bfcbf81cfe76f38b3bf893a9c64ec5e31c53f13bfd68c9dcdf25ce3dd5f99ac8b58dd6b4b1a3c0c687c26e1bf4ded1cbee18ee138e28d61a2920f9f3e04f988681"
const i3 = try i1.mul(i2, std.testing.allocator);
defer i3.deinit(allocator);

Division

Division with Remainder

Compared to most other methods divrem will return a tuple consisting of the result of the division and the remainder.

var i1 = try BigInt.fromStringAlloc("0x9f4f2726179a224501d762422c946590d9bb54a98ceb1f0ad2", 0, allocator);
defer i1.deinit(allocator);

var i2 = try BigInt.fromStringAlloc("0x9f4f2726179a224501d762422c946590d90fffffffffffffff", 0, allocator);
defer i2.deinit(allocator);

const res, const rem = try i1.divrem(i2, std.testing.allocator);
defer res.deinit(allocator); // "0x1"
defer rem.deinit(allocator); // "0xab54a98ceb1f0ad3"

Remainder

To calculate only the remainder use the remainder method.

var i1 = try BigInt.fromStringAlloc("0x9f4f2726179a224501d762422c946590d9bb54a98ceb1f0ad2", 0, allocator);
defer i1.deinit(allocator);

var i2 = try BigInt.fromStringAlloc("0x9f4f2726179a224501d762422c946590d90fffffffffffffff", 0, allocator);
defer i2.deinit(allocator);

const rem = try i1.remainder(i2, std.testing.allocator);
defer rem.deinit(allocator); // "0xab54a98ceb1f0ad3"

Modulo

To calculate n mod m where m is the module use the mod method.

var n = try BigInt.fromStringAlloc("-0xab54a98ceb1f0ad2", 0, allocator);
defer n.deinit(allocator);

var m = try BigInt.fromStringAlloc("0xc9f2c9cd04674edea3fffffff", 0, allocator);
defer m.deinit(allocator);

const a = try n.mod(m, std.testing.allocator);
defer a.deinit(allocator); // "0xc9f2c9ccf9b20445d54e0f52d"

Multiplicative Inverse

One can calculate the multiplicative inverse d of a value e where e * d = 1 (mod m) using the mulinv method.

It is important to note that this method will only succeed if e and m do not share a common divisor, i.e. the method will always succeed if one chooses a prime for m.

var e = try BigInt.fromStringAlloc("0x13cb6d5a698890d16746620b38ad51b169dfde8cd89c474c14a98248f794bcba", 0, allocator);
defer e.deinit(allocator);

var m = try BigInt.fromStringAlloc("0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f", 0, allocator);
defer m.deinit(allocator);

const d = try e.mulinv(m, std.testing.allocator);
defer d.deinit(allocator); // "0xf38c3f1da477ede38da56515070d2a6d2d0ff4ae146125caf3115b1e8ded63f"

// e * d = 1 (mod m)