找回密码
 新注册用户
搜索
查看: 30977|回复: 58

[项目新闻] [BOINC] [数学类] NFS@Home

[复制链接]
发表于 2009-9-14 21:04:49 | 显示全部楼层 |阅读模式
NFS@Home is a research project that uses Internet-connected computers to do the lattice sieving step in the Number Field Sieve factorization of large integers. You can participate by downloading and running a free program on your computer.

NFS@Home是使用数域筛法(NFS)分解大合数的一个BOINC项目,目前分解的主要是形如a^n-1的数也即Cunningham数,比如现在正在分解的是6^317-1。

项目主页:
http://escatter11.fullerton.edu/nfs/index.php

评分

参与人数 1基本分 +30 维基拼图 +15 收起 理由
霊烏路 空 + 30 + 15

查看全部评分

回复

使用道具 举报

发表于 2009-9-14 21:26:48 | 显示全部楼层
感谢你提供资料,如果楼主能给出更详细的说明,会吸引更多人参与的
回复

使用道具 举报

发表于 2009-9-14 21:31:17 | 显示全部楼层
加入项目失败

2009/9/14 21:30:44                Fetching configuration file from http://escatter11.fullerton.edu/nfs/get_project_config.php
回复

使用道具 举报

发表于 2009-9-14 21:38:09 | 显示全部楼层
哦, 可以加入了
回复

使用道具 举报

发表于 2009-9-14 21:50:55 | 显示全部楼层
差点看成是Need For Speed……

Pinging ter1.fullerton.edu [137.151.45.191] with 32 bytes of data:
Request  ou.
Request  ou.
Request  ou.
Request  ou.

Ping stacs or 137.151.45.191:
    PackSen = 4, Received = 0, Lost = 4 (100% loss),

都是超时……

[ 本帖最后由 ledled 于 2009-9-14 21:57 编辑 ]
回复

使用道具 举报

发表于 2009-9-14 21:55:50 | 显示全部楼层
话说我也看成极品飞车了......
回复

使用道具 举报

发表于 2009-9-14 22:01:21 | 显示全部楼层
官方程序列表里面有 x64 程序。。

但丢给我的是 x86 。。
回复

使用道具 举报

发表于 2009-9-14 22:01:58 | 显示全部楼层

回复 #5 ledled 的帖子

不稳定。。我有时打不开。。有时超快。。
回复

使用道具 举报

发表于 2009-9-14 22:02:53 | 显示全部楼层
貌似这个项目服务器较慢,一直ping不通。
回复

使用道具 举报

发表于 2009-9-14 22:05:52 | 显示全部楼层

回复 #8 BiscuiT 的帖子

已经创建好帐户,第一次见到这么慢的服务器,还以为最慢的就CPDN
回复

使用道具 举报

发表于 2009-9-14 22:16:27 | 显示全部楼层
Snap1.png

wu不算大

停止后进度可以保存
回复

使用道具 举报

 楼主| 发表于 2009-9-14 22:23:03 | 显示全部楼层
我也不知道具体该给出哪些资料,我大致了解的有大数分解目前主要应用在公钥密码方面,
还有这个项目现在使用的方法是SNFS(Special Number Field Sieve)分解比较特殊的一类合数,
而RSA中的那种一般形式的合数需要使用GNFS(General Number Field Sieve),二者的区别主要在多项式的选择不同。

分解的基本思想是寻找整数x和y使得x^2=y^2 (mod n),这里的n是需要分解的合数。
x和y的寻找过程又分一些小的步骤,这里会用到一些数论方面的知识,
开始需选择一个多项式f(x)=x^d + c_{d-1} * x^(d-1) + ... + c_{0}
这里的c_{d-1}表示的是x^(d-1)这一项的系数,c_{0}是常数项。
α是f(x)=0的一个复数根,
定义φ(a_{0}+a_{1} * α + ... + a_{d-1} * α^(d-1)) = a_{0}+a_{1} * m + ... + a_{d-1} * m^(d-1) (mod n)。
可以知道φ是从Z[α]到Z_{n}的同态。
还有一个参数m,使得f(m)=0 (mod n).
由于使用的是SNFS,所以这几个参数实现可以比较简单的求得。
再设
F(x,y)=x^d + c_{d-1} * x^(d-1) * y + ... + c_{0} * y^d
G(x,y)=x - my
寻找向量对(a,b)使得F(a,b)*G(a,b)的所有因子都比较小,
最后寻找到足够多的向量对之后就可以寻找到其中的一些构成集合S,使得
    ∏  (a - b * m) = v^2 (mod n)
(a,b)∈S
以及
f'(α)  *   ∏  (a - b * α) = γ^2
         (a,b)∈S
计算u=φ(γ);
gcd(u-f'(m)*v, n)即可得到n的一个因子。

寻找向量对(a,b)的阶段称作sieve,这个阶段便是SNF@Home所做的。
每个包完成大概需要1个小时,上传的数据在1M左右。
接下来的寻找集合S的过程称作matrix,Square root这个阶段主要就是寻找u和v,
这个过程现在是由Greg完成,
比如刚分解的2,2214L sieve阶段花了大约5天,余下部分花了2天。


项目负责人是Greg Childers,他貌似是一个大学的教授。

评分

参与人数 4基本分 +62 维基拼图 +25 收起 理由
霊烏路 空 + 50 + 25
refla + 5 精品文章
cicikml + 5 感谢分享,楼主辛苦了
cuihao + 2 LZ辛苦了

查看全部评分

回复

使用道具 举报

头像被屏蔽
发表于 2009-9-14 23:38:14 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

发表于 2009-9-15 13:42:24 | 显示全部楼层

回复 #7 BiscuiT 的帖子

64位的计算程序只有Linux的吧
16e Lattice Sieve
平台 版本 发布时间
Microsoft Windows (98 or later) running on an Intel x86-compatible CPU 1.06 10 Sep 2009 4:12:44 UTC
Linux running on an Intel x86-compatible CPU 1.01 27 Jun 2008 21:58:21 UTC
Linux running on an AMD x86_64 or Intel EM64T CPU 1.04 27 Jun 2008 15:38:34 UTC
回复

使用道具 举报

发表于 2009-9-15 13:47:09 | 显示全部楼层

回复 #14 aquarius12 的帖子

哦,win下没有64bit程序。。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 新注册用户

本版积分规则

论坛官方淘宝店开业啦~
欢迎大家多多支持基金会~

Archiver|手机版|小黑屋|中国分布式计算总站 ( 沪ICP备05042587号 )

GMT+8, 2024-3-28 20:59

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表