論文の概要: 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方式と比較して性能がよいことがわかった。

関連論文リスト

• Bregman-divergence-based Arimoto-Blahut algorithm [53.64687146666141]
  本稿では,Arimoto-BlahutアルゴリズムをBregman-Diversergenceシステム上で定義された一般関数に一般化する。 本稿では,古典的および量子速度歪み理論に適用可能な凸最適化自由アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-08-10T06:16:24Z)
• Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
  Indexed Minimum Empirical Divergence (IMED)は、マルチアームバンディット問題に対する非常に効果的なアプローチである。 UCBベースのアルゴリズムとトンプソンサンプリングを実証的に上回ることが観察されている。 我々は、LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの新しい線形バージョンを提案する。
  論文  参考訳（メタデータ） (2024-05-24T04:11:58Z)
• ADMM-MM Algorithm for General Tensor Decomposition [7.0326155922512275]
  提案アルゴリズムは3つの基本損失関数(ell$-loss, $ell$-loss, KL divergence)と様々な低ランクテンソル分解モデル(CP, Tucker, TT, TR)をサポートする。 提案したアルゴリズムにより広帯域のアプリケーションを解くことができ、プラグイン・アンド・プレイ方式で既存のテンソル分解モデルに容易に拡張できることを示す。
  論文  参考訳（メタデータ） (2023-12-19T00:17:34Z)
• Automatic Rao-Blackwellization for Sequential Monte Carlo with Belief Propagation [4.956977275061968]
  状態空間モデル(SSM)に関する具体的なベイズ予想は、一般には難解である。 本稿では,信念の伝播を用いた閉形式解を可能な限り計算する混合推論アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-15T15:05:25Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• 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)
• The Dynamics of Riemannian Robbins-Monro Algorithms [101.29301565229265]
  本稿では,Robins と Monro のセミナル近似フレームワークを一般化し拡張するリーマンアルゴリズムの族を提案する。 ユークリッドのそれと比較すると、リーマンのアルゴリズムは多様体上の大域線型構造が欠如しているため、はるかに理解されていない。 ユークリッド・ロビンス=モンロスキームの既存の理論を反映し拡張するほぼ確実な収束結果の一般的なテンプレートを提供する。
  論文  参考訳（メタデータ） (2022-06-14T12:30:11Z)
• Reconstructing Sparse Signals via Greedy Monte-Carlo Search [6.660458629649825]
  高次元環境下でスパース信号を再構成するモンテカルロ法を提案する。 欲求モンテカルロ探索アルゴリズムは、欲求モンテカルロ探索アルゴリズム (greedy Monte-Carlo search algorithm) と呼ばれる。
  論文  参考訳（メタデータ） (2020-08-07T13:36:57Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• Stochastic Regret Minimization in Extensive-Form Games [109.43344748069933]
  Monte-Carlo counterfactual regret minimization (MCCFR) は、完全な木には大きすぎるシーケンシャルゲームを解くための最先端のアルゴリズムである。 後悔の最小化手法を開発するための新しい枠組みを開発する。 MCCFRよりも優れた方法がいくつかある3つのゲームについて広範な実験を行った。
  論文  参考訳（メタデータ） (2020-02-19T23:05:41Z)

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

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