| dbpprop:abstract
|
- In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga(b) is a solution of the equation a = b over the real or complex numbers. Similarly, if g and h are elements of a finite cyclic group G then a solution x of the equation g = h is called a discrete logarithm to the base g of h in the group G.
- In der Gruppentheorie ist der diskrete Logarithmus das Analogon zum gewöhnlichen Logarithmus aus der Analysis; diskret kann in diesem Zusammenhang etwa wie ganzzahlig verstanden werden. Die diskrete Exponentiation in einer zyklischen Gruppe bildet eine Umkehrfunktion des diskreten Logarithmus. Als Vergleich die stetige Exponentialfunktion ist eine Umkehrfunktion des gewöhnlichen Logarithmus. Als ein Beispiel diene das Rechnen modulo n. Der diskrete Logarithmus ist hier die kleinste Lösung x der Gleichung <math>a^x \equiv m \mod p</math> bei gegebenen natürlichen Zahlen m, a und der Primzahl p. Da sich die diskrete Exponentiation leicht (im Sinne der Komplexitätstheorie) berechnen lässt, während für die Umkehrfunktion, den diskreten Logarithmus, meist nur schwere (im Sinne der Komplexitätstheorie) Algorithmen bekannt sind, eignet sich die diskrete Exponentiation als Einwegfunktion in der Kryptografie. Anwendungsbeispiele sind u. a. Diffie-Hellman-Schlüsselaustausch Elgamal-Kryptosystem DSA-Verfahren Elliptische-Kurven-Kryptosystem
- En matemàtiques, en particular en àlgebra abstracta i les seves aplicacions, els logaritmes discrets són anàlegs als logaritmes ordinaris però aplicats a grup. En particular, un logaritme ordinari <math>\log_a(b)</math> és una solució de l'equació <math>a^x=b</math> sobre nombres reals o complexos. De forma similar, si <math>g</math> i <math>h</math> són elements d'un grup cíclic <math>G</math> llavors de una solució <math>x</math> de l'equació <math>g^x=h</math> se'n diu un logaritme discret en base <math>g</math> de <math>h</math> en el grup <math>G</math>.
- Nechť m, q, k, Y jsou přirozená čísla, pro něž platí <math>Y = q^{k} mod \quad m</math>. Potom každé číslo k, odpovídající uvedené rovnici nazveme diskrétní logaritmus o základu q z Y vzhledem k modulu m. Tato definice nedefinuje číslo k jednoznačně, proto se někdy upravuje tak, že ze všech možných diskrétních logaritmů ve smyslu předchozí definice se vybere ten nejmenší.
- Se conoce como logaritmo discreto de x en base a módulo n a resolver la ecuación x=a^y\;mod\ n donde x,n y a son constantes e y es la incógnita. A partir de ahora notaremos esta situación como y=log\ disc_a(x) El hecho de aplicar aritmética modular hace el problema de hallar y irresoluble en un tiempo razonable, por esto se usa, al igual que otros problemas con algoritmos poco eficientes, en criptografía, en el método de intercambio de claves de Diffie-Hellman o en el sistema de ElGamal. Una definición más rigurosa es la siguiente: Sea (G,*) un grupo cíclico finito con n elementos y donde * es la multiplicación, es decir G=\{e,g,g^2,... ,g^{n-1}\}. Como hemos dicho que (G,*) es cíclico sabemos que \forall a\in G \; \exists k\in \mathbb{Z}\;|\;a=g^k. Entonces definimos log \ disc_g:G \rightarrow \mathbb{Z}/n\mathbb{Z} como la función que asigna valores de la siguiente manera x\longmapsto k\; |\; x=g^k\; mod\; n Algunas de las propiedades de esta función son log\ disc_g(x*y)=log\ disc_g(x)+log\ disc_g(y) \forall\ t\in\mathbb{N},log\ disc_g(c^t)=tlog\ disc_g(c) log\ disc_g(1)=0 log\ disc_g(g)=1 Aquí sigue vigente la fórmula del cambio de base de los logaritmos continuos siempre que c sea otro generador log\ disc_c(x)=log\ disc_c(g)*log\ disc_g(x)
- En algèbre générale et dans ses applications d'arithmétique modulaire, le logarithme discret est défini en théorie des groupes par analogie avec le logarithme ordinaire. On considère un groupe cyclique G d'ordre n (dont la loi sera notée multiplicativement) et un générateur b de G. Alors chaque élément x de G peut être écrit sous la forme x = b pour un certain entier k; de plus, deux quelconques de ces entiers sont nécessairement congrus modulo n. Il est ainsi possible de définir une fonction <math>\log_b</math> de <math>G</math> dans <math>Z_n</math> (où <math>Z_n</math> désigne l'anneau des entiers modulo n) en associant à tout élément x de <math>Z_n</math> la classe de congruence de k modulo n. Cette fonction est un isomorphisme de groupe, appelé logarithme discret de base b. La formule familière de changement de bases pour les logarithmes ordinaires reste valide : si c est un autre générateur de G, alors : <math>\log_c (x) = \log_c(b) \cdot \log_b(x)</math> Pour certains groupes, le calcul des logarithmes discrets s'avère difficile, tandis que le problème inverse de l'exponentiation discrète ne l'est pas; cette asymétrie est exploitée dans certaines applications en cryptologie. Les choix populaires de G en cryptologie sont les groupes cycliques (Zp) (constitués des nombres {1,... ,p − 1} muni de la multiplication modulo le nombre premier p); voir le logarithme discret du cryptosystème d'ElGamal, l'échange de clés Diffie-Hellman et l'algorithme de signature numérique DSA. Il est peut-être plus simple de comprendre les logarithmes discrets dans ce groupe avec un exemple : Pour trouver la k puissance de l’un des nombres de ce groupe, ce qui se nomme exponentiation discrète, il faut élever ce nombre à la puissance k et calculer le reste de la division par p. Par exemple : 3 = 243. Le reste de la division entière de 243 par 7 étant 5, 3 dans le groupe (Z7) est 5. Le logarithme discret est le problème inverse : étant donné 3 ≡ 5 (mod 7), quel est le plus petit k pour lequel cette proposition est vraie ? L'algorithme de Pohlig-Hellman peut être utilisé pour calculer les logarithmes discrets dans ces groupes si p-1 est un produit de petits nombres premiers, ce qui oblige à l'éviter dans ce genre d'applications. Le calcul d'index est une autre méthode pour calculer les logarithmes discrets dans ces groupes, comme l'attaque anniversaire. Des applications plus récentes de la cryptologie utilisent les logarithmes discrets dans les sous-groupes cycliques de courbes elliptiques sur les corps finis. Voir cryptologie sur les courbes elliptiques.
- In matematica ed in particolare nell'algebra e nelle sue applicazioni i logaritmi discreti sono il corrispettivo dei logaritmi ordinari per l'aritmetica modulare. Il problema del calcolo dei logaritmi discreti ha notevoli somiglianze con quello della fattorizzazione dei numeri interi, in quanto entrambi i problemi sono supposti difficili (non sono noti algoritmi che li risolvono in tempo polinomiale), algoritmi dell'uno sono spesso adattati all'altro e viceversa, ed entrambi sono stati utilizzati come base teorica per la costruzione di sistemi crittografici. Tali sistemi crittografici fondano la propria sicurezza sulla supposta difficoltà di tali problemi.
- 代数学における離散対数（りさんたいすう、discrete logarithm）とは、群論における対数の類似物である。 離散対数を計算する問題は整数の因数分解と以下の点が共通している： 両方とも難しい（量子コンピュータ以外では効率的に解くアルゴリズムが得られていない） 片方に対するアルゴリズムはしばしばもう片方にも利用できる 問題の困難性が暗号系の構築に利用されている
- Het Discrete Logaritme Probleem (DLP) is gedefinieerd in elke cyclische groep.
- Logarytm dyskretny elementu <math>b (przy podstawie <math>a) w danej grupie skończonej jest to taka liczba całkowita <math>c, że w grupie zachodzi równość (stosując notację multiplikatywną dla działania grupowego): <math>a^c = b \;. Logarytm dyskretny nie zawsze istnieje, a jeśli istnieje nie jest jednoznaczny. Np. w ciele skończonym Z11 logarytmem przy podstawie 4 z elementu 9 jest liczba 3 (ale też 8). W tym ciele nie istnieje logarytm przy podstawie 4 z elementu 7. Znalezienie logarytmu dyskretnego jest zaskakująco trudnym problemem. O ile potęgowanie wymaga <math>O(\log c) operacji - liczymy <math>a, a^2, a^4, a^8, \dots, po czym wymnażamy te z nich dla których bity c są równe 1, to jedyną prostą metodą rozwiązywania problemu logarytmu dyskretnego jest przeszukanie wszystkich możliwych <math>c. Istnieją efektywniejsze metody, jednak żadna z ogólnych metod nie ma złożoności wielomianowej wobec ilości bitów wejścia (istnieją takie dla pewnych specyficznych klas liczb pierwszych, których należy więc w kryptografii unikać). Najszybszy algorytm (sito ciała liczbowego) obliczania logarytmu dyskretnego w GF(p) ma złożoność czasową: <math>e^{c\cdot\log^{\frac{1}{3}}_2(p) \cdot \log^{\frac{2}{3}}_2(\log_2)} gdzie c jest pewną stałą. Jedną z metod obliczania logarytmu dyskretnego w GF(p) jest redukcja Pohliga-Hellmana. Trudność znalezienia logarytmu dyskretnego jest podstawą istnienia wielu algorytmów kryptograficznych, takich jak ElGamal i protokół Diffiego-Hellmana czy kryptografia oparta na krzywych eliptycznych.
- Дискретное логарифмирование (DLOG) – задача обращения функции <math>g^x</math> в некоторой конечной мультипликативной группе <math>G</math>. Наиболее часто задачу дискетного логарифмирования рассматривают в группе обратимых элементов кольца вычетов, в мультипликативной группе конечного поля, или в группе точек на эллиптической кривой над конечным полем. Эффективные алгоритмы для решения задачи дискетного логарифмирования в общем случае неизвестны. Для заданных g и a решение x уравнения <math>g^x = a</math> называется дискретным логарифмом элемента a по основанию g. В случае, когда G является группой обратимых элементов кольца вычетов по модулю m, решение называют также индексом числа a по основанию g. Индекс числа a по основанию g гарантированно существует, если g является первообразным корнем по модулю m.
- 離散對數是在整數中，一種基於同餘運算和原根的一種對數運算。
|
| rdfs:comment
|
- In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga(b) is a solution of the equation a = b over the real or complex numbers. Similarly, if g and h are elements of a finite cyclic group G then a solution x of the equation g = h is called a discrete logarithm to the base g of h in the group G.
- In der Gruppentheorie ist der diskrete Logarithmus das Analogon zum gewöhnlichen Logarithmus aus der Analysis; diskret kann in diesem Zusammenhang etwa wie ganzzahlig verstanden werden. Die diskrete Exponentiation in einer zyklischen Gruppe bildet eine Umkehrfunktion des diskreten Logarithmus. Als Vergleich die stetige Exponentialfunktion ist eine Umkehrfunktion des gewöhnlichen Logarithmus. Als ein Beispiel diene das Rechnen modulo n.
- En matemàtiques, en particular en àlgebra abstracta i les seves aplicacions, els logaritmes discrets són anàlegs als logaritmes ordinaris però aplicats a grup. En particular, un logaritme ordinari <math>\log_a(b)</math> és una solució de l'equació <math>a^x=b</math> sobre nombres reals o complexos.
- Nechť m, q, k, Y jsou přirozená čísla, pro něž platí <math>Y = q^{k} mod \quad m</math>. Potom každé číslo k, odpovídající uvedené rovnici nazveme diskrétní logaritmus o základu q z Y vzhledem k modulu m. Tato definice nedefinuje číslo k jednoznačně, proto se někdy upravuje tak, že ze všech možných diskrétních logaritmů ve smyslu předchozí definice se vybere ten nejmenší.
- Se conoce como logaritmo discreto de x en base a módulo n a resolver la ecuación x=a^y\;mod\ n donde x,n y a son constantes e y es la incógnita. A partir de ahora notaremos esta situación como y=log\ disc_a(x) El hecho de aplicar aritmética modular hace el problema de hallar y irresoluble en un tiempo razonable, por esto se usa, al igual que otros problemas con algoritmos poco eficientes, en criptografía, en el método de intercambio de claves de Diffie-Hellman o en el sistema de ElGamal.
- En algèbre générale et dans ses applications d'arithmétique modulaire, le logarithme discret est défini en théorie des groupes par analogie avec le logarithme ordinaire. On considère un groupe cyclique G d'ordre n (dont la loi sera notée multiplicativement) et un générateur b de G. Alors chaque élément x de G peut être écrit sous la forme x = b pour un certain entier k; de plus, deux quelconques de ces entiers sont nécessairement congrus modulo n.
- In matematica ed in particolare nell'algebra e nelle sue applicazioni i logaritmi discreti sono il corrispettivo dei logaritmi ordinari per l'aritmetica modulare.
- Het Discrete Logaritme Probleem (DLP) is gedefinieerd in elke cyclische groep.
- Logarytm dyskretny elementu <math>b (przy podstawie <math>a) w danej grupie skończonej jest to taka liczba całkowita <math>c, że w grupie zachodzi równość (stosując notację multiplikatywną dla działania grupowego): <math>a^c = b \;. Logarytm dyskretny nie zawsze istnieje, a jeśli istnieje nie jest jednoznaczny. Np. w ciele skończonym Z11 logarytmem przy podstawie 4 z elementu 9 jest liczba 3 (ale też 8).
- Дискретное логарифмирование (DLOG) – задача обращения функции <math>g^x</math> в некоторой конечной мультипликативной группе <math>G</math>.
- 離散對數是在整數中，一種基於同餘運算和原根的一種對數運算。
|
![[RDF Data]](/statics/sw-cube.png)
