• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Security for Information Technology and Communications >An Improved Algorithm for Iterative Matrix-Vector Multiplications over Finite Fields
【24h】

An Improved Algorithm for Iterative Matrix-Vector Multiplications over Finite Fields

机译：有限字段迭代矩阵矢量乘法的改进算法

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Cryptographic computations such as factoring integers and computing discrete logarithms over finite fields require solving a large system of linear equations. When dealing with such systems iterative approaches such as Wiedemann or Lanczos are used. Both methods are based on the computation of a Krylov subspace in which the computational cost is often dominated by successive matrix-vector products. We introduce a new algorithm for computing iterative matrix-vector multiplications over finite fields. The proposed algorithm consists of two stages. The first stage (preprocessing) sorts the elements of the matrix row by row in ascending order and produces permutation tables. After preprocessing, many consecutive multiplications can be performed by the second stage of the algorithm using sequential additions on vector elements by the guidance of the permutation tables. We show that the preprocessing cost of the proposed algorithm can easily be amortized after several matrix-vector multiplications are performed. We implemented the algorithm using the C++ programming language and compared the performance with a classical method. The proposed algorithm exhibits significant improvement between 35% and 67%.
机译：诸如要约整数和计算离散对数的加密计算需要解决大型线性方程系统。在处理这些系统时，使用迭代方法，如Wiedemann或Lanczos。两种方法都基于计算成本的krylov子空间的计算，其中计算成本通常由连续的矩阵矢量产品主导。我们介绍了一种用于计算有限字段的迭代矩阵矢量乘法的新算法。所提出的算法包括两个阶段。第一阶段（预处理）按升序按行排序矩阵行的元素，并产生排列表。在预处理之后，可以通过置换表的引导，通过向矢量元素上的顺序添加，通过算法的第二阶段执行许多连续乘法。我们表明，在执行几个矩阵矢量乘法之后，所提出的算法的预处理成本很容易被摊销。我们使用C ++编程语言实现了算法，并使用经典方法进行比较性能。所提出的算法表现出35％和67％的显着改善。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号