Analysis of Elliptic Curve Method & Block Wiedemann Algorithm: A Case Study of Big Integer Factorization on Multi-cores Platforms

計畫名稱:Analysis of Elliptic Curve Method & Block Wiedemann Algorithm: A Case Study of Big Integer Factorization on Multi-cores Platforms

所屬單位:資訊系

計畫主持人:洪士灝

研究人員:林宗慶

資源需求:gcc

使用期間:2009/03~

研究主題:
Analysis of Elliptic Curve Method & Block Wiedemann Algorithm: A Case Study of Big Integer Factorization on Multi-cores Platforms

研究內容概述:
Block Wiedemann演算法,是目前General Number Field Sieve裡重要的一環,主要構成是稀疏矩陣的乘法,當矩陣大小超過一個數量後,平行化的需求在所難免。然而其計算過程當中,對於網路頻寬的需求相當高,進入多核心時代,對於網路頻寬增加的壓力更為增加,因此,希望利用設計平行化的版本,並且分析其後端網路設備、配置對於效能的影響程度,以及多核心環境下對於網路頻寬的影響,預測效能趨勢,找尋最佳的配置。 另外,Elliptic curve method也是跟大數質因數有關的一個應用,ECM本身可以用來分解大數,不過目前的世界記錄也僅止於67位數,並沒有辦法分解目前RSA加解密演算法相關的大數。即使如此,ECM還是可以整合進去General Number Field Sieve當中Sieving的步驟,以加速Sieving的進行。 這個研究計畫的內容,除了Block Wiedemann演算法,也希望分析ECM在多核心環境下的效能,作為一個比較分析,以瞭解新一代的多核心結構對於大數分解效能的影響。

詳細計畫內容 回到上一頁