Abstract:

Bernstein’s Batch-factor algorithm can test B-smoothness of a lot of integers in a short time. But this method costs so much memory that it’s widely used in theory analyses but rarely used in practice. Based on splitting product of primes into pieces, a hierarchical batch-factor algorithm cloud framework was proposed to solve this problem. This hierarchical framework made the development clear and easy, and could be easily moved to other architectures; Cloud computing framework borrowed from MapReduce made use of services provided by cloud clients such as distribute memory, share memory and message to carry out mapping of splitting-primes batch factor algorithm, which solved the great cost of Bernstein’s method. Experiments show that, this framework is with good scalability and can be adapted to different sizes batch factor in which the scale of prime product varies from 1.5GB to 192GB, which enhances the usefulness of the algorithm significantly.

Key words: hierarchical, parallel framework, cloud computing, Bernstein, batch-factor, splitting-primes

摘要：

Bernstein提出的批分解算法能够快速完成给定光滑界B的一批随机整数的光滑性判断。然而该方法内存需求过于庞大，使得该算法广泛应用在理论分析阶段，实际应用却很少。为解决该问题，提出一种素数分段的方法，并据此提出一种层次化批分解算法云框架。该框架通过层次化的设计使得开发过程清晰简洁，具有较强的可移植性；借鉴自MapReduce的改进的云计算框架利用云客户端的分布存储和共享存储、消息机制等并行支撑平台提供的服务完成素数分段批分解算法的映射，解决了大规模Bernstein批分解算法空间需求过大的问题。实验结果显示，该框架能够适应素因子乘积规模由1.5GB至192GB的批分解运算，扩展性良好，增强了批分解算法的实用性。

关键词: 层次化, 并行框架, 云计算, Bernstein, 批分解, 分段素数