Fugu-MT 論文翻訳(概要): Efficient Additions and Montgomery Reductions of Large Integers for SIMD

論文の概要: Efficient Additions and Montgomery Reductions of Large Integers for SIMD

arxiv url: http://arxiv.org/abs/2308.16432v1
Date: Thu, 31 Aug 2023 03:44:49 GMT
ステータス: 処理完了
システム内更新日: 2024-03-19 07:03:01.499432
Title: Efficient Additions and Montgomery Reductions of Large Integers for SIMD
Title（参考訳）: SIMD用大型整数器の高効率付加とモンゴメリー低減
Authors: Pengchang Ren, Reiji Suda, Vorapong Suppakitpaisarn,
Abstract要約: 本稿では,512ビット以上の整数に対してモンゴメリー還元と加算を行うための効率的なアルゴリズムを提案する。新しい加算アルゴリズムは、より小さな加算を用いて大きな整数の追加をシミュレートし、すぐに同じキャリーセットを生成する。モンゴメリー還元の場合、シリアル乗算はSIMD拡張を用いて効果的に計算できるプリ計算に置き換えられる。
参考スコア（独自算出の注目度）: 2.362288417229025
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
Abstract: This paper presents efficient algorithms, designed to leverage SIMD for performing Montgomery reductions and additions on integers larger than 512 bits. The existing algorithms encounter inefficiencies when parallelized using SIMD due to extensive dependencies in both operations, particularly noticeable in costly operations like ARM's SVE. To mitigate this problem, a novel addition algorithm is introduced that simulates the addition of large integers using a smaller addition, quickly producing the same set of carries. These carries are then utilized to perform parallel additions on large integers. For Montgomery reductions, serial multiplications are replaced with precomputations that can be effectively calculated using SIMD extensions. Experimental evidence demonstrates that these proposed algorithms substantially enhance the performance of state-of-the-art implementations of several post-quantum cryptography algorithms. Notably, they deliver a 30% speed-up from the latest CTIDH implementation, an 11% speed-up from the latest CSIDH implementation in AVX-512 processors, and a 7% speed-up from Microsoft's standard PQCrypto-SIDH for SIKEp503 on A64FX.
Abstract（参考訳）: 本稿では,SIMDを利用して512ビット以上の整数に対してモンゴメリー還元と加算を行うアルゴリズムを提案する。既存のアルゴリズムは、SIMDを使用して並列化する場合、両方の操作に大きく依存するため、特にARMのSVEのような高価な操作では、非効率に遭遇する。この問題を軽減するために、より小さな加算を用いて大きな整数の加算をシミュレートする新しい加算アルゴリズムが導入された。これらのキャリアは、大きな整数に対して並列的な加算を実行するために使用される。モンゴメリー還元の場合、シリアル乗算はSIMD拡張を用いて効果的に計算できるプリ計算に置き換えられる。実験的な証拠は、これらの提案されたアルゴリズムが、いくつかの量子後暗号アルゴリズムの最先端実装の性能を大幅に向上させることを証明している。特に、最新のCTIDH実装からの30%のスピードアップ、AVX-512プロセッサのCSIDH実装からの11%のスピードアップ、A64FX上のSIKEp503用のMicrosoftの標準PQCrypto-SIDHからの7%のスピードアップを提供する。

関連論文リスト

