離散対数

数学 では、与えられた実数に対して${\displaystyle a}$そして${\displaystyle b}$対数​${\displaystyle \log _{b}(a)}$数字です${\displaystyle x}$そのため${\displaystyle b^{x}=a}$離散対数は群論における類似の概念である。どの群においても${\displaystyle G}$、力${\displaystyle b^{k}}$すべての整数に対して定義できる${\displaystyle k}$、そして離散対数${\displaystyle \log _{b}(a)}$整数です${\displaystyle k}$そのため${\displaystyle b^{k}=a}$整数を法とする算術演算の特殊な場合${\displaystyle m}$より一般的に使われる用語はインデックスです。次のように書くことができます。${\displaystyle k=\mathrm {ind} _{b}a\!\!\!\!{\pmod {m}}}$いつ${\displaystyle b^{k}\equiv a\!\!\!\!{\pmod {m}}}$。

離散対数はいくつかの特殊なケースでは高速に計算できますが、一般的に効率的な計算方法は知られていません。Diffie –HellmanやElGamalを含むいくつかの暗号システムは、慎重に選択された群上の離散対数問題には効率的な解がないという困難性の仮定に基づいてセキュリティを構築しています。^{[ 1 ]}一般に、ブラックボックス群に対しては準指数時間解はありません。^{[ 2 ]}

させて${\displaystyle G}$を任意の群とする。その群演算を乗法で、単位元をで表す。${\displaystyle 1}$。 させて${\displaystyle b}$の要素である${\displaystyle G}$任意の正の整数に対して${\displaystyle k}$表現${\displaystyle b^{k}}$の積を表す${\displaystyle b}$自身と${\displaystyle k}$回数: ^{[ 3 ]}

${\displaystyle b^{k}=\underbrace {b\cdot b\cdot \ldots \cdot b} _{k\;{\text{因子}}}.}$

同様に、${\displaystyle b^{-k}}$の積を表す${\displaystyle b^{-1}}$自身と${\displaystyle k}$回数。${\displaystyle k=0}$、${\displaystyle k}$^力はアイデンティティである：${\displaystyle b^{0}=1}$。

させて${\displaystyle a}$また、${\displaystyle G}$整数${\displaystyle k}$方程式を解く${\displaystyle b^{k}=a}$は、離散対数（またはこの文脈では単に対数）と呼ばれます。${\displaystyle a}$基地へ${\displaystyle b}$一人はこう書いている${\displaystyle k=\log _{b}a}$。

べき乗は通常の代数的恒等式に従う${\displaystyle b^{k+l}=b^{k}\cdot b^{l}}$[ ^{3 ]}言い換えれば^、関数

${\displaystyle f\colon \mathbf {Z} \to G}$

定義される${\displaystyle f(k)=b^{k}}$は整数群からの群準同型である。${\displaystyle \mathbf {Z} }$サブグループに追加${\displaystyle H}$の${\displaystyle G}$によって生成されました${\displaystyle b}$すべての${\displaystyle a}$で${\displaystyle H}$、${\displaystyle \log _{b}a}$存在する。逆に、${\displaystyle \log _{b}a}$存在しない${\displaystyle a}$含まれていないもの${\displaystyle H}$。

もし${\displaystyle H}$無限大の場合、${\displaystyle \log _{b}a}$もユニークであり、離散対数は群同型に相当する。

${\displaystyle \log _{b}\colon H\to \mathbf {Z} .}$

一方、${\displaystyle H}$次数が有限である${\displaystyle n}$、 それから${\displaystyle \log _{b}a}$0 は合同法を除いて一意です${\displaystyle n}$離散対数は群同型に相当する

${\displaystyle \log _{b}\colon H\to \mathbf {Z} _{n},}$

どこ${\displaystyle \mathbf {Z} _{n}}$は整数の加法群を表す。${\displaystyle n}$。

通常の対数に対するおなじみの底変換公式は依然として有効です。${\displaystyle c}$は別のジェネレーターです${\displaystyle H}$、 それから

${\displaystyle \log _{c}a=\log _{c}b\cdot \log _{b}a.}$

離散対数問題は、計算上困難であると考えられている。古典的な（例えば、量子コンピュータではない）コンピュータでは、一般的に離散対数を計算するための効率的な（多項式時間）アルゴリズムはまだ知られていない。

計算のための一般的なアルゴリズム${\displaystyle \log _{b}a}$有限群において${\displaystyle G}$上げる${\displaystyle b}$より大きな権力へ${\displaystyle k}$希望するまで${\displaystyle a}$が見つかりました。このアルゴリズムは試行乗算と呼ばれることもあります。実行時間は グループのサイズに比例します。${\displaystyle G}$したがって、グループのサイズにおける桁数に対して指数関数的に増加する。そのため、これは指数時間アルゴリズムであり、小規模なグループにのみ実用的である。${\displaystyle G}$。

