Viele Menschen kennen Baby-Step Giant-Step als Algorithmus zur Lösung des diskreten Logarithmusproblems. Ich konnte jedoch keine Artikel finden, die sich mit beliebigen Mods befassen, also werde ich darüber schreiben.
Erstens bezieht sich das diskrete logarithmische Problem auf die folgenden Probleme. (Wenn Sie die Lösung von Baby-Step Giant-Step kennen, überspringen Sie sie bitte.)
Angesichts der positiven ganzen Zahlen $ M $ und der ganzen Zahlen $ X, Y $, die $ 0 \ leq X, Y \ lt M $ sind.
Finden Sie die (minimale) nicht negative ganze Zahl $ K
Sie können dieses Problem wie folgt lösen.
Lassen Sie uns zunächst den einfachen Fall von $ X = 0 $ behandeln. Wenn $ Y = 0 $, dann ist $ K = 1 $, wenn $ Y \ neq 0 $, dann ist $ K = -1 $ (existiert nicht). Hier wird jedoch $ 0 ^ 0 = 1 $ gesetzt.
Betrachten Sie als nächstes den Fall von $ X \ neq 0 $. Eine nicht negative ganze Zahl, so dass $ K = p * i + q \ (0 \ leq q \ lt p) $ $ (1) $ als $ p = \ left \ lceil \ sqrt {M} \ right \ rceil $ erfüllt Suchen wir nach $ i, q $. Nach dem Satz von Fermat reicht es aus, den Bereich von $ 0 \ leq i \ lt p $ zu überprüfen.
Da nun $ M $ eine Primzahl ist und $ 0 \ lt X \ lt M $, gilt $ \ gcd (X, M) = 1 $. Daher gibt es nur ein $ X ^ {-1} $, das $ X * X ^ {-1} \ equiv 1 \ pmod M $ im Bereich von $ 0 \ lt X ^ {-1} \ lt M $ erfüllt. Machen. Mit diesem $ X ^ {-1} $ wird der Ausdruck $ (1) $ wie folgt transformiert.
\begin{align}
X^K&\equiv Y\pmod M\\
X^{p*i+q}&\equiv Y\pmod M\\
X^q&\equiv Y*A^i\pmod M\tag{2}\\
\end{align}
Bei der Transformation der 2. in 3. Zeile setzen wir $ A = (X ^ {-1}) ^ p $.
Der Wert, den die linke Seite von $ (2) $ annehmen kann, ist $ X ^ 0 \ bmod M, X ^ 1 \ bmod M, \ Punkte, X ^ {p-1} \ bmod M $ höchstens $ p = \ left \ lceil \ sqrt {M} \ right \ rceil $ Kind. Daher berechnen wir im Voraus ein assoziatives Array (unordered_map oder HashMap), das nach $ X ^ j \ bmod M \ mapsto j $ kopiert wird. Wenn zu diesem Zeitpunkt bereits "Schlüssel" eingefügt wurde, überschreiben Sie "Wert" nicht.
Wenn Sie oben alle $ i = 0,1, \ dots, p-1 $ auf der rechten Seite von $ (2) $ markieren, können Sie das gewünschte $ i, q $ erhalten (falls nicht gefunden, $ K = -1 $). Indem das assoziative Array "value" nicht überschrieben und $ i $ in aufsteigender Reihenfolge gescannt wird, bildet das erste gefundene $ i, q $ das kleinste $ K $, das $ (1) $ erfüllt. Ich verstehe auch.
Der Rechenaufwand für die obige Lösung
-Die Berechnung von $ p $ ist eine Dichotomie und $ O (\ log M) $
Daher ist das Ganze $ O (\ sqrt {M}) $.
Dies ist das Hauptthema dieses Artikels. Wenn $ M $ eine zusammengesetzte Zahl wird, kann der obige Algorithmus nicht so angewendet werden, wie er ist. Dies liegt daran, dass $ X ^ {-1} $ möglicherweise nicht vorhanden ist. Wenn $ M $ jedoch eine zusammengesetzte Zahl ist, kann das Problem mit fast demselben Algorithmus gelöst werden.
Die Lösung ist unten gezeigt.
Verarbeiten Sie zunächst den Fall von $ M = 1 $. In diesem Fall erfüllt $ K = 0 $ für $ X, Y $ $ (1) $ und ist das Minimum.
Nachfolgend $ M> 1 $.
$ g: = \ gcd {(X, M)} $. Wenn $ g = 1 $ ist, existiert $ X ^ {-1} $, so dass der obige Algorithmus so angewendet werden kann, wie er ist, also endet er hier. Wenn es $ g \ neq 1 $ ist, ist das nicht der Fall, also werde ich ein wenig darüber nachdenken.
Es zerlegt $ X und M $ in Produkte wie $ X = g * X '$ und $ M = g * M' $.
Einsetzen dieser in $ (1) $ ergibt $ (g * X ') ^ K \ equiv Y \ pmod {(g * M')} $. Daher gibt es eine ganze Zahl $ n
Wenn $ K> 0 $ ist, muss $ Y $ ein Vielfaches von $ g $ sein, daher wird $ Y $ auch als $ Y = g * Y '$ zerlegt ($ Y $ ist $). Es gibt kein $ K $, das $ (1) $ erfüllt, es sei denn, es ist ein Vielfaches von g $). Sie können mit der Berechnung der $ (3) $ -Formel fortfahren und die Formel $ (4) $ erhalten.
\begin{align}
g*X'*(g*X')^{K-1}-g*Y'&=n*g*M'\\
X'*(g*X')^{K-1}-Y'&=n*M'\\
X'*(g*X')^{K-1}&\equiv Y'\pmod{M'}\tag{4}
\end{align}
Außerdem ist $ X '* {X'} ^ {-1} \ equiv 1 \ pmod {M '} $, $ 0 \ lt {X' } ^ {-1} \ lt Es gibt nur ein $ {X '} ^ {-1} $, das zu M' $ wird. Auf diese Weise erhalten wir die $ (5) $ -Gleichung.
\begin{align}
X'*(g*X')^{K-1}&\equiv Y'\pmod{M'}\\
(g*X')^{K-1}&\equiv Y'*{X'}^{-1}\pmod{M'}\\
X^L&\equiv Z\pmod{M'}\tag{5}\\
\end{align}
Bei der Transformation der 2. in 3. Zeile setzen wir $ L = K-1, \ Z = Y '* {X'} ^ {-1} $.
Da $ (5) $ ein diskretes logarithmisches Problem ist, das kleiner als das ursprüngliche Problem ist, kann dieses Problem rekursiv gelöst werden. Unter Berücksichtigung der später beschriebenen Analyse des Berechnungsbetrags ist auch ersichtlich, dass diese Wiederholung immer endet. Wenn die kleinste nicht negative ganze Zahl $ L $ existiert, die $ (5) $ erfüllt, ist $ L + 1 $ die Antwort, und wenn $ L $ nicht existiert, gibt es keine Lösung für das ursprüngliche Problem.
Zu beachten ist, dass $ \ gcd {(X, M ')} = 1 $ nicht immer der Fall ist.
Wenn zum Beispiel $ (X, M) = (20, 24) $ ist, dann ist $ g = \ gcd {(X, M)} = 4 $, also $ M '= M / g = 6 $. Zu diesem Zeitpunkt ist $ \ gcd {(X, M ')} = 2 \ neq 1 $.
Der Rechenaufwand für diese Lösung beträgt
(Betrag der rekursiven Berechnung bis $ \ gcd {(X, M)} = 1 $) + (Berechnungsbetrag des Baby-Schritt-Riesenschritts)
ist. Es ist notwendig, sich für $ \ gcd {(X, M)} \ neq 1 $ zurückzuziehen, wobei $ (X, M) $ $ (X, M / \ gcd {(X, M)}) $ ist Weitermachen mit. Zu diesem Zeitpunkt wird $ M $ bei jeder Rückverfolgung auf weniger als die Hälfte reduziert, da $ \ gcd {(X, M)}> = 2 $ ist. Daher beträgt die Anzahl der Wiederholungen $ O (\ log M) $ und die Anzahl der Wiederholungen $ O ((\ log M) ^ 2) $, da die euklidische Methode der gegenseitigen Teilung nur eine bestimmte Anzahl von Malen jeder Wiederholung durchgeführt wird. ..
Aus dem oben Gesagten konnten wir das diskrete logarithmische Problem mit beliebigen Mods mit einem Gesamtberechnungsbetrag von $ O (\ sqrt M) $ lösen.
Abschließend möchte ich mit einem Java-Programm schließen, das diskrete logarithmische Probleme mit beliebigen Mods löst.
Zur Überprüfung verwendetes Problem: Diskreter Logarithmus Einreichung: Diskreter Logarithmus
DiscreteLogarithm.java
public class DiscreteLogarithm {
/**
*Löse das diskrete logarithmische Problem mit einem beliebigen Mod. Das heißt, x^k=Finden Sie die kleinste nicht negative ganze Zahl k, die y mod m erfüllt.
* @Unten im Parameter x-Protokoll
* @param y {@code x}冪
* @param m mod
* @return x^k=Die kleinste nicht negative ganze Zahl, die y mod m k erfüllt. Wenn es nicht existiert-Rückgabe 1.
*/
public static long log(long x, long y, long m) {
if ((x %= m) < 0) x += m;
if ((y %= m) < 0) y += m;
// m =1 Fall handhaben
if (m == 1) return 0;
// y = 1 (k = 0)Fälle behandeln
if (y == 1) return 0;
long[] gi = gcdInv(x, m);
// g=gcd(x,m), ix*x=g mod m
long g = gi[0], ix = gi[1];
if (g != 1) {
//y ist gcd(x, g)Muss ein Vielfaches von sein
if (y % g != 0) return -1;
m /= g;
y = (y / g) * ix;
//Lösen Sie kleine Probleme
long log = log(x, y, m);
//Wenn es keine Lösung für das kleine Problem gibt, gibt es keine Lösung für das ursprüngliche Problem
if (log < 0) return -1;
//Wenn die Antwort auf die kleine Frage l lautet, lautet die Antwort auf die ursprüngliche Frage l+ 1
return log + 1;
}
// gcd(x, g) =1 ist Baby-step Giant-Kann mit Schritt gelöst werden
return coprimeLog(x, y, m, ix);
}
/**
*Baby, wenn x und m sich gegenseitig ausschließen-step Giant-Lösen Sie das diskrete logarithmische Problem schrittweise.
* @Unten im Parameter x-Protokoll
* @param y {@code x}冪
* @param m mod
* @param ix mod {@code m}Im{@code x}Inverses Multiplikatorelement x^{-1}
* @return x^k=Die kleinste nicht negative ganze Zahl, die y mod m k erfüllt. Wenn es nicht existiert-Rückgabe 1.
*/
private static long coprimeLog(long x, long y, long m, long ix) {
long p = ceilSqrt(m);
java.util.HashMap<Long, Long> memo = new java.util.HashMap<>();
for (long i = 0, powx = 1; i < p; i++) {
memo.putIfAbsent(powx, i);
powx = powx * x % m;
}
long a = pow(ix, p, m);
for (long i = 0, ypowa = y; i < p; i++) {
long q = memo.getOrDefault(ypowa, -1l);
if (q >= 0) return p * i + q;
ypowa = ypowa * a % m;
}
return -1l;
}
/**
* (x-1)^2 < n <= x^Dichotomisiere x, das 2 erfüllt.
* @Eine Ganzzahl, die param n sqrt benötigt
* @return (x-1)^2 < n <= x^Befriedige 2 x
*/
private static long ceilSqrt(long n) {
long l = -1, r = n;
while (r - l > 1) {
long m = (r + l) >> 1;
if (m * m >= n) r = m;
else l = m;
}
return r;
}
/**
* a^b mod m wird nach der dichotomen Potenzmethode berechnet.
* @param a bottom
* @param b index
* @param m mod
* @return a^b mod m
*/
private static long pow(long a, long b, long m) {
if (m == 1) return 0;
if ((a %= m) < 0) a += m;
long pow = 1;
for (long p = a, c = 1; b > 0;) {
long lsb = b & -b;
while (lsb != c) {
c <<= 1;
p = (p * p) % m;
}
pow = (pow * p) % m;
b ^= lsb;
}
return pow;
}
/**
* g = gcd(x, m), a * x =Ein Paar, das g mod m erfüllt(g, x)Wird nach der euklidischen Methode der gegenseitigen Teilung berechnet.
* @param a
* @param m mod
* @return g = gcd(x, m), a * x =Ein Paar, das g mod m erfüllt(g, x)
*/
private static long[] gcdInv(long a, long m) {
if ((a %= m) < 0) a += m;
if (a == 0) return new long[]{m, 0};
long s = m, t = a;
long m0 = 0, m1 = 1;
while (t > 0) {
long u = s / t;
s -= t * u;
m0 -= m1 * u;
long tmp;
tmp = s; s = t; t = tmp;
tmp = m0; m0 = m1; m1 = tmp;
}
if (m0 < 0) m0 += m / s;
return new long[]{s, m0};
}
}
Recommended Posts