DOCSEARCHbyAlgolia
Submit Docs

BigInt

repository·master·Indexed 21 days ago

https://github.com/attaswift/bigint

A pure Swift library providing arbitrary-precision integer types, BigInt (signed) and BigUInt (unsigned). Designed as a lightweight, dependency-free alternative to GMP, it features copy-on-write value semantics and supports standard arithmetic, bitwise operations, modular exponentiation, primality testing via Miller–Rabin, and GCD using Stein's algorithm.

Tokens
1.9K
Snippets
4
Records
8
Agent score
24%

What's inside BigInt

  1. Overview of BigInt and BigUInt types

    master

    BigInt provides arbitrary-precision integer types implemented in pure Swift using an Array<UInt64> representation in base $2^{64}$. It is a lightweight alternative to the GNU Multiple Precision Arithmetic Library (GMP).

    There are two primary types:

    • BigUInt: An unsigned big integer.
    • BigInt: A signed big integer.

    Both types are Swift structs with copy-on-write value semantics, allowing them to be used similarly to standard Swift integer types.

  2. How BigUInt indexing and memory management works

    master

    BigUInt is a MutableCollectionType of 64-bit digits, where the least significant digit is at index 0.

    To simplify memory management, BigUInt supports subscripting with indexes at or above its count:

    • Get: Accessing an out-of-bound index returns 0.
    • Set: Setting an out-of-bound index automatically extends the underlying array.

    BigInt (the signed variant) is implemented as a wrapper around a BigUInt absolute value and a sign bit, both of which are accessible as public read-write properties.

  3. Implement RSA cryptography with BigInt

    master

    The BigInt module provides the necessary primitives to implement an RSA cryptography system, including:

    • Prime Generation: Use BigUInt.randomInteger(withExactWidth:) to generate random integers and the .isPrime() method (which performs the Miller–Rabin primality test) to verify primes.
    • Key Generation: Create a public/private keypair using a modulus n (the product of two large primes) and an exponent e. The private exponent d is calculated using the .inverse(phi) method, where phi is (p - 1) * (q - 1).
    • Encryption/Decryption: Use the .power(exponent, modulus:) method to perform modular exponentiation.
    • Data Conversion: BigUInt can be initialized from NSData (e.g., UTF-8 encoded strings) and can be serialized back using .serialize().

    Warning: This is a simplified implementation for educational purposes and should not be used in production cryptography systems.

    // Generating a prime
func generatePrime(_ width: Int) -> BigUInt {
    while true {
        var random = BigUInt.randomInteger(withExactWidth: width)
        random |= BigUInt(1)
        if random.isPrime() {
            return random
        }
    }
}

// RSA Key components
typealias Key = (modulus: BigUInt, exponent: BigUInt)

// Encryption using modular exponentiation
func encrypt(_ message: BigUInt, key: Key) -> BigUInt {
    return message.power(key.exponent, modulus: key.modulus)
}

// Example: Encrypting a string
let secret: BigUInt = BigUInt("Arbitrary precision arithmetic is fun!".dataUsingEncoding(NSUTF8StringEncoding)!)
let cyphertext = encrypt(secret, key: publicKey)

// Decrypting
let plaintext = encrypt(cyphertext, key: privateKey)
let received = String(data: plaintext.serialize(), encoding: NSUTF8StringEncoding)

  4. Install BigInt via Swift Package Manager

    master

    To integrate BigInt into your Swift project, add it as a dependency in your Package.swift manifest. The library provides experimental support for Swift Package Manager.

    Note: BigInt 5.4.0+ requires Swift 5.x. For older Swift versions, refer to the compatibility table in the documentation.

    .package(url: "https://github.com/attaswift/BigInt.git", from: "5.4.0")

  5. Calculate digits of π using a spigot algorithm

    master

    BigInt can be used to implement mathematical algorithms like Jeremy Gibbon's spigot algorithm to generate the digits of π. The algorithm relies on integer arithmetic and can be implemented as an infinite AnyIterator or GeneratorType.

    func digitsOfPi() -> AnyIterator<Int> {
    var q: BigUInt = 1
    var r: BigUInt = 180
    var t: BigUInt = 60
    var i: UInt64 = 2
    return AnyIterator {
        let u: UInt64 = 3 * (3 * i + 1) * (3 * i + 2)
        let y = (q.multiplied(byDigit: 27 * i - 12) + 5 * r) / (5 * t)
        (q, r, t) = (
            10 * q.multiplied(byDigit: i * (2 * i - 1)),
            10 * (q.multiplied(byDigit: 5 * i - 2) + r - y * t).multiplied(byDigit: u),
            t.multiplied(byDigit: u))
        i += 1
        return Int(y[0])
    }
}

  6. Calculate factorials using BigInt

    master

    You can use BigInt to perform high-precision calculations like factorials for any integer. Since BigInt supports arbitrary precision, it can handle the extremely large numbers generated by factorial functions that would overflow standard integer types.

    import BigInt

func factorial(_ n: Int) -> BigInt {
    return (1 ... n).map { BigInt($0) }.reduce(BigInt(1), *)
}

print(factorial(100))
// ==> 93326215443944152681699238856266700490715968264381621468592963895217599993229915...

  7. Core arithmetic and bitwise capabilities

    master

    The library implements a wide range of mathematical operations:

    Arithmetic

    • Standard Operators: +, -, *, /, %, +=, -=, *=, /=, %=.
    • Specialized Subtraction: Variants exist that allow shifting digits of the second operand or returning an overflow flag for unsigned subtraction.
    • Multiplication: Uses brute force for numbers up to 1024 digits, then switches to the Karatsuba recursive method. The limit is configurable via BigUInt.directMultiplicationLimit.
    • Division: Uses Knuth's Algorithm D. BigUInt.divide returns both quotient and remainder simultaneously for better performance.
    • Fused Multiply-Add: A dedicated method for combined operations.

    Bitwise and Shift

    • Bitwise: ~, |, &, ^, |=, &=, ^=.
    • Shifts: >>, <<, >>=, <<=.
    • Properties: bitWidth, trailingZeroBitCount, and leadingZeroBitCount.

    Advanced Mathematics

    • Square Root: sqrt(n) using Newton's method.
    • GCD: BigUInt.gcd(n, m) using Stein's algorithm.
    • Modular Exponentiation: base.power(exponent, modulus).
    • Multiplicative Inverse: n.inverse(modulus) using the extended Euclidean algorithm.
    • Primality Testing: n.isPrime() using the Miller–Rabin test.