論文の概要: On Modular Algorithms and Butterfly Operations in Number Theoretic Transform
- arxiv url: http://arxiv.org/abs/2402.00675v2
- Date: Fri, 9 Feb 2024 20:12:01 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-25 12:08:11.068122
- Title: On Modular Algorithms and Butterfly Operations in Number Theoretic Transform
- Title（参考訳）: 数理論変換におけるモジュールアルゴリズムとバタフライ演算について
- Authors: Yanze Yang, Yiran Jia, Guangwu Xu,
- Abstract要約: 数論変換(NTT)は数論、代数、暗号の計算において非常に有用なツールである。
本稿ではNTTのバタフライ操作について論じる。
モンゴメリーアルゴリズムのいくつかの変種はNTTの高速化を目的として提案されている。
- 参考スコア（独自算出の注目度）: 2.9357919636083256
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Number theoretic transform (NTT) has been a very useful tool in computations for number theory, algebra and cryptography. Its performance affects some post-quantum cryptosystems. In this paper, we discuss the butterfly operation of NTT. This basic module of NTT requires heavy modular arithmetics. Montgomery reduction is commonly used in this setting. Recently several variants of Montgomery algorithm have been proposed for the purpose of speeding up NTT. We observe that the Chinese remainder theorem (CRT) can be involved in this type of algorithms in natural and transparent ways. In the first part of the paper, a framework of using CRT to model Montgomery type algorithms is described. The derivation of these algorithms as well as their correctness are all treated in the CRT framework. Under our approach, some problems of a modular reduction algorithm (published in IACR Transactions on Cryptographic Hardware and Embedded Systems, doi:10.46586/tches.v2022.i4.614-636 ) are identified, and a counterexample is generated to show that the algorithm is incorrect. In the second part of the paper, we modify a modular multiplication algorithm of Plantard to suite the butterfly structure by Scott, an improved computation of the butterfly module for NTT is obtained. Experiments show that the method performs better compared to NTT implementations using previous popular methods.
- Abstract（参考訳）: 数論変換(NTT)は数論、代数、暗号の計算において非常に有用なツールである。
その性能は量子後暗号システムに影響を及ぼす。
本稿ではNTTのバタフライ操作について論じる。
NTTの基本モジュールは、重いモジュラー演算を必要とする。
モンゴメリー還元はこの設定で一般的に使用される。
近年,NTTの高速化を目的としたモンゴメリーアルゴリズムの変種がいくつか提案されている。
我々は、中国の剰余定理(CRT)が自然かつ透明な方法でこの種のアルゴリズムに関わっていることを観察する。
論文の前半では、モンゴメリー型アルゴリズムをモデル化するためにCRTを使用するフレームワークについて述べる。
これらのアルゴリズムの導出と正確性は、すべてCRTフレームワークで扱われる。
提案手法では,モジュールリダクションアルゴリズム(IACR Transactions on Cryptographic Hardware and Embedded Systems, doi:10.46586/tches.v2022.i4.614-636 )のいくつかの問題を同定し,そのアルゴリズムが正しくないことを示す。
論文の第2部では、Scottによる蝶構造を組合わせるために、Planardのモジュラ乗算アルゴリズムを変更し、NTT用の蝶モジュールの計算を改良した。
実験の結果,従来のNTT方式と比較して性能がよいことがわかった。
関連論文リスト
- A new lightweight additive homomorphic encryption algorithm [0.0]
本稿では、同じ暗号鍵と復号鍵を持つ軽量な加法的同型アルゴリズムについて述べる。
これにより、モジュラー指数からモジュラー乗算への暗号化と復号化の計算コストが削減される。
論文 参考訳（メタデータ） (2023-12-12T05:12:20Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-30T15:57:14Z) - Efficient Additions and Montgomery Reductions of Large Integers for SIMD [2.362288417229025]
本稿では,512ビット以上の整数に対してモンゴメリー還元と加算を行うための効率的なアルゴリズムを提案する。
新しい加算アルゴリズムは、より小さな加算を用いて大きな整数の追加をシミュレートし、すぐに同じキャリーセットを生成する。
モンゴメリー還元の場合、シリアル乗算はSIMD拡張を用いて効果的に計算できるプリ計算に置き換えられる。
論文 参考訳（メタデータ） (2023-08-31T03:44:49Z) - Synthesising Recursive Functions for First-Order Model Counting:
Challenges, Progress, and Conjectures [12.47276164048813]
1次モデルカウント(英: First-order model counting、FOMC)は、有限領域の1次論理において文のモデルを数えるように要求する計算問題である。
私たちは、典型的にドメイン再帰に伴う制限を緩和し、サイクルを含むかもしれない有向グラフを扱う。
これらの改良により、アルゴリズムはそれまで到達範囲を超えていた問題を数えるための効率的な解を見つけることができる。
論文 参考訳（メタデータ） (2023-06-07T06:49:01Z) - A Constrained BA Algorithm for Rate-Distortion and Distortion-Rate
Functions [13.570794979535934]
速度歪み関数に対するBlahut-Arimoto (BA)アルゴリズムの修正
修正アルゴリズムは、与えられた対象歪みに対してRD関数を直接計算する。
論文 参考訳（メタデータ） (2023-05-04T08:41:03Z) - Modular Differential Evolution [0.0]
本稿では,一般的な微分進化(DE)アルゴリズムのためのモジュラーフレームワークを提案する。
モジュールDEの設定のチューニングは、我々のフレームワークで再現された一般的なDEバージョンのセットよりも大幅に優れています。
論文 参考訳（メタデータ） (2023-04-19T09:29:48Z) - Regret Bounds for Expected Improvement Algorithms in Gaussian Process
Bandit Optimization [63.8557841188626]
期待されている改善(EI)アルゴリズムは、不確実性の下で最適化するための最も一般的な戦略の1つである。
本稿では,GP予測平均を通した標準既存値を持つEIの変種を提案する。
我々のアルゴリズムは収束し、$mathcal O(gamma_TsqrtT)$の累積後悔境界を達成することを示す。
論文 参考訳（メタデータ） (2022-03-15T13:17:53Z) - Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。
O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。
さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
論文 参考訳（メタデータ） (2021-10-15T00:54:04Z) - AsySQN: Faster Vertical Federated Learning Algorithms with Better
Computation Resource Utilization [159.75564904944707]
垂直連合学習(VFL)のための非同期準ニュートン(AsySQN)フレームワークを提案する。
提案アルゴリズムは、逆ヘッセン行列を明示的に計算することなく、近似して降下ステップをスケールする。
本稿では,非同期計算を採用することにより,計算資源の有効利用が期待できることを示す。
論文 参考訳（メタデータ） (2021-09-26T07:56:10Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。