目录
最近突发奇想，想到自己有几台电脑，性能都不错但是经常闲置，包括实验室的服务器也不是每时每刻都在充分利用资源，因此完全可以跑一些别的程序来利用。我最先想到的就是以前做电脑压力测试的Prime95程序，然后一搜发现这里面还是有不少门道的。本文介绍一下如何利用你家电脑闲置的性能,将其贡献给科学事业，并且在冬天的夜晚让它的散热成为一大取暖来源~哈哈哈哈
GIMPS
我最先测试的程序是Prime95，Prime95是梅森素数搜索计划（Great Internet Mersenne Prime Search, GIMPS）的Windows客户端。这个计划旨在利用互联网的计算资源来寻找梅森素数。形如$2^p-1$（$p$为素数）的数被称为梅森数，如果这个梅森数也是素数那么就被称为梅森素数。梅森素数是目前寻找大素数最高效的目标，人类发现最大的质数前几名都来自于GIMPS发现的梅森素数。
如果有人问：找素数有什么意义？那么请参考下面这段话
I’ve had people ask, “What is the use of running that program and calculating those digits?” and my immediate answer is, “It is of hardly any use.” There is very little prospect of any gain whatsoever. At most, we may learn a little about the behavior and performance of computer processors and hard drives when put under prolonged stress, and we could possibly uncover hardware defects that may otherwise have been overlooked. But otherwise nothing practical will come of it. It will not find treatments for diseases, improve weather modeling, or help predict the stock market.
But if you cannot understand that there is something in man which responds to exploring the unknown in some form and adding to the sum total of human knowledge, then you won’t see why people are running those programs. What we get from this is just the sheer joy of exploration and the possibility of being recorded in history as a record holder. And joy is, after all, the goal of life. We play games, sing songs, and write stories not because we are professional athletes or artists, but because we find them fun to do. We do not live to make money, we make money to be able to live. That is what life means and what life is for.
― MooMoo2 & George Mallory, mersenneforum.org
如果你不想知道很多信息，只想直接开冲，那么你只需要从GIMPS官网下载Prime95（Windows）/ mprime（Linux），解压后双击直接开跑就可以了。如果你希望了解这个程序具体在干什么，或者想青史留名找到新的梅森素数，那么请接着往下读这一节~
PrimeNet
首先需要介绍一下GIMPS的分布式计算网络，名字叫PrimeNet。PrimeNet负责分发计算任务和收集计算结果。由于梅森素数的形式是$2^p-1$，因此PrimeNet中把$p$称为Exponent（指数），验证每个指数对应的梅森数是否为素数是独立的。目前PrimeNet中对于每个指数有如下几种计算任务，括号内为PrimeNet中的缩写：
- Trial Factor (TF): 暴力遍历素数，测试每个素数是否是当前梅森数的因数。
- P-1 Test (PM1): Pollard $p-1$测试法，可以在一定范围内寻找到一个因数$q$，前提是$q-1$是高度复合的（也被称为smooth，意思是由很多很多小的质因数合成的合数）
- P+1 Test (PP1): Williams $p+1$测试法，跟P-1测试类似，但是寻找的因数$q$需满足$q+1$高度复合。
- Lucas-Lehmer Test (LL): 一种验证梅森数是否为质数的算法，该算法虽然很简单，但是非常耗时。
- Double Check (D): 由于计算机在运算过程中可能会非常罕见地产生差错（这也是为什么人们需要ECC内存），因此为了确保素性判断正确，PrimeNet会让另外一台计算机重新计算Lucas-Lehmer，但是使用不同的初始参数，以验证计算的正确性。
- Probable Prime Test (PRP): 这个测试是一种Fermat测试，但是使用了一种改进的验证方法。该算法会在测试过程中生成一个无法仿造的证明文件，这个证明文件可以由另一台计算机很快验证，大大减少了运算量。（但是好像这个算法只能得到Probable Prime，最后的验证应该还是需要使用Lucas-Lehmer）
- Proof Verification (CERT): 即验证PRP生成的证明的任务
除了这些任务之外，PrimeNet还衍生出了因数分解的任务，即尝试对质数验证失败的梅森数进行完整因数分解，在这个过程中也有可能发现非常大的质数，被称为co-factor。因数分解任务有如下两种：
- Elliptic Curve Factorization (ECM): 利用椭圆曲线分解法进行因数分解，可以寻找一定范围以内的因数
- Probable Prime Cofactor Test (PRP-CF): 对于梅森数除去找到的因数还剩下的因数进行素性测试，这个剩下的数通常仍然非常大，因为因数分解的方法通常只能找到几十位的因数，再大的因数实在太难计算了。 目前PrimeNet中因数分解的任务只分配给指数为四千万以下的梅森数。另外，以上这些任务只是大类，实际上PrimeNet中的任务划分更细一点，比如TF会分为普通TF和TF-LMH，后者优先选择TF进展比较小的指数进行分解。
PrimeNet中目前验证一个梅森数的完整流程大概如下：
| |
将验证分为这么多步的原因主要还是为了减少计算量，TF和PM1在测试小因数的时候比较快，而Lucas-Lehmer虽然可以直接测试梅森数的素性，但是用TF和PM1粗筛可以大大减少计算量。这里TF计算的上限和PM1测试的范围都是PrimeNet根据找到因数的概率和计算耗时之间权衡之后算出来的。
在早期PRP证明的算法还没有出现的时候（2020年以前），完整流程实际上是TF -> PM1 -> LL -> DC，因此目前PrimeNet还有大量积攒的LL测试没有被双重验证果，因此目前发现的梅森素数M74207281、M77232917、M82589933的顺位还没有被确定。
PrimeNet的整体进展可以在GIMPS官网的任务分配表中中查看，这个表中展示了每一个范围中指数的状态。
最右边的一大列
Available指的是还没有被认领的任务，右边第二列Assigned指的是已被认领的任务，左边Composite里面F指的是找到因数的梅森数、DC指的是验证过的LL/PRP测试为合数的梅森数，右边Status Unproven中LL/PRP这一列指的是LL测试还没有被验证的指数，ERR指的是LL计算中出现错误的，而NO-LL则是完成了P-1测试后还没有经过LL/PRP测试的指数。
客户端
在了解了计算任务的种类之后，接下来就是选择下载合适的客户端了。GIMPS除了官方的Prime95之外还有不少第三方实现的客户端。如果你想用CPU跑的话，直接使用官方的Prime95/mprime客户端即可；如果你的电脑有GPU，那么你可以选择GPU客户端，比较常用的有mfaktc (NVIDIA) / mfakto (AMD) / gpuowl (通用)。我主要使用的是gpuowl，因为它的代码最近仍然有更新，编译方便，并且支持P-1和PRP测试，而mfaktc和mfakto只能进行TF。不过gpuowl在windows上不太好编译。还有一些其他的GPU客户端，具体可以参考GIMPS论坛的这个介绍贴。
部分客户端的介绍和教程可以参考我之后的一篇博客。
在使用客户端之前，首先可以在GIMPS官网上注册一个账户，这个账户即你在PrimeNet中的账户，在使用客户端的时候把用户名提供给客户端，这样可以让PrimeNet统计你的贡献。PrimeNet的贡献统计以GHz-days（GHD）为单位，每个任务的GHD数值通过一定的公式进行估算的，并不是直接统计你的CPU频率乘上你所花费的时间。据我的经验，如果你想拥有最高的GHD/day，使用CPU和GPU比较划算的都是TF任务。
另外注册账户之后，你还可以选择一个Team加入，这样你的贡献值同样会被计算到Team中。目前我加入的GIMPSChina团队近年的贡献量排名第三，可喜可贺！
关于客户端的使用上，各个客户端基本都是解压之后即可使用，或者编译后使用。使用Prime95客户端的话程序会自动下载新的计算任务，你只需要设置CPU和内存的占用情况即可。如果你要跑TF/DC/PRP任务，那么只需要设置线程数即可，如果要跑PM1，那么需要设置内存上限至少为1G，并且越高越好。内存的设置在菜单里Resource Limit一栏的Advanced项目里面。而用gpuowl的话需要手动申请任务，在Github主页上有说明具体的使用方法。注意新的PrimeNet账户在一段时间（两三天）内是没法提交手动申请任务的结果的，需要管理员审核后才能提交，原因是之前有人恶意提交错误结果，具体情况参见这个GIMPS论坛的帖子。
其他素数寻找项目
GIMPS是最早的互联网寻找素数的项目，后来受GIMPS的影响产生了很多新的项目，例如SRBase，GPU72以及PrimeGrid。SRBase旨在寻找形如$k*b^n\pm 1$的素数，其中$k$为偶数，$b$为基；GPU72旨在利用GPU扩大梅森数的分解范围（提高到10亿，PrimeNet目前只搜索到1亿）；PrimeGrid则是一系列质数寻找项目的集合。这些项目之间通常会相互分享因数分解的结果。另外，在PrimePages网站上有统计目前已知的各个形式的最大质数，在Mersenne.ca网站上有更详细的梅森数计算结果统计。
BOINC
除了GIMPS之外另一个更广为人知的志愿科学计算项目则是伯克利的Berkeley Open Infrastructure for Network Computing (BOINC)。这一项目给科学计算提供了统一的计算分发框架，里面有不少大型合作项目，涵盖数学、物理、天文、生物等多方面。
使用教程
参与BOINC的计算就更加简单了，首先你需要安装一个BOINC客户端，在官网上可以下载到。在安装完成之后，只需要在项目列表里面选择自己喜欢的项目即可参加。通常每个项目都有自己的网站，并且你需要在网站上注册账号，以便于该项目追踪你的贡献，这个步骤在你选择想参加的项目之后会提示你进行操作。参加项目之后，BOINC便会开始自动分配你可以参加的项目。
BOINC客户端同样支持资源占用的限制，并且支持在电脑有操作的时候暂停计算任务，更加便于你利用电脑的空闲时间进行计算了。BOINC相关项目的贡献，除了每个网站自己的统计外，还可以在第三方网站（如Free-DC和BOINCStats）上查到。
GridCoin
另外BOINC还有一个很吸引人的地方是，有一款加密货币叫GridCoin是专门设计用来回报BOINC参与者的。因此如果你参加了GridCoin的计算池，那么你为科学事业贡献的算力实际上也是在挖矿！算力和电力的无用消耗是我不喜欢加密货币，尤其是比特币的最大原因，而设计在BOINC之上的GridCoin则完美解决了这个问题，并且GridCoin基于Proof of Stake，而不是现在比特币和以太坊使用的Proof of Work，更加降低了额外的计算资源消耗。因此如果你愿意参与BOINC的话，可以考虑同时利用GridCoin来回馈自己。
在使用方法上，如果你是首次参加GridCoin，那么你需要利用GridCoin的计算池来进行挖矿，这个模式被称为Pool Crunching，除了安装BOINC之外你还需要在BOINC客户端中选择GridCoin支持的项目管理器（我选择的是grcpool），这样你的计算贡献会被归到GridCoin计算池的名下，而这个计算池会根据你的贡献分配GridCoin。当你有了GridCoin之后你也可以选择独立进行计算而不依赖于计算池，这个被称为Solo Crunching，这个情况下你的计算贡献也会直接被各个项目统计到。具体的使用方法还请参考GridCoin官网
在了解这些的过程中，我还发现了一个聚集了国内志愿计算爱好者的论坛——中国分布式计算论坛，这里面有很多BOINC和GIMPS的贡献者，他们会交流项目参与方法、项目更新等。看到有这么多人愿意给科学事业贡献自己的算力我还是感到很开心的，如果感兴趣的话欢迎加入这些科学计算项目~