より高度なアルゴリズムも存在し、それらは通常、整数因数分解のための類似アルゴリズムにヒントを得ている。これらのアルゴリズムは単純なアルゴリズムよりも高速で、中には群のサイズの平方根に比例するものもあり、群のサイズの桁数の半分に対して指数関数的に高速になるものもある。しかし、いずれも（群のサイズの桁数に対して）多項式時間で実行されるものではない。

• ベビーステップ ジャイアントステップ
• 機能フィールドふるい
• インデックス計算アルゴリズム
• 数値フィールドふるい
• ポーリグ・ヘルマンアルゴリズム
• ポラードの対数に対するρアルゴリズム
• ポラードのカンガルーアルゴリズム（別名：ポラードのラムダアルゴリズム）

ピーター・ショアによる効率的な量子アルゴリズムが存在する。^{[ 5 ]}

特定の特殊なケースでは、効率的な古典的アルゴリズムも存在します。たとえば、整数のグループでは、${\displaystyle p}$さらに、${\displaystyle b^{k}}$製品になる${\displaystyle b\cdot k}$、そして等号は法合同を意味する${\displaystyle p}$整数において。拡張ユークリッドアルゴリズムは${\displaystyle k}$素早く。

ディフィー・ヘルマン法では、素数を法とする巡回群は${\displaystyle p}$が使用されるため、群の位数が ( である) の場合、Pohlig–Hellman による離散対数の効率的な計算が可能になります。${\displaystyle p-1}$) は十分に滑らかであり、大きな素因数を持たない。

離散対数の計算と整数因数分解は異なる問題ではあるが、いくつかの共通点がある。

• どちらも有限アーベル群の隠れた部分群問題の特殊なケースである。
• どちらの問題も難しいようです（非量子コンピュータ向けの効率的なアルゴリズムは知られていません）。
• どちらの問題に対しても、量子コンピュータ上で効率的なアルゴリズムが知られている。
• ある問題のアルゴリズムはしばしば別の問題に適応され、
• これら二つの問題の難しさは、様々な暗号システムを構築するために利用されてきた。

離散対数を計算することが明らかに困難な群が存在する。いくつかのケース（例えば、群の大きな素数位数の部分群）$\displaystyle \mathbf {Z} _{p}^{\times }}$）最悪の場合に対して効率的なアルゴリズムが知られていないだけでなく、平均的な場合の複雑さは、ランダム自己還元性を使用した場合、最悪の場合とほぼ同じくらい難しいことが示されています。^{[ 6 ]}

同時に、離散べき乗の逆問題は難しくありません（例えば、2乗によるべき乗を用いて効率的に計算できます）。この非対称性は、整数因数分解と整数乗の間の非対称性に類似しています。これらの非対称性（およびその他の片方向関数）は、暗号システムの構築において利用されてきました。

グループに人気の選択肢${\displaystyle G}$離散対数暗号（DLC）では、巡回群は$\displaystyle \mathbf {Z} _{p}^{\times }}$（例えば、エルガマル暗号、ディフィー・ヘルマン鍵交換、デジタル署名アルゴリズムなど）および有限体上の楕円曲線の巡回部分群（楕円曲線暗号を参照）。

一般的に離散対数問題を解くための公に知られているアルゴリズムはないが、数体篩アルゴリズムの最初の3つのステップは群のみに依存する${\displaystyle G}$特定の要素ではなく${\displaystyle G}$その有限性${\displaystyle \log }$特定のグループに対してこれら 3 つのステップを事前に計算することで、最初の 3 つのステップよりも計算コストがはるかに低い最後のステップを実行するだけで、そのグループの特定の対数を取得できます。^{[ 7 ]}

インターネットトラフィックの多くは、1024ビット以下のオーダーのグループ、例えばRFC 2409で指定されているオークリー素数のオーダーを持つ巡回グループのいずれかを使用していることが判明した。^{[ 8 ]} Logjam攻撃はこの脆弱性を利用して、512ビット素数、いわゆるエクスポートグレードのオーダーを持つグループの使用を許可していたさまざまなインターネットサービスを侵害した。^{[ 7 ]}

Logjam攻撃の著者らは、1024ビット素数の離散対数問題を解くために必要な、はるかに困難な事前計算は、米国国家安全保障局（NSA）のような大規模な国家情報機関の予算内であると推定している。Logjamの著者らは、広く再利用されている1024 DH素数に対する事前計算が、NSAが現在の暗号の大部分を破ることができるという流出したNSA文書の主張の背後にあると推測している。^{[ 7 ]}

• AWファーバー モデル366
• パーシー・ラドゲートとアイルランドの対数

• リチャード・クランドール、カール・ポメランス。「素数：計算論的視点」第5章、第2版、シュプリンガー。
• スティンソン、ダグラス・ロバート（2006）。暗号理論：理論と実践（第3 版）。ロンドン、英国：CRC Press。ISBN 978-1-58488-508-5。