目前gnfs的整个五步中，筛法最重要，但是ggnfs和msieve都没有实现用GPU做筛法。

前期准备，多项式测试：
(1)poly select (<5%)  

gnfs的主体工作，多机分布式筛法：
(2)sieve (~90%)

单机后期处理：
(3)relations filter (<0.5%)
(4)Linear algebra 或者称之为 matrix slover (~5%)
(5)square root (<0.5%)

msieve 的GPU (NV CUDA verison)只局限于第一步poly select，工作量5%的一步。
msieve的筛法很慢，不支持lattice sieve（格子筛法）,也就没法分布式运算。

90%以上的工作量， 还得靠ggnfs lattice sieve 完成。虽然不支持GPU，但是格子筛法天然支持分布式，也不错了。

与性能相关的最重要的两步：
STEP 1: Polynomial Selection 多项式选取
STEP 2: Sieving 筛法

STEP 1， 关于多项式选取：
ggnfs原本的Polynomial Selection采用的是Murphy-Montgomery 算法。
后来加入Thorsten Kleinjung的改正算法pol51，效果改善很多。

STEP 2， 关于二维格子筛法：
在格子筛法方面，它包含Franke改进的lattice sieve，lasieve筛法天然支持分布式运算。
gnfs-lasieve4L1ne 分别对应不同digits的gnfs(~1n0 digits)，酌情选择。
可以用多台机器，分布式筛，每台机器可以多进程（可以手工分片，进程间不需要通信）。
筛完了再一起收集。

poly select方法仍在不断改进中：
1999年分解RSA 140(463 bit),155(512 bit)提出来的多项式选取方法,这个方法由
Peter Montgomery和Brian Murphy合作的，详见Murphy的博士论文（144页）。
edbK9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8Y4N6%4N6#2)9J5k6h3#2S2N6r3S2K6i4K6u0W2j5h3&6#2i4K6u0W2k6h3c8#2i4K6u0W2j5i4g2Q4x3V1k6Q4y4@1g2T1M7X3g2F1N6q4)9J5c8Y4m8V1i4K6u0r3e0i4g2J5M7r3S2&6i4K6u0V1N6r3S2W2M7$3W2K6i4K6u0W2M7r3c8X3
B. A. Murphy
Polynomial selection for the Number Field Sieve Integer Factorisation Algorithm,
Ph.D. thesis, The Australian National University, 1999.

接下来几年，其他人提出的poly select基本上都是基于Murphy的改进。
ggnfs里面的pol51号称最快，是Thorsten Kleinjung改进的。
RSA-576与RSA-640，自德国的Bahr、Boehm、Franke、Thorsten Kleinjung完成。

RSA-768, 还是Thorsten Kleinjung等人主导完成的。论文上Thorsten Kleinjung的名字排在第一。

特别说明的是， 大型gnfs分解项目是系统工程。不是拍脑袋就能算出来的。
后期巨大的Matrix Solver非常头疼。不但人力，而且硬件消耗的电量也是惊人的。
分解RSA-768，长达年余，不同国家的几个实验室参与sieve。电费超过10万美元。
研究团队有荷兰与瑞士政府科学研究基金的资助。

如果目前要分解RSA-1024，没有足够的经费，人力，硬件，是不可能实现的。
普通人根本没有在supercomputer上实践的机会。

将来，技术发展了，就另当别论。

desktop PC用户，能分解到RSA -600 bits左右。莫斯科大学2010年有人分解596 bits （C180）。
后期处理Matrix用到 契比雪夫 超级计算机。
Factorization of RSA-180
S. A. Danilov, I. A. Popovyan   Moscow State University, Russia May 9, 2010∗

We used freely available open source tools to factor RSA-180 on 3 Intel Core i7
PCs and the supercomputer SKIF MSU ‘Chebyshov’.

大概明白你的意思...我再消化消化~
目前的工作只有5%可以用GPU加速，这个确实太少了，简直可以说微不足道。ggnfs的lattice sieve既然能分布式运算，那么就说明这个步骤是可以拆分为多个子单元并行完成的，彼此之间没有顺序和因果关系。理论上，只要能够PC机并行，采用GPU片内并行运算就是可行的。

不过，还得看看具体算法，研究下为什么目前市面上还没有针对lattice sieve的GPU算法。或许加速比不高？所以没有广泛采用吧。

如果针对lattice sieve的GPU算法能加速10倍即可(9800GT：core i5)，因为现在的NV460/480，或ATI 59xx，都比9800GT快N倍了。到时候1块GPU，12小时内破512bits应该没有问题。

不能瞎乐观，大跃进放卫星，不可行。

