BigInt

Swift

概述

本仓库提供了 任意宽度的整数类型，使用 100% 纯 Swift 实现。 底层表示形式采用以 2^64 为基数，使用 Array<UInt64>。

当您需要比 UIntMax 更宽的整数类型，但不希望添加 GNU 多精度算术库 作为依赖项时，此模块非常方便。

包含两种大整数类型：BigUInt 和 BigInt，后者是有符号变体。 这两者都是 Swift 结构体，具有写时复制的值语义，它们的使用方式与任何其他整数类型非常相似。

该库提供了大整数上最常用的一些函数的实现，包括：

这些实现旨在具有合理的效率，但即使我碰巧实现了与 GMP 具有相同渐近行为的算法，它们也不太可能在任何方面与 GMP 竞争。（尽管我还没有进行比较基准测试。）

该库具有 100% 的单元测试覆盖率。 可惜这并不意味着其中没有错误。

API 文档

生成的 API 文档可在 https://attaswift.github.io/BigInt/ 获得。

许可证

BigInt 可以在 MIT 许可证下使用、分发和修改。

要求和集成

BigInt 4.0.0 需要 Swift 4.2（最后一个支持 Swift 3.x 的版本是 BigInt 2.1.0。最后一个支持 Swift 2 的版本是 BigInt 1.3.0。）

Swift 版本 最新的 BigInt 版本
3.x 2.1.0
4.0 3.1.0
4.2 4.0.0
5.x 5.4.0

BigInt 部署到 macOS 10.10、iOS 9、watchOS 2 和 tvOS 9。它仅在最新的操作系统版本上进行了测试——但是，由于该模块使用的平台提供的 API 非常少，因此早期版本的问题应该很少。

BigInt 不使用特定于 Apple 平台的 API，因此应该很容易将其移植到其他操作系统。

设置说明

实现说明

BigUInt 是其 64 位数字的 MutableCollectionType，最低有效位位于索引 0 处。 为了方便起见，BigUInt 允许您使用其 count 处或之上的索引来对其进行下标运算。 下标运算符 对越界 get 返回 0，并在越界 set 上自动扩展数组。 这使得内存管理更简单。

BigInt 只是一个围绕 BigUInt [绝对值][大小] 和 符号位 的小型包装器，这两个都可以作为公共读写属性访问。

为什么没有通用的 BigInt<Digit> 类型？

BigInt 提供的类型不是参数化的——这是非常有意的，因为在这种用例中，Swift 泛型在运行时会给我们带来很大的代价。 在我尝试的每一种方法中，使任意精度算术运算与通用 Digit 类型参数一起工作都会导致代码速度慢了整整 十倍。 如果您可以在不产生如此巨大的性能损失的情况下使算法通用化，请请启发我！

这是我计划进一步研究的一个领域，因为拥有任意宽度算术运算的通用实现将很有用。（多项式除法和十进制基数是两个例子。）该库已经将双位乘法和除法实现为协议上的扩展方法，并具有关联的类型要求； 这并没有明显影响性能。 不幸的是，对于 BigUInt 的方法来说，情况并非如此。

当然，作为最后的手段，我们可以简单地复制代码来创建一个单独的通用变体，该变体速度较慢但更灵活。

计算示例

必须有的阶乘演示

很容易使用 BigInt 计算任何整数的阶乘函数

import BigInt

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

print(factorial(10))
==> 362880

print(factorial(100))
==> 93326215443944152681699238856266700490715968264381621468592963895217599993229915
    6089414639761565182862536979208272237582511852109168640000000000000000000000

