BigInt 5.2.0

BigInt 5.2.0

×

测试已测试✓
语言语言 SwiftSwift
许可证 MIT
发布上次发布2020年9月
SPM支持 SPM✓

由 Károly Lőrentey、The Attaswift 项目、Andrew Hannon、Koray Koska 维护。

BigInt 5.2.0

BigInt

Swift 3 License Platform

Build Status Code Coverage Carthage compatible Version

概述

此仓库提供了在 100% 纯 Swift 中实现的任意宽度的整数类型，其底层表示是基数为 2^64，使用 Array<UInt64>。

当您需要比 UIntMax 更宽的整数字段类型时，它会很有用，但是不想添加 GNU 多精度算术库 作为依赖项。

包含两个大整数字段：BigUInt 和 BigInt（后者为有符号变体）。这两个都是 Swift 结构体，具有写时复制值语义，并且可以像任何其他整数类型一样使用。

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

  • Comparable 和 Hashable 的所有功能

  • 完整的算术运算符集合：+，-，*，/，%，+=，-=，*=，/=，%=

    • 加法 和 减法 变体允许在运行时动态地移动第二个操作数的位数。
    • 无符号减法在结果将小于零时触发中断。（有一些变体会返回溢出标志。）
    • 乘法 对不超过1024位数的数字使用暴力法，然后切换到Karatsuba的递归方法。 (此限制可配置，见 BigUInt.directMultiplicationLimit。)
    • 还提供了可用融合乘加方法和其他特殊情况变体。
    • 除法 使用Knuth的算法D，具有3/2数字宽度的商近似。当除数为零时，将发出错误。
    • BigUInt.divide 同时返回商和余数；这比单独计算它们要快。

  • 位运算符: ~，|，&，^，|=，&=，^=，以及以下只读属性

  • 移位运算符: >>，<<，>>=，<<=

  • 将 NSData 转换为大整数的方法以及 vice versa。

  • 支持生成指定最大宽度或量的随机大整数。

  • 进制转换到/a href="http://attaswift.github.io/BigInt/Extensions/String.html#/s:FE6BigIntSScFTVS_7BigUInt5radixSi9uppercaseSb_SS" rel="nofollow">String和大整数 (big integers)至36进制（使用重复除法）。

    • 大整数用此实现StringLiteralConvertible（以10为基数）。

  • sqrt(n)：整数的平方根（使用牛顿法）。

  • BigUInt.gcd(n, m)：两个整数的最大公约数（Stein算法）。

  • base.power(exponent, modulus)：模指数运算（从右到左的二进制方法）。vanilla指数运算也可用。

  • n.inverse(modulus)：模运算中的乘法逆元素（扩展欧几里得算法）。

  • n.isPrime()：Miller–Rabin素性测试。

实现旨在具有较高的效率，但它们可能根本无法与GMP竞争，即使我在实现与GMP具有相同渐近行为的算法时也是如此。（我尚未进行性能 benchmark 比较过。）

该库有100%的单元测试覆盖率。遗憾的是，这并不表示其中没有bug。

API 文档

生成的API文档可在http://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.0 5.0.0

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

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

设置说明

  • Swift 包管理器：虽然包管理器仍然处于起步阶段，但 BigInt 提供了对它的实验性支持。将此添加到你的 Package.swift 清单的依赖部分

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

  • CocoaPods：在 Podfile 中放置此内容

    pod 'BigInt', '~> 5.0'

  • Carthage：在 Cartfile 中放置此内容

    github "attaswift/BigInt" ~> 5.0

实现说明

BigUInt 是其 64 位数字的 MutableCollectionType，最小的数字位于索引 0。作为一个便利性，BigUInt 允许你使用或高于其 count 的索引来下标。当超出索引范围时，下标操作符 返回 0，并自动在超出索引范围时自动扩展数组。这使内存管理更简单。

BigInt 只是一个围绕 BigUInt 的一个非常小的包装，它包含了 绝对值 和一个 符号位，这两个都可以作为公共的读写属性访问。

为什么没有泛型 BigInt 类型？

由 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位素数。该模块包括一个生成特定大小的随机整数的函数，还包含一个isPrime方法，用于执行Miller-Rabin素性测试。这些就是我们需要的全部。

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

现在去自己玩玩大整数吧！