論文の概要: SAT and Lattice Reduction for Integer Factorization

• arxiv url: http://arxiv.org/abs/2406.20071v1
• Date: Fri, 28 Jun 2024 17:30:20 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-01 16:10:57.825176
• Title: SAT and Lattice Reduction for Integer Factorization
• Title（参考訳）: インテガーファクトリゼーションのためのSATと格子低減
• Authors: Yameen Ajani, Curtis Bright,
• Abstract要約: ランダムリークビット因数分解問題の解法として,新しいハイブリッドSATおよび計算機代数手法を提案する。 我々の実装は、純粋なSATや純粋計算機代数のアプローチよりもはるかに高速なランダムリークビット分解問題を解く。
• 参考スコア（独自算出の注目度）: 5.035245337299788
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The difficulty of factoring large integers into primes is the basis for cryptosystems such as RSA. Due to the widespread popularity of RSA, there have been many proposed attacks on the factorization problem such as side-channel attacks where some bits of the prime factors are available. When enough bits of the prime factors are known, two methods that are effective at solving the factorization problem are satisfiability (SAT) solvers and Coppersmith's method. The SAT approach reduces the factorization problem to a Boolean satisfiability problem, while Coppersmith's approach uses lattice basis reduction. Both methods have their advantages, but they also have their limitations: Coppersmith's method does not apply when the known bit positions are randomized, while SAT-based methods can take advantage of known bits in arbitrary locations, but have no knowledge of the algebraic structure exploited by Coppersmith's method. In this paper we describe a new hybrid SAT and computer algebra approach to efficiently solve random leaked-bit factorization problems. Specifically, Coppersmith's method is invoked by a SAT solver to determine whether a partial bit assignment can be extended to a complete assignment. Our hybrid implementation solves random leaked-bit factorization problems significantly faster than either a pure SAT or pure computer algebra approach.
• Abstract（参考訳）: 大きな整数を素数に分解することの難しさは、RSAのような暗号システムの基盤である。 RSAの普及により、素因のビットが利用可能となるサイドチャネル攻撃など、因子化問題に対する多くの攻撃が提案されている。 素因子の十分なビットが知られている場合、分解問題を解くのに有効な2つの方法は、SATソルバと銅細工の方法である。 SATアプローチは分解問題をブール適合性問題に還元する一方、Cupersmithのアプローチは格子基底還元を用いる。 銅スミスの手法は既知のビット位置がランダム化されているときに適用されないが、SATベースの手法は任意の場所で既知のビットを利用することができるが、銅スミスの手法によって利用される代数構造について知識がない。 本稿では,ランダムリークビット因数分解問題を効率的に解くためのハイブリッドSATと計算機代数のアプローチについて述べる。 具体的には、SATソルバによって、部分ビット割り当てを完全な割り当てに拡張できるかどうかを判定するために、Cupersmithのメソッドが呼び出される。 我々のハイブリッド実装は、純粋なSATや純粋計算機代数のアプローチよりもはるかに高速なランダムリークビット分解問題を解く。

関連論文リスト

• General Method for Solving Four Types of SAT Problems [12.28597116379225]
  既存の方法は、様々なタイプのブール適合性問題(SAT)に対して様々なアルゴリズムを提供する。 本研究では,整数計画法と強化学習法(RL)に基づく統合フレームワークDCSATを提案する。
  論文  参考訳（メタデータ） (2023-12-27T06:09:48Z)
• Decomposing Hard SAT Instances with Metaheuristic Optimization [52.03315747221343]
  分解硬度(d硬度)の概念を導入する。 d-硬度が$C$ w.r.tの硬度の推定値を示すことを示す。
  論文  参考訳（メタデータ） (2023-12-16T12:44:36Z)
• Machine Learning for SAT: Restricted Heuristics and New Graph Representations [0.8870188183999854]
  SATは、自動スケジューリングを含む多くのアプリケーションにおいて、基本的なNP完全問題である。 大きなインスタンスを解決するためには、SATソルバは、例えばDPLLとCDCLソルバの分岐変数を選択するなど、ブールアンに依存する必要がある。 我々は、訓練されたMLモデルでいくつかの初期ステップを行い、古典的なランタイムに制御をリリースする戦略を提案する。
  論文  参考訳（メタデータ） (2023-07-18T10:46:28Z)
• Estimating the hardness of SAT encodings for Logical Equivalence Checking of Boolean circuits [58.83758257568434]
  LEC インスタンスの SAT 符号化の硬さは SAT パーティショニングでは textitw.r. と推定できることを示す。 そこで本研究では, SAT符号化の難易度を精度良く推定できるパーティショニング法を提案する。
  論文  参考訳（メタデータ） (2022-10-04T09:19:13Z)
• Asymmetric Scalable Cross-modal Hashing [51.309905690367835]
  クロスモーダルハッシュは、大規模なマルチメディア検索問題を解決する方法として成功している。 これらの問題に対処する新しい非対称スケーラブルクロスモーダルハッシュ(ASCMH)を提案する。 我々のASCMHは、最先端のクロスモーダルハッシュ法よりも精度と効率の点で優れています。
  論文  参考訳（メタデータ） (2022-07-26T04:38:47Z)
• Penalty Weights in QUBO Formulations: Permutation Problems [0.0]
  量子コンピュータで動くよう設計された最適化アルゴリズムは 近年 研究の関心を集めています これらの解法の多くは、二項形式と二項形式の問題を最適化することしかできない。 多くの最適化問題があり、自然に置換として表される。 より有望な結果をもたらすペナルティ重みを計算するための新しい静的手法を提案する。
  論文  参考訳（メタデータ） (2022-06-20T22:00:38Z)
• Integer Factorization with Compositional Distributed Representations [5.119801391862319]
  本稿では,ベクトル記号アーキテクチャを用いた分散表現を用いた整数分解手法を提案する。 この手法は、整数分解をニューラルネットワークを用いて解くことができ、並列なニューロモルフィックハードウェアに実装される可能性がある方法で定式化する。
  論文  参考訳（メタデータ） (2022-03-02T08:09:17Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNFベースのSATとMaxSATは論理合成と検証システムの中心である。 そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-07-15T04:47:35Z)
• Batch Bayesian Optimization on Permutations using Acquisition Weighted Kernels [86.11176756341114]
  決定点プロセスに基づく新しい効率的なバッチ取得方法であるLAWを紹介します。 本研究では,理論特性の知見を得るための後悔分析法を提案する。 二次代入などの置換を含むいくつかの標準問題に対する手法を評価する。
  論文  参考訳（メタデータ） (2021-02-26T10:15:57Z)
• Determining the Multiplicative Complexity of Boolean Functions using SAT [1.4902915966744057]
  ブール関数の乗法的複雑性を決定するための構築的SATアルゴリズムを提案する。 提案アルゴリズムは,全5入力アフィン等価クラスの代表に対して最適XAGを求めることができる。
  論文  参考訳（メタデータ） (2020-05-04T18:29:48Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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