algorithm - 大整数的除法(模数)(最多 200 位)

Question

我正在使用 Miller–Rabin primality test 在 Pascal 中编写质数生成器(最多 200 位) .

我已经实现了多个步骤，但我卡在了模幂部分。我选择了 Right-to-left binary method其中(我假设)我必须实现 A mod B，其中 A 和 B 都是(在最坏的情况下为 200 位数字)。为了计算模数，我必须实现最多 200 位的 2 个数字的除法。我在一个数组中表示我的长整数，其中每个元素都是一个数字 (0-9)。

我已经用谷歌搜索了，但没有找到任何适合我的算法(这不会花费很多时间来实现)。所以我想问问有没有人有这方面的经验。我不一定是最快的算法，但它不应该像欧几里德除法那样“愚蠢”，这需要数年时间并且应该很容易实现。我不想使用任何库(纯 pascal)

Answer 1

阅读this answer用于快速乘法和 this page较慢但更容易理解的乘法。阅读this page使用该乘法算法进行快速除法。时间复杂度将与乘法的时间复杂度成正比。