論文の概要: The Equivalence of Fast Algorithms for Convolution, Parallel FIR Filters, Polynomial Modular Multiplication, and Pointwise Multiplication in DFT/NTT Domain
- arxiv url: http://arxiv.org/abs/2512.01974v1
- Date: Mon, 01 Dec 2025 18:29:28 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-12-02 19:46:35.017284
- Title: The Equivalence of Fast Algorithms for Convolution, Parallel FIR Filters, Polynomial Modular Multiplication, and Pointwise Multiplication in DFT/NTT Domain
- Title（参考訳）: DFT/NTT領域における畳み込み, 並列FIRフィルタ, 多項式モジュラ乗算, ポイントワイズ乗算における高速アルゴリズムの等価性
- Authors: Keshab K. Parhi,
- Abstract要約: 我々は、よく知られた高速畳み込み構造が、他の4つの問題領域における高速アルゴリズムの設計の基礎となることを示す。
高速なモジュール乗算と高速なポイントワイド乗算問題は、暗号システムアプリケーションにとって重要である。
- 参考スコア（独自算出の注目度）: 8.883733362171034
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Fast time-domain algorithms have been developed in signal processing applications to reduce the multiplication complexity. For example, fast convolution structures using Cook-Toom and Winograd algorithms are well understood. Short length fast convolutions can be iterated to obtain fast convolution structures for long lengths. In this paper, we show that well known fast convolution structures form the basis for design of fast algorithms in four other problem domains: fast parallel filters, fast polynomial modular multiplication, and fast pointwise multiplication in the DFT and NTT domains. Fast polynomial modular multiplication and fast pointwise multiplication problems are important for cryptosystem applications such as post-quantum cryptography and homomorphic encryption. By establishing the equivalence of these problems, we show that a fast structure from one domain can be used to design a fast structure for another domain. This understanding is important as there are many well known solutions for fast convolution that can be used in other signal processing and cryptosystem applications.
- Abstract（参考訳）: 高速な時間領域アルゴリズムが信号処理アプリケーションで開発され、乗算の複雑さが軽減された。
例えば、Cook-ToomアルゴリズムとWinogradアルゴリズムを用いた高速な畳み込み構造がよく理解されている。
短い長さの高速な畳み込みは、長い長さの高速な畳み込み構造を得るために反復することができる。
本稿では、高速並列フィルタ、高速多項式モジュラ乗算、DFTおよびNTT領域における高速点乗算の4つの問題領域における高速アルゴリズム設計の基礎となる高速畳み込み構造について述べる。
高速多項式モジュラー乗算と高速点乗算問題は、後量子暗号や同型暗号のような暗号系アプリケーションにとって重要である。
これらの問題の等価性を確立することにより、ある領域からの高速な構造を用いて別の領域の高速な構造を設計できることが示される。
この理解は、他の信号処理や暗号システムアプリケーションで使用できる高速畳み込みのためのよく知られたソリューションとして重要である。
関連論文リスト
- Fast correlated decoding of transversal logical algorithms [67.01652927671279]
大規模計算には量子エラー補正(QEC)が必要であるが、かなりのリソースオーバーヘッドが発生する。
近年の進歩により、論理ゲートからなるアルゴリズムにおいて論理キュービットを共同で復号化することにより、症候群抽出ラウンドの数を削減できることが示されている。
ここでは、回路を介して伝播する関連する論理演算子製品を直接復号することで、回路の復号化の問題を修正する。
論文 参考訳（メタデータ） (2025-05-19T18:00:00Z) - Improving Algorithmic Efficiency using Cryptography [11.496343300483904]
計算問題を解く際の時間的複雑さを改善するために暗号を用いる方法を示す。
標準的な暗号仮定の下では、既存のアルゴリズムよりも決定的に高速なアルゴリズムを設計できることを示す。
論文 参考訳（メタデータ） (2025-02-18T17:08:59Z) - KyberMat: Efficient Accelerator for Matrix-Vector Polynomial Multiplication in CRYSTALS-Kyber Scheme via NTT and Polyphase Decomposition [20.592217626952507]
CRYSTAL-Kyber (Kyber) は、標準化プロセス中に選択された暗号鍵カプセル化機構 (KEM) の1つである。
本稿では,Kyberアーキテクチャのレイテンシとスループットの制約に対する最適化について述べる。
論文 参考訳（メタデータ） (2023-10-06T22:57:25Z) - Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
本稿では, パール構造因果モデルにおいて, 因果関係などの部分的特定可能なクエリのバウンダリングの問題について議論する。
最近提案された反復EMスキームは初期化パラメータをサンプリングしてそれらの境界を内部近似する。
シンボルパラメータを実際の値に置き換えた回路構造を,単一のシンボル知識コンパイルによって得られることを示す。
論文 参考訳（メタデータ） (2023-10-05T07:10:40Z) - Fast 2D Convolutions and Cross-Correlations Using Scalable Architectures [2.2940141855172027]
基本的な考え方は、2次元の畳み込みとクロス相関を変換領域内の1次元の畳み込みとクロス相関の集合にマッピングすることである。
このアプローチでは、スケーラブルなアーキテクチャを使用して、最新のFPGAやZynq-SOCデバイスに組み込むことができる。
論文 参考訳（メタデータ） (2021-12-24T22:34:51Z) - Phase polynomials synthesis algorithms for NISQ architectures and beyond [3.3722008527102894]
ほとんどの場合、我々のアルゴリズムは、CNOTカウントとCNOT深さの少ない回路を生成する。
また,CNOT数の増加と実行時間の短縮を両立させ,アルゴリズムと高速なアルゴリズムとのギャップを埋める手法も提案する。
論文 参考訳（メタデータ） (2021-04-02T08:26:36Z) - Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。
提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
論文 参考訳（メタデータ） (2021-03-03T22:42:15Z) - 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) - QFAST: Quantum Synthesis Using a Hierarchical Continuous Circuit Space [5.406226763868874]
短絡回路を製造するために設計された量子合成ツールQFASTを提案する。
最適なサードパーティ合成アルゴリズムを与えられた階層レベルでプラグインすることで、より短い回路を生成する方法を示す。
論文 参考訳（メタデータ） (2020-03-09T23:55:43Z) - Computational optimization of convolutional neural networks using
separated filters architecture [69.73393478582027]
我々は、計算複雑性を低減し、ニューラルネットワーク処理を高速化する畳み込みニューラルネットワーク変換を考える。
畳み込みニューラルネットワーク(CNN)の使用は、計算的に要求が多すぎるにもかかわらず、画像認識の標準的なアプローチである。
論文 参考訳（メタデータ） (2020-02-18T17:42:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。