征集分布计算项目课题[公告]

cahmill

应该做一个地磁波的

cuihao

让电脑随机输五个字符，看看是China的几率有多大。
（有点没用，但是开始么，先弄个简单的）

(Y)

来说点废话。

一个计算项目，是通过基础数据和算发构成的。
基础数据如果具有分散性和对称性是最好的。就是数据可以相对独立的计算，不发生太多关联，并且这部分数据和那部分数据的算法基本相同。
算法也需要可描述性、简易性和通用性为上。就是算法是被描述明确的，算法的开发过程简单，算法可以被大量任务所使用。
涉及到分布式任务，则算法的分布式逻辑也需要很简单，也就是分布计算后的结果汇总也要易于开发和运行。

目前需要较大计算量的任务一般有数据分析、模型计算、数理计算等等。
数据分析例如天文数据分析，基因数据分析，气候数据分析，股票数据分析等等。这里对数据的要求很高。一般很难拿到专业机构的天文数据和基因数据及气候数据吧。相对来说股票数据的标准化非常好，股票软件都提供标准格式的历史数据下载。原生数据量大，也导致了结果数据量大。

模型计算例如工程计算、分子力学模拟（要不我们来模拟核试验？）、3D渲染等等。但都涉及数据不通用以及算法的独立性。

数理计算似乎最理想了。原生数据量小，有大量的论文来描述算法。但是计算结果不具备商业价值。

可以关注一下每年的全国大学数学建模竞赛的内容，历年来的题目涉及非常广泛，也非常典型。我念书的时候赶上这么几个题目。100万RMB的资金，10中不同的收益和风险的投资项目，如何调节投资比例达到风险更小，收益更高。我那时候用奔腾133算了1个多小时。当投资项目入今天的100中以上，投资金额大到1GRMB以上的时候，的确具备很高的商业价值。原生数据少，通用性好，算法简单。

还有一个是交通路由计算的题目，20个地点之间不同的距离，在完成某个特定的运输任务，寻找成本最底的路径。这个对交通、物流业有非常重大的价值。如果设计全国大部分省的绝大部分市甚至县（公开数据，但整理需要时间。不知道各个交大有没有现成的数据），则计算量非常大。原生数据少，而且通用性也很强，算法可以反复使用。在物资中转地的设定，道路的扩建，降低物流成本方面都有很大的用处。

还有一个简单的石油开采的计算。但我个人认为是糊弄孩子们的，在实际应用中缺乏很多约束关系。
等等之类的项目其实很多。其他的体目我没参加，不太清楚。

可以筛选一下，选择几个适合基于互联网的分布式计算项目。

fwjmath

我已经把n=30的情况做出来了~~~

(Y)

原帖由 fwjmath 于 2008-8-25 11:03 发表
我已经把n=30的情况做出来了~~~

有你这程序，何愁拿不着全国一等奖啊！

fwjmath

我以亲身经历担保这样的程序肯定拿不到省级的奖项。

duligavin

分布式翻译

(Y)

原帖由 fwjmath 于 2008-8-25 16:57 发表
我以亲身经历担保这样的程序肯定拿不到省级的奖项。

看来我还是90年代的老眼光。

chaoge

筛选出某个域上的所有素数阶的椭圆曲线，看看美国鬼子在椭圆曲线密码上捣腾了些什么名堂。

fwjmath

问一下楼上这个有啥学术上的意义么？~~~我对这个不太懂~~~
这个的数据量应该很大~~~不知道分布式计算能不能处理~~~我觉得很难说~~~

chaoge

就是筛出一个指定的有限域上的所有素数阶椭圆曲线，这个难度是有点大，搜索空间也很大。
比如素域F_p，p = 2^192-2^64-1，对[1...p]进行遍历，逐个计算曲线的阶并进行素性判定。
分布式计算，每个节点分配一个搜索区间。

当然，一些优化可在一定程度上缩小搜索区间或加快淘汰速度。比如同伦曲线具有相同的阶，早期淘汰掉非素数阶的曲线等。

目前用来做椭圆曲线密码系统的几条曲线都是美国NIST推荐的，很特别，天晓得有什么机关在里面。
搜出所有素数阶的曲线供大家随机选择，也算是对世界信息安全的一大贡献，也是对社会的一大贡献。

fwjmath

这个我查了一点资料~~~由于曲线实在太多了~~~所以有人建议采用的办法是先随机生成一条曲线然后用SEA算法来计算它的阶~~~这样的话会不会更加实用呢？~~~

chaoge

理论上是可以这样的。换个角度来看，由于计算曲线的阶，或者说筛选曲线，是一套系统，而由曲线做一个密码系统则是另一套。
前者相对耗时一点，它们彼此独立。对于应用来说，一般是先筛一条曲线或者若干曲线出来，然后在应用中注入一条曲线。

曲线的阶计算很复杂，非专业人士很难搞定。这样就导致大量的椭圆曲线密码系统都是建立在NIST推荐的曲线上，也就是说，实际上，对于大部分应用而言，大家没有选择的权利或者说没有选择的机会。如果美国鬼子早已破解了这几条曲线，那么我们的银行，我们的信息安全，，，，不敢想象哈。

所以，我认为筛出10万条曲线供大家选择这类工作还是有意义的。

fwjmath

嗯~~~或许吧~~~这样的话你先要证明你的算法筛选出来的曲线没有统计学特性~~~
筛选一条阶为n的曲线大概需要多少时间？~~~

chaoge

以192比特长度的有限域来看，如果通过了早期淘汰策略的曲线的阶，大约需要60分钟可计算完成，这是对通用版的而言，优化一下可以加快速度。对高度优化过的只需要5分钟，个人认为不是很有必要了。接下来要对曲线的阶进行素性检验，如果是概率检验，则相对比较快。如果用确定性素性检验，采用2000 or 2001年印度两个学生给出的确定性算法，则计算量大，但也同样适合分布式计算。

因此整个工作有两个大计算量的部分：
1） 计算曲线的阶
2）素性检验