| dbo:abstract
|
- 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 un grup. En particular, un logaritme ordinari és una solució de l'equació sobre nombres reals o complexos. De manera similar, si i són elements d'un grup cíclic , llavors d'una solució de l'equació se'n diu un logaritme discret en base de en el grup . (ca)
- Nechť jsou přirozená čísla, pro něž platí . Potom každé číslo odpovídající uvedené rovnici nazveme diskrétní logaritmus o základu z vzhledem k modulu . Tato definice nedefinuje číslo 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ší. Obecně se nemusí jednat přímo o přirozená čísla modulo , diskrétní logaritmus je zobecnění klasického logaritmu pro konečné cyklické grupy. (cs)
- En matematiko, diskreta logaritmo estas grupa analogo de ordinara logaritmo. Estu (Zp)×, kiu estas la aro de entjeroj {1, …, p − 1} sub multipliko module la primo p. Se oni bezonas trovi la k-an potencon de unu el la nombroj en ĉi tiu grupo, oni povas fari ĉi tion per trovo de ĝia k-a potenco kiel entjero kaj tiam trovo la resto post divido per p. Ĉi tiu procezo estas la diskreta potencigo. Ekzemple, estu (Z17)×. Por komputi 34 en ĉi tiu grupo, oni unue komputu 34 = 81, kaj tiam dividu 81 per 17, ricevante reston 13. Tial 34 = 13 en la grupo (Z17)×. Diskreta logaritmo estas la inversa operacio. Estu donite ke 3k ≡ 13 (mod 17), kio estas la k? Reale, estas malfinie multaj respondoj, pro la modula naturo de la problemo; oni tipe strebas al la plej malgranda nenegativa respondo, kiu estas k=4. La problemo de komputado de diskreta logaritmo similas al problemo de entjera faktorigo, ĉar
* Ambaŭ problemoj estas malfacilaj, ne estas sciataj kompetentaj algoritmoj (kun polinoma tempo por ne-)
* Algoritmoj de unu problemo estas ofte adaptitaj al la alia
* La malfacileco de ambaŭ problemoj estas uzata por konstrui ĉifrikajn sistemojn. La naiva algoritmo por komputado de diskreta logaritmo estas per testado de ĉiuj eroj de la grupo, la rula tempo estas lineara de amplekso de la grupo kaj tial eksponenta tempo de kvanto de ciferoj. (eo)
- In der Gruppentheorie und Zahlentheorie 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 ist die Umkehrfunktion des diskreten Logarithmus. Als Vergleich: Die natürliche Exponentialfunktion auf den reellen Zahlen ist die Umkehrfunktion des natürlichen Logarithmus. Ein wichtiger Anwendungsfall tritt beim Rechnen modulo p auf. Der diskrete Logarithmus von zur Basis ist hier der kleinste Exponent der Gleichung bei gegebenen natürlichen Zahlen , und der Primzahl . Zum Beispiel ist beim Rechnen modulo der diskrete Logarithmus von zur Basis gleich , da ist. Da für den diskreten Logarithmus meist nur ineffiziente (im Sinne der Komplexitätstheorie) Algorithmen bekannt sind, während sich die Umkehrfunktion, die diskrete Exponentialfunktion, leicht (im Sinne der Komplexitätstheorie) berechnen lässt, eignet sich die diskrete Exponentialfunktion als Einwegfunktion in der Kryptografie. Anwendungsbeispiele sind u. a.
* Diffie-Hellman-Schlüsselaustausch
* Elgamal-Signaturverfahren
* DSA-Verfahren
* Elliptische-Kurven-Kryptosystem (de)
- En álgebra abstracta, se conoce como logaritmo discreto de y en base g, donde g e y son elementos de un grupo cíclico finito G, a la solución x de la ecuación gx = y. Esto, se puede denotar matemáticamente como: Los logaritmos discretos son análogos en teoría de grupos a los logaritmos ordinarios en análisis. Mientras que el cálculo de su inversa — la exponenciación discreta — es una tarea muy sencilla en términos computacionales, el cálculo del logaritmo discreto no es sencillo en muchos grupos. El hecho de que el problema sea «irresoluble» en un tiempo razonable si se utiliza aritmética modular hace que esto se use en criptografía, en el método de intercambio de claves de Diffie-Hellman o en el sistema de ElGamal. (es)
- In mathematics, for given real numbers a and b, the logarithm logb a is a number x such that bx = a. Analogously, in any group G, powers bk can be defined for all integers k, and the discrete logarithm logb a is an integer k such that bk = a. In number theory, the more commonly used term is index: we can write x = indr a (mod m) (read "the index of a to the base r modulo m") for rx ≡ a (mod m) if r is a primitive root of m and gcd(a,m) = 1. Discrete logarithms are quickly computable in a few special cases. However, no efficient method is known for computing them in general. Several important algorithms in public-key cryptography, such as ElGamal base their security on the assumption that the discrete logarithm problem over carefully chosen groups has no efficient solution. (en)
- Le logarithme discret est un objet mathématique utilisé en cryptologie. C'est l'analogue du logarithme réel qui est la réciproque de l'exponentielle, mais dans un groupe cyclique G fini. Le logarithme discret est utilisé pour la cryptographie à clé publique, typiquement dans l'échange de clés Diffie-Hellman et le chiffrement El Gamal. La raison est que, pour un certain nombre de groupes, on ne connait pas d'algorithme efficace pour le calcul du logarithme discret, alors que celui de la réciproque, l'exponentiation, se réalise en un nombre de multiplications logarithmique en la taille de l'argument (voir exponentiation rapide), (fr)
- 代数学における離散対数（りさんたいすう、英: discrete logarithm）とは、通常の対数の群論的な類似物である。離散対数を計算する問題は整数の因数分解と以下の点が共通している：
* 両方とも難しい（量子コンピュータ以外では効率的に解くアルゴリズムが得られていない）
* 片方に対するアルゴリズムはしばしばもう片方にも利用できる
* 問題の困難性が暗号系の構築に利用されている (ja)
- 이산 로그(離散--, discrete logarithm)는 일반 로그와 비슷하게 군론에서 정의된 연산으로, 를 만족하는 를 가리킨다. 이산 대수(離散對數)라고 부르기도 한다. (ko)
- In de wiskunde is de discrete logaritme voor een groep met vermenigvuldiging de inverse functie van machtsverheffen. Het is het analogon van de gewone logaritme voor de reële getallen. Onder de term 'discreet' moet hier 'geheeltallig' verstaan worden. In een cylische groep zijn alle elementen een macht van een voortbrengend element. Die machten zijn meestal eenvoudig te berekenen. Moeilijker is het van een gegeven element te bepalen welke macht het is van het voortbrengende element en er is geen algemene methode daarvoor bekend. In de cryptografie maakt men daarvan gebruik door een zorgvuldige keuze van de groepsgrootte. De discrete logaritme is vergelijkbaar met een array-index. Bij een gegeven index is het relatief eenvoudig het array-element te vinden. Omgekeerd is het in het algemeen lastig voor een bepaalde waarde van een element de bijbehorende index te bepalen, anders dan door het array te doorzoeken. (nl)
- 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. In particolare, il logaritmo discreto trova applicazione nella crittografia basata su curve ellittiche. Tali sistemi crittografici fondano la propria sicurezza sulla supposta difficoltà di tali problemi. (it)
- Logarytm dyskretny elementu przy podstawie w danej grupie skończonej – liczba całkowita dla której zachodzi równość (w notacji multiplikatywnej): Logarytm dyskretny nie zawsze istnieje, a jeśli istnieje, może nie być jednoznaczny. Np. w ciele skończonym 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 operacji – liczymy 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 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ą: 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. (pl)
- Na matemática, especialmente em álgebra abstrata e suas aplicações, logaritmos discretos são grupos análogos a logaritmos naturais. Em particular, um logaritmo loga(b) é a solução de uma equação ax = b sobre os reais ou complexos. De maneira análoga, se g e h são elementos de um grupo cíclico finito G então a solução x da equação gx = h é chamada logaritmo discreto na base g de h no grupo G. (pt)
- Дискретное логарифмирование (DLOG) — задача обращения функции в некоторой конечной мультипликативной группе . Наиболее часто задачу дискретного логарифмирования рассматривают в мультипликативной группе кольца вычетов или конечного поля, а также в группе точек эллиптической кривой над конечным полем. Эффективные алгоритмы для решения задачи дискретного логарифмирования в общем случае неизвестны. Для заданных g и a решение x уравнения называется дискретным логарифмом элемента a по основанию g. В случае, когда G является мультипликативной группой кольца вычетов по модулю m, решение называют также индексом числа a по основанию g. Индекс числа a по основанию g гарантированно существует, если g является первообразным корнем по модулю m. (ru)
- 在整數中，離散對數（英語：Discrete logarithm）是一種基於同餘運算和原根的一種對數運算。而在實數中對數的定義 logb a 是指對於給定的 a 和 b，有一個數 x，使得bx = a。相同地在任何群 G中可為所有整數 k定義一個冪數為 bk，而離散對數 logb a是指使得 bk = a的整數 k。 離散對數在一些特殊情況下可以快速計算。然而，通常沒有具非常效率的方法來計算它們。公鑰密碼學中幾個重要算法的基礎，是假設尋找離散對數的問題解，在仔細選擇過的群中，並不存在有效率的求解算法。 (zh)
- В математиці, особливо в абстрактній алгебрі і її застосуваннях, дискретний логарифм — теоретико-груповий аналог звичайного логарифма. Зокрема, звичайний логарифм loga(b) — це розв'язок рівняння ax = b у полі дійсних або комплексних чисел. Подібно, якщо g і h елементи зі скінченної циклічної групи G, тоді розв'язок x рівняння gx = h зветься дискретним логарифмом h за основою g в групі G. (uk)
|
| rdfs:comment
|
- 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 un grup. En particular, un logaritme ordinari és una solució de l'equació sobre nombres reals o complexos. De manera similar, si i són elements d'un grup cíclic , llavors d'una solució de l'equació se'n diu un logaritme discret en base de en el grup . (ca)
- Nechť jsou přirozená čísla, pro něž platí . Potom každé číslo odpovídající uvedené rovnici nazveme diskrétní logaritmus o základu z vzhledem k modulu . Tato definice nedefinuje číslo 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ší. Obecně se nemusí jednat přímo o přirozená čísla modulo , diskrétní logaritmus je zobecnění klasického logaritmu pro konečné cyklické grupy. (cs)
- Le logarithme discret est un objet mathématique utilisé en cryptologie. C'est l'analogue du logarithme réel qui est la réciproque de l'exponentielle, mais dans un groupe cyclique G fini. Le logarithme discret est utilisé pour la cryptographie à clé publique, typiquement dans l'échange de clés Diffie-Hellman et le chiffrement El Gamal. La raison est que, pour un certain nombre de groupes, on ne connait pas d'algorithme efficace pour le calcul du logarithme discret, alors que celui de la réciproque, l'exponentiation, se réalise en un nombre de multiplications logarithmique en la taille de l'argument (voir exponentiation rapide), (fr)
- 代数学における離散対数（りさんたいすう、英: discrete logarithm）とは、通常の対数の群論的な類似物である。離散対数を計算する問題は整数の因数分解と以下の点が共通している：
* 両方とも難しい（量子コンピュータ以外では効率的に解くアルゴリズムが得られていない）
* 片方に対するアルゴリズムはしばしばもう片方にも利用できる
* 問題の困難性が暗号系の構築に利用されている (ja)
- 이산 로그(離散--, discrete logarithm)는 일반 로그와 비슷하게 군론에서 정의된 연산으로, 를 만족하는 를 가리킨다. 이산 대수(離散對數)라고 부르기도 한다. (ko)
- 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. In particolare, il logaritmo discreto trova applicazione nella crittografia basata su curve ellittiche. Tali sistemi crittografici fondano la propria sicurezza sulla supposta difficoltà di tali problemi. (it)
- Na matemática, especialmente em álgebra abstrata e suas aplicações, logaritmos discretos são grupos análogos a logaritmos naturais. Em particular, um logaritmo loga(b) é a solução de uma equação ax = b sobre os reais ou complexos. De maneira análoga, se g e h são elementos de um grupo cíclico finito G então a solução x da equação gx = h é chamada logaritmo discreto na base g de h no grupo G. (pt)
- 在整數中，離散對數（英語：Discrete logarithm）是一種基於同餘運算和原根的一種對數運算。而在實數中對數的定義 logb a 是指對於給定的 a 和 b，有一個數 x，使得bx = a。相同地在任何群 G中可為所有整數 k定義一個冪數為 bk，而離散對數 logb a是指使得 bk = a的整數 k。 離散對數在一些特殊情況下可以快速計算。然而，通常沒有具非常效率的方法來計算它們。公鑰密碼學中幾個重要算法的基礎，是假設尋找離散對數的問題解，在仔細選擇過的群中，並不存在有效率的求解算法。 (zh)
- В математиці, особливо в абстрактній алгебрі і її застосуваннях, дискретний логарифм — теоретико-груповий аналог звичайного логарифма. Зокрема, звичайний логарифм loga(b) — це розв'язок рівняння ax = b у полі дійсних або комплексних чисел. Подібно, якщо g і h елементи зі скінченної циклічної групи G, тоді розв'язок x рівняння gx = h зветься дискретним логарифмом h за основою g в групі G. (uk)
- In der Gruppentheorie und Zahlentheorie 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 ist die Umkehrfunktion des diskreten Logarithmus. Als Vergleich: Die natürliche Exponentialfunktion auf den reellen Zahlen ist die Umkehrfunktion des natürlichen Logarithmus.
* Diffie-Hellman-Schlüsselaustausch
* Elgamal-Signaturverfahren
* DSA-Verfahren
* Elliptische-Kurven-Kryptosystem (de)
- En matematiko, diskreta logaritmo estas grupa analogo de ordinara logaritmo. Estu (Zp)×, kiu estas la aro de entjeroj {1, …, p − 1} sub multipliko module la primo p. Se oni bezonas trovi la k-an potencon de unu el la nombroj en ĉi tiu grupo, oni povas fari ĉi tion per trovo de ĝia k-a potenco kiel entjero kaj tiam trovo la resto post divido per p. Ĉi tiu procezo estas la diskreta potencigo. Ekzemple, estu (Z17)×. Por komputi 34 en ĉi tiu grupo, oni unue komputu 34 = 81, kaj tiam dividu 81 per 17, ricevante reston 13. Tial 34 = 13 en la grupo (Z17)×. (eo)
- En álgebra abstracta, se conoce como logaritmo discreto de y en base g, donde g e y son elementos de un grupo cíclico finito G, a la solución x de la ecuación gx = y. Esto, se puede denotar matemáticamente como: (es)
- In mathematics, for given real numbers a and b, the logarithm logb a is a number x such that bx = a. Analogously, in any group G, powers bk can be defined for all integers k, and the discrete logarithm logb a is an integer k such that bk = a. In number theory, the more commonly used term is index: we can write x = indr a (mod m) (read "the index of a to the base r modulo m") for rx ≡ a (mod m) if r is a primitive root of m and gcd(a,m) = 1. (en)
- Logarytm dyskretny elementu przy podstawie w danej grupie skończonej – liczba całkowita dla której zachodzi równość (w notacji multiplikatywnej): Logarytm dyskretny nie zawsze istnieje, a jeśli istnieje, może nie być jednoznaczny. Np. w ciele skończonym 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. gdzie c jest pewną stałą. Jedną z metod obliczania logarytmu dyskretnego w GF(p) jest redukcja Pohliga-Hellmana. (pl)
- In de wiskunde is de discrete logaritme voor een groep met vermenigvuldiging de inverse functie van machtsverheffen. Het is het analogon van de gewone logaritme voor de reële getallen. Onder de term 'discreet' moet hier 'geheeltallig' verstaan worden. De discrete logaritme is vergelijkbaar met een array-index. Bij een gegeven index is het relatief eenvoudig het array-element te vinden. Omgekeerd is het in het algemeen lastig voor een bepaalde waarde van een element de bijbehorende index te bepalen, anders dan door het array te doorzoeken. (nl)
- Дискретное логарифмирование (DLOG) — задача обращения функции в некоторой конечной мультипликативной группе . Наиболее часто задачу дискретного логарифмирования рассматривают в мультипликативной группе кольца вычетов или конечного поля, а также в группе точек эллиптической кривой над конечным полем. Эффективные алгоритмы для решения задачи дискретного логарифмирования в общем случае неизвестны. (ru)
|