gnfs因为算法复杂，不能做到自动化生产线，一头进猪肉，一头出香肠那种。它的计算过程需要人工判断，出错的话，要能够解决。前面的步骤没有完成，后面的步骤就无法继续。

其次，sieve只是主要工作。如果sieve提升了，poly select和matrix slover反而成重头了。
实际上sieve都没多少人研究了，人们研究得较多是poly select和matrix slover。
因为随着N增大，sieve并没多少变化。而poly select和matrix slover都会变得异常复杂。

对于gnfs 512:
1.
poly select，如果用GPU， 10 小时足够; 不用GPU， 4 cores * 12 hours 也足够了。
2.
sieve 统计数据得出大约相当于4000MIPS - 5000 MIPS年,要看Poly 的选择是否优秀。
用PC的话，core2duo 3GHz， 1 core * 3000 hours。有50 cpu cores， 2.5 days就足够了。
3.
Matirx Slover，相当于 24 - 35  hours * 8 cores。视Matrix Size 1.1 - 1.4 G不等。
算法复杂，可并行，内存消耗大。目前只能用CPU。

filtering, sqrt 都是2小时以内就能完成的，改进也改进不了多少。

sieve那步用上GPU，取代50 cpu cores，合计大约4-5天。

目前 lattice sieve 无法用GPU操作，主要原因是GPU的内存不够。
gnfs c154-c155: (512 bit)
lpba/lpbr 29,
factor base 30,000,000
以每一个siever消耗的内存120M计算。
一个GPU如果有128 cores， 如果全部跑siever，那么siever消耗 128 * 120MB = 15 GB RAM。
GPU没有这么大的内存。

所以目前gnfs, sieve这步，还得靠大量PC做分布式运算。

这也是为什么分解RSA-768，数个国家的人员合作，多个实验室，用数百台PC，sieve了大约20个月。 而没有采用一块GPU的原因。
对一个大型团队来说，编程不是难题，他们没采用GPU，根本原因是硬件上不可行。

(对比，椭圆曲线离散对数问题ECDLP的rho法对内存消耗量很少，可以用GPU)

543K9s2c8@1M7s2y4Q4x3@1q4Q4x3V1k6Q4x3V1k6V1L8$3y4#2L8h3g2F1N6s2y4Q4x3X3g2W2M7r3k6D9i4K6u0W2j5$3S2Q4x3V1k6#2M7$3g2J5M7#2)9J5c8X3I4Q4x3V1k6D9k6g2)9J5c8X3I4W2L8Y4y4@1M7X3q4Q4x3V1k6H3N6h3u0D9K9h3y4Q4x3V1k6H3j5i4m8W2M7Y4y4Q4x3V1k6J5M7$3p5%4y4U0S2Q4x3X3g2@1P5s2b7`.

[Sieving]
We started sieving in August 2007 and stopped in April 2009.

Environment:
     We used various PCs and clusters at BSI, CWI, EPFL, INRIA (Institut
     National de Recherche en Informatique et en Automatique, France),
     NTT (Nippon Telegraph & Telephone, Japan), the University of Bonn,
     EGEE (Enabling Grids for E-sciencE), AC3 (The Australian Centre for
     Advanced Computing and Communications), and PCs in the United Kingdom.

Time:
     Total sieving time is scaled to about 1500 AMD64 years.

目前GPU内存肯定比不上PC内存廉价，现在一个普通的服务器有64GB内存很常见；却没有哪块独立显卡的GPU有这么大内存。不过，如果GPU可以直接访问全部的主内存，那就可以用GPU计算了。

但是gnfs 768， 1024这些，因为factor base, lpba/lpbr增大，每个sieve的内存也将更大。
768每个siever需要2GB RAM。1024就更大了。100核跑下来， RAM就不够了。

GPU纯粹靠many cores取胜，GPU通常有几百个核，CPU通常只有几个核到十几个核。目前GPU，单core远不如CPU。 sieve因为每个核都要那么大内存。

内存要消耗在GPU上不划算，不如直接用CPU。

楼上在这方面的经验真不少，很难得！
如果有时间，readyu能否给国内的爱好者写一份小规模PC机破解RSA（155,210...）的指南？
我想你在实验中肯定遇到过很多很多问题，解决这些问题肯定花费了不少时间。
为了能让国内玩家快速上手，少走弯路，希望日后有时间的话，能总结下平时你破解时遇到的问题和经验，包括软件的配置，硬件的参数设置等等。多谢！

我只知道有人做过，而且可以通过多线程并行快速实现，具体的不太了解。
希望大家能够早日实现。