print(factorial(1000))
==> 40238726007709377354370243392300398571937486421071463254379991042993851239862902
    05920442084869694048004799886101971960586316668729948085589013238296699445909974
    24504087073759918823627727188732519779505950995276120874975462497043601418278094
    64649629105639388743788648733711918104582578364784997701247663288983595573543251
    31853239584630755574091142624174743493475534286465766116677973966688202912073791
    43853719588249808126867838374559731746136085379534524221586593201928090878297308
    43139284440328123155861103697680135730421616874760967587134831202547858932076716
    91324484262361314125087802080002616831510273418279777047846358681701643650241536
    91398281264810213092761244896359928705114964975419909342221566832572080821333186
    11681155361583654698404670897560290095053761647584772842188967964624494516076535
    34081989013854424879849599533191017233555566021394503997362807501378376153071277
    61926849034352625200015888535147331611702103968175921510907788019393178114194545
    25722386554146106289218796022383897147608850627686296714667469756291123408243920
    81601537808898939645182632436716167621791689097799119037540312746222899880051954
    44414282012187361745992642956581746628302955570299024324153181617210465832036786
    90611726015878352075151628422554026517048330422614397428693306169089796848259012
    54583271682264580665267699586526822728070757813918581788896522081643483448259932
    66043367660176999612831860788386150279465955131156552036093988180612138558600301
    43569452722420634463179746059468257310379008402443243846565724501440282188525247
    09351906209290231364932734975655139587205596542287497740114133469627154228458623
    77387538230483865688976461927383814900140767310446640259899490222221765904339901
    88601856652648506179970235619389701786004081188972991831102117122984590164192106
    88843871218556461249607987229085192968193723886426148396573822911231250241866493
    53143970137428531926649875337218940694281434118520158014123344828015051399694290
    15348307764456909907315243327828826986460278986432113908350621709500259738986355
    42771967428222487575867657523442202075736305694988250879689281627538488633969099
    59826280956121450994871701244516461260379029309120889086942028510640182154399457
    15680594187274899809425474217358240106367740459574178516082923013535808184009699
    63725242305608559037006242712434169090041536901059339838357779394109700277534720
    00000000000000000000000000000000000000000000000000000000000000000000000000000000
    00000000000000000000000000000000000000000000000000000000000000000000000000000000
    00000000000000000000000000000000000000000000000000000000000000000000000000000000
    00000

好吧，我想这还不错，但不是很令人兴奋。 让我们尝试一些更有用的东西。

RSA 加密

BigInt 模块提供了实现（过于）简单的 RSA 加密系统的所有必要部分。

让我们从一个简单的函数开始，该函数生成一个随机的 n 位素数。 该模块包含一个生成特定大小的随机整数的函数，以及一个执行 Miller-Rabin 素性测试的 isPrime 方法。 这些都是我们需要的

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

let p = generatePrime(1024)
==> 13308187650642192396256419911012544845370493728424936791561478318443071617242872
    81980956747087187419914435169914161116601678883358611076800743580556055714173922
    08406194264346635072293912609713085260354070700055888678514690878149253177960273
    775659537560220378850112471985434373425534121373466492101182463962031

let q = generatePrime(1024)
==> 17072954422657145489547308812333368925007949054501204983863958355897172093173783
    10108226596943999553784252564650624766276133157586733504784616138305701168410157
    80784336308507083874651158029602582993233111593356512531869546706885170044355115
    669728424124141763799008880327106952436883614887277350838425336156327

太棒了！ 现在我们有了两个大的素数，我们可以从中生成 RSA 公钥/私钥对。

typealias Key = (modulus: BigUInt, exponent: BigUInt)

let n = p * q
==> 22721008120758282530010953362926306641542233757318103044313144976976529789946696
    15454966720907712515917481418981591379647635391260569349099666410127279690367978
    81184375533755888994370640857883754985364288413796100527262763202679037134021810
    57933883525572232242690805678883227791774442041516929419640051653934584376704034
    63953169772816907280591934423237977258358097846511079947337857778137177570668391
    57455417707100275487770399281417352829897118140972240757708561027087217205975220
    02207275447810167397968435583004676293892340103729490987263776871467057582629588
    916498579594964478080508868267360515953225283461208420137

let e: BigUInt = 65537
let phi = (p - 1) * (q - 1)
let d = e.inverse(phi)!     // d * e % phi == 1
==> 13964664343869014759736350480776837992604500903989703383202366291905558996277719
    77822086142456362972689566985925179681282432115598451765899180050962461295573831
    37069237934291884106584820998146965085531433195106686745474222222620986858696591
    69836532468835154412554521152103642453158895363417640676611704542784576974374954
    45789456921660619938185093118762690200980720312508614337759620606992462563490422
    76669559556568917533268479190948959560397579572761529852891246283539604545691244
    89999692877158676643042118662613875863504016129837099223040687512684532694527109
    80742873307409704484365002175294665608486688146261327793

