【24h】

SMP Based Solver for Large Binary Systems

机译:适用于大型二进制系统的基于SMP的求解器

获取原文

摘要

Solving a large sparse system of linear equations (SSLE)over the binary field is an important step in the general number field seive (GNFS) algorithm that is often used to factorize large integers used in the RSA algorithm. Block Lanczos method proposed by Montgomery is an efficient and reliable method for solving such systems. A number of implementations of Block Lanczos method on distributed systems have been proposed in past. This paper discusses the parallel Montgomery's Block Lanczos method for solving binary system of equations on shared multiprocessors(SMP). A simple experiment shows that the speed of convergence of this algorithm is dependent on a wise choice of initial guess for kick-starting the algorithm. A somewhat dense choice of the initial guess is suggested rather than a random choice for faster convergence. Devoid of any communication overheads of a loosely coupled system, the improved method gives good performance on SMP systems which can provide an able alternative to the more popular distributed systems. Details of implementation of this algorithm on SMP and experimental results are also provided in the paper.
机译:解决二进制字段上的大型线性方程组(SSLE)稀疏系统是通用数字段seive(GNFS)算法中的重要一步,该算法通常用于分解RSA算法中使用的大整数。 Montgomery提出的Block Lanczos方法是解决此类系统的一种有效且可靠的方法。过去已经提出了在分布式系统上的Block Lanczos方法的许多实现。本文讨论了在共享多处理器(SMP)上求解并行二进制方程组的蒙哥马利块Lanczos并行方法。一个简单的实验表明,该算法的收敛速度取决于启动算法的初始猜测的明智选择。建议对初始猜测进行某种程度的密集选择,而不是为了更快地收敛而采用随机选择。避免了松散耦合系统的任何通信开销,改进的方法在SMP系统上提供了良好的性能,可以为更流行的分布式系统提供有力的替代方案。本文还提供了该算法在SMP上的实现细节和实验结果。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号