Beaucoup de gens connaissent Baby-step Giant-step comme un algorithme pour résoudre le problème du logarithme discret. Cependant, je n'ai trouvé aucun article traitant de mods arbitraires, donc j'écrirai à ce sujet.
Premièrement, le problème logarithmique discret fait référence aux problèmes suivants. (Si vous connaissez la solution de Baby-step Giant-step, sautez-la)
Étant donné les entiers positifs $ M $ et les entiers $ X, Y $, qui sont $ 0 \ leq X, Y \ lt M $.
Trouvez l'entier non négatif (minimum) $ K $ qui satisfait
Vous pouvez résoudre ce problème comme suit.
Tout d'abord, traitons le cas simple de $ X = 0 $. Si $ Y = 0 $, alors $ K = 1 $, si $ Y \ neq 0 $, alors $ K = -1 $ (n'existe pas). Cependant, ici, $ 0 ^ 0 = 1 $ est défini.
Ensuite, considérons le cas de $ X \ neq 0 $. Un entier non négatif tel que $ K = p * i + q \ (0 \ leq q \ lt p) $ satisfait $ (1) $ comme $ p = \ left \ lceil \ sqrt {M} \ right \ rceil $ Cherchons $ i, q $. A partir du théorème de Fermat, il suffit de vérifier la plage de $ 0 \ leq i \ lt p $.
Maintenant, puisque $ M $ est un nombre premier et que $ 0 \ lt X \ lt M $, $ \ gcd (X, M) = 1 $ tient. Par conséquent, il n'y a qu'un seul $ X ^ {-1} $ qui satisfait $ X * X ^ {-1} \ equiv 1 \ pmod M $ dans la plage de $ 0 \ lt X ^ {-1} \ lt M $. Faire. En utilisant cette $ X ^ {-1} $, l'expression $ (1) $ est transformée comme suit.
\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}
Dans la transformation de la 2ème à la 3ème ligne, nous mettons $ A = (X ^ {-1}) ^ p $.
La valeur que le côté gauche de $ (2) $ peut prendre est $ X ^ 0 \ bmod M, X ^ 1 \ bmod M, \ dots, X ^ {p-1} \ bmod M $ au plus $ p = \ left \ lceil \ sqrt {M} \ right \ rceil $ Kind. Par conséquent, nous allons calculer à l'avance un tableau associatif (ʻunordered_mapouHashMap`) qui sera copié dans $ X ^ j \ bmod M \ mapsto j $. À ce stade, si «clé» a déjà été insérée, n'écrasez pas la «valeur».
À partir de ce qui précède, si vous cochez tous les $ i = 0,1, \ points, p-1 $ sur le côté droit de $ (2) $, vous pouvez obtenir le $ i, q $ souhaité (si non trouvé, $ K = -1 $). En n'écrasant pas le tableau associatif «value» et en balayant $ i $ dans l'ordre croissant, le premier $ i, q $ trouvé constitue le plus petit $ K $ qui satisfait $ (1) $. Je comprends aussi.
La quantité de calcul pour la solution ci-dessus
-Le calcul de $ p $ est une dichotomie et $ O (\ log M) $
Par conséquent, le tout est $ O (\ sqrt {M}) $.
C'est le sujet principal de cet article. Lorsque $ M $ devient un nombre composite, l'algorithme ci-dessus ne peut pas être appliqué tel quel. C'est parce que $ X ^ {-1} $ peut ne pas exister. Cependant, si $ M $ est un nombre composite, le problème peut être résolu avec presque le même algorithme.
La solution est présentée ci-dessous.
Tout d'abord, traitez le cas de $ M = 1 $. Dans ce cas, pour tout $ X, Y $, $ K = 0 $ satisfait $ (1) $ et est le minimum.
Par la suite, M $> 1 $.
$ g: = \ gcd {(X, M)} $. Si $ g = 1 $, $ X ^ {-1} $ existe, donc l'algorithme ci-dessus peut être appliqué tel quel, donc il se termine ici. Si c'est $ g \ neq 1 $, ce n'est pas le cas, alors je vais imaginer un peu.
Il décompose $ X et M $ en produits tels que $ X = g * X '$ et $ M = g * M' $.
En les substituant à $ (1) $, on obtient $ (g * X ') ^ K \ equiv Y \ pmod {(g * M')} $. Par conséquent, il existe un entier $ n
Lorsque $ K> 0 $, $ Y $ doit être un multiple de $ g $, donc $ Y $ est également décomposé en $ Y = g * Y '$ ($ Y $ est $). Il n'y a pas de $ K $ qui satisfait $ (1) $ sauf s'il s'agit d'un multiple de g $). Vous pouvez procéder au calcul de la formule $ (3) $ et obtenir la formule $ (4) $.
\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}
De plus, puisque $ \ gcd {(X ', M')} = 1 $ tient, $ X '* {X'} ^ {-1} \ equiv 1 \ pmod {M '} $, $ 0 \ lt {X' } ^ {-1} \ lt Il n'y a qu'un seul $ {X '} ^ {-1} $ qui devient M' $. En utilisant ceci, nous obtenons l'équation $ (5) $.
\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}
Dans la transformation de la 2ème à la 3ème ligne, nous mettons $ L = K-1, \ Z = Y '* {X'} ^ {-1} $.
Puisque $ (5) $ est un problème logarithmique discret de plus petite taille que le problème d'origine, ce problème peut être résolu de manière récursive. En outre, compte tenu de l'analyse des montants de calcul décrite plus loin, nous pouvons voir que cette récurrence se termine toujours. Si le plus petit entier non négatif $ L $ qui satisfait $ (5) $ existe, alors $ L + 1 $ est la réponse, et si $ L $ n'existe pas, il n'y a pas de solution au problème d'origine.
Une chose à noter est que $ \ gcd {(X, M ')} = 1 $ n'est pas toujours le cas.
Par exemple, si $ (X, M) = (20, 24) $, alors $ g = \ gcd {(X, M)} = 4 $, donc $ M '= M / g = 6 $. A ce moment, $ \ gcd {(X, M ')} = 2 \ neq 1 $.
La quantité de calcul pour cette solution est
(Montant du calcul récursif jusqu'à $ \ gcd {(X, M)} = 1 $) + (Montant du calcul de Baby-step Giant-step)
est. Il est nécessaire de se répéter quand $ \ gcd {(X, M)} \ neq 1 $, où $ (X, M) $ est $ (X, M / \ gcd {(X, M)}) $ Passer à. A ce moment, puisque $ \ gcd {(X, M)}> = 2 $, $ M $ est réduit à moins de la moitié à chaque fois qu'il est retracé. Par conséquent, le nombre de récurrences est $ O (\ log M) $, et le montant de récurrence est $ O ((\ log M) ^ 2) $ car la méthode de division mutuelle euclidienne n'est exécutée qu'un certain nombre de fois chaque récurrence. ..
À partir de ce qui précède, nous avons pu résoudre le problème logarithmique discret avec des mods arbitraires avec le montant total du calcul étant $ O (\ sqrt M) $.
Enfin, je voudrais conclure avec un programme Java qui résout des problèmes logarithmiques discrets avec des mods arbitraires.
Problème utilisé pour vérifier: Logarithme discret Soumission: Logarithme discret
DiscreteLogarithm.java
public class DiscreteLogarithm {
/**
*Résolvez le problème logarithmique discret avec un mod arbitraire. Autrement dit, x^k=Trouvez le plus petit entier non négatif k qui satisfait y mod m.
* @Bas du journal param x
* @param y {@code x}冪
* @param m mod
* @return x^k=Le plus petit entier non négatif qui satisfait y mod m k. Si ça n'existe pas-Renvoie 1.
*/
public static long log(long x, long y, long m) {
if ((x %= m) < 0) x += m;
if ((y %= m) < 0) y += m;
// m =Poignée 1 cas
if (m == 1) return 0;
// y = 1 (k = 0)Poignées de cas
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 est pgcd(x, g)Doit être un multiple de
if (y % g != 0) return -1;
m /= g;
y = (y / g) * ix;
//Résolvez les problèmes de petite taille
long log = log(x, y, m);
//S'il n'y a pas de solution pour le problème de petite taille, il n'y a pas de solution pour le problème d'origine
if (log < 0) return -1;
//Si la réponse à la question de petite taille est l, la réponse à la question initiale est l+ 1
return log + 1;
}
// gcd(x, g) =1 est bébé-step Giant-Peut être résolu avec l'étape
return coprimeLog(x, y, m, ix);
}
/**
*Bébé quand x et m sont mutuellement exclusifs-step Giant-Résolvez le problème logarithmique discret par étape.
* @Bas du journal param x
* @param y {@code x}冪
* @param m mod
* @param ix mod {@code m}Dans{@code x}Élément inverse multiplicateur x^{-1}
* @return x^k=Le plus petit entier non négatif qui satisfait y mod m k. Si ça n'existe pas-Renvoie 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^Dichotomiser x qui satisfait 2.
* @Un entier qui prend le paramètre n sqrt
* @return (x-1)^2 < n <= x^Satisfaire 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 est calculé par la méthode de puissance dichotomique.
* @param un fond
* @index param b
* @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 =Une paire qui satisfait g mod m(g, x)Est calculé par la méthode de division mutuelle euclidienne.
* @param a
* @param m mod
* @return g = gcd(x, m), a * x =Une paire qui satisfait g mod m(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