let publicKey: Key = (n, e)
let privateKey: Key = (n, d)

在 RSA 中，模幂运算用于加密（和解密）消息。

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

让我们通过将字符串转换为 UTF-8、将生成的二进制表示形式解释为大整数并使用公钥对其进行加密来尝试一下我们的新密钥对。 BigUInt 有一个接受 NSData 的初始化器，所以这很容易做到

let secret: BigUInt = BigUInt("Arbitrary precision arithmetic is fun!".dataUsingEncoding(NSUTF8StringEncoding)!)
==> 83323446846105976078466731524728681905293067701804838925389198929123912971229457
    68818568737

let cyphertext = encrypt(secret, key: publicKey)
==> 95186982543485985200666516508066093880038842892337880561554910904277290917831453
    54854954722744805432145474047391353716305176389470779020645959135298322520888633
    61674945129099575943384767330342554525120384485469428048962027149169876127890306
    77028183904699491962050888974524603226290836984166164759586952419343589385279641
    47999991283152843977988979846238236160274201261075188190509539751990119132013021
    74866638595734222867005089157198503204192264814750832072844208520394603054901706
    06024394731371973402595826456435944968439153664617188570808940022471990638468783
    49208193955207336172861151720299024935127021719852700882

好吧，它看起来加密得很对，但是我们能找回原始消息吗？ 从理论上讲，使用私钥加密密文会返回原始消息。 让我们看看

let plaintext = encrypt(cyphertext, key: privateKey)
==> 83323446846105976078466731524728681905293067701804838925389198929123912971229457
    68818568737

let received = String(data: plaintext.serialize(), encoding: NSUTF8StringEncoding)
==> "Arbitrary precision arithmetic is fun!"

耶！ 这真是太棒了，但请不要在实际的加密系统中使用此示例代码。 RSA 有很多微妙的（以及一些不太微妙的）复杂性，为了保持本示例的简短，我们忽略了这些复杂性。

计算 π 的位数

使用 BigInt 尝试的另一个有趣的活动是生成 π 的数字。 让我们尝试实现 Jeremy Gibbon 的 spigot 算法。 就 π 生成器而言，这是一种相当慢的算法，但它可以弥补它的趣味性因素：它非常短，仅使用（大）整数算术，并且每次迭代都会在 π 的十进制表示中生成一个新数字。 这自然导致实现为无限 GeneratorType

func digitsOfPi() -> AnyGenerator<Int> {
    var q: BigUInt = 1
    var r: BigUInt = 180
    var t: BigUInt = 60
    var i: UInt64 = 2 // Does not overflow until digit #826_566_842
    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])
    }
}

好吧，这出乎意料地容易。 但是它有效吗？ 当然可以！

var digits = "π ≈ "
var count = 0
for digit in digitsOfPi() {
    assert(digit < 10)
    digits += String(digit)
    count += 1
    if count == 1 { digits += "." }
    if count == 1000 { break }
}

digits
==> π ≈ 3.14159265358979323846264338327950288419716939937510582097494459230781640628
    62089986280348253421170679821480865132823066470938446095505822317253594081284811
    17450284102701938521105559644622948954930381964428810975665933446128475648233786
    78316527120190914564856692346034861045432664821339360726024914127372458700660631
    55881748815209209628292540917153643678925903600113305305488204665213841469519415
    11609433057270365759591953092186117381932611793105118548074462379962749567351885
    75272489122793818301194912983367336244065664308602139494639522473719070217986094
    37027705392171762931767523846748184676694051320005681271452635608277857713427577
    89609173637178721468440901224953430146549585371050792279689258923542019956112129
    02196086403441815981362977477130996051870721134999999837297804995105973173281609
    63185950244594553469083026425223082533446850352619311881710100031378387528865875
    33208381420617177669147303598253490428755468731159562863882353787593751957781857
    780532171226806613001927876611195909216420198

现在去体验一下大整数运算的乐趣吧！