Efficient and Flexible Differet-Radix Montgomery Modular Multiplication for Hardware Implementation [14.516310806294433]
DRMMMと呼ばれる反復モンゴメリーモジュラー乗算の効率的な並列変乗法を提案し、複数の反復で商を計算できるようにする。提案した変種に基づいて,高速な動作を実現するための高性能ハードウェア実装アーキテクチャを設計する。
論文参考訳（メタデータ） (2024-07-17T16:24:15Z)
A High-Speed Hardware Algorithm for Modulus Operation and its Application in Prime Number Calculation [0.0]
提案アルゴリズムは加算演算,減算演算,論理演算,ビットシフト演算のみを用いる。暗号化アプリケーションにおけるスケーラビリティの課題に対処する。このアルゴリズムを50,000までの素数計算に適用すると、実用性と性能上の利点が示される。
論文参考訳（メタデータ） (2024-07-17T13:24:52Z)
BoostCom: Towards Efficient Universal Fully Homomorphic Encryption by Boosting the Word-wise Comparisons [14.399750086329345]
完全同型暗号化(FHE)は、最初に復号化することなく、暗号化データ上での計算の実行を可能にする。本稿では,単語比較処理の高速化を目的としたBoostComを提案する。我々は、最先端のCPUベースのuFHEシステムと比較して、桁違い(11.1倍高速)のエンドツーエンド性能向上を実現している。
論文参考訳（メタデータ） (2024-07-10T02:09:10Z)
SAGA: Synthesis Augmentation with Genetic Algorithms for In-Memory Sequence Optimization [0.0]
MAGIC(Memristor Aided Logic)は、メモリへの書き込み操作を通じて物理的に計算を行うメモリ回路を使用するアプローチである。本稿では,これらの遺伝的アルゴリズムの生成と実装について詳述し,多数のオープン回路実装について評価する。評価された10のベンチマーク回路のうち、これらの変更により、インメモリ回路評価の効率は、ベストケースで128%、平均で27.5%向上した。
論文参考訳（メタデータ） (2024-06-14T03:00:42Z)
Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching [53.91395791840179]
我々は、大規模なSDPを解くための、証明可能な正確で高速でスケーラブルなアルゴリズムであるUnified Spectral Bundling with Sketching (USBS)を提案する。 USBSは、20億以上の決定変数を持つインスタンス上で、最先端のスケーラブルなSDP解決器よりも500倍のスピードアップを提供する。
論文参考訳（メタデータ） (2023-12-19T02:27:22Z)
An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文参考訳（メタデータ） (2023-09-30T15:57:14Z)
Decreasing the Computing Time of Bayesian Optimization using Generalizable Memory Pruning [56.334116591082896]
本稿では,任意のサロゲートモデルと取得関数で使用可能なメモリプルーニングとバウンダリ最適化のラッパーを示す。 BOを高次元または大規模データセット上で実行することは、この時間の複雑さのために難解になる。すべてのモデル実装はMIT Supercloudの最先端コンピューティングハードウェア上で実行される。
論文参考訳（メタデータ） (2023-09-08T14:05:56Z)
Rapid Person Re-Identification via Sub-space Consistency Regularization [51.76876061721556]
Person Re-Identification (ReID) は、歩行者を分離したカメラで識別する。実値特徴記述子を用いた既存のReID法は精度が高いが、ユークリッド距離計算が遅いため効率が低い。本稿では,ReID 処理を 0.25 倍高速化するサブスペース一貫性規則化 (SCR) アルゴリズムを提案する。
論文参考訳（メタデータ） (2022-07-13T02:44:05Z)
Providing Meaningful Data Summarizations Using Examplar-based Clustering in Industry 4.0 [67.80123919697971]
我々は,従来のCPUアルゴリズムと比較して,一精度で最大72倍,半精度で最大452倍の高速化を実現していることを示す。提案アルゴリズムは射出成形プロセスから得られた実世界のデータに適用し, 得られたサマリーが, コスト削減と不良部品製造の削減のために, この特定のプロセスのステアリングにどのように役立つかについて議論する。
論文参考訳（メタデータ） (2021-05-25T15:55:14Z)
Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding Design for Multiuser MIMO Systems [59.804810122136345]
本稿では,AIIDNN(ディープ・アンフォールディング・ニューラルネット)を一般化した,ディープ・アンフォールディングのためのフレームワークを提案する。古典的重み付き最小二乗誤差(WMMSE)反復アルゴリズムの構造に基づく効率的なIAIDNNを提案する。提案したIAIDNNは,計算複雑性を低減した反復WMMSEアルゴリズムの性能を効率よく向上することを示す。
論文参考訳（メタデータ） (2020-06-15T02:57:57Z)
Fast Implementation of Morphological Filtering Using ARM NEON Extension [0.9135092203041721]
ARMプロセッサにおける形態素画像フィルタリングの高速化の可能性を検討する。 ARM SIMD拡張NEONを用いた浸食・拡張の高速化を提案する。浸食および浸食の最終実施時の効率は3倍に向上した。
論文参考訳（メタデータ） (2020-02-19T12:55:34Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。