离散对数









未解決的计算机科学問題：是否存在离散对数问题的多项式时间经典算法？		 Question mark2.svg

在整數中，離散對數（英语：Discrete logarithm）是一種基於同餘運算和原根的一種對數運算。而在實數中對數的定義 logba 是指對於給定的 a 和 b，有一個數 x，使得bx = a。相同地在任何群 G中可為所有整數 k定義一個冪數為 bk，而離散對數 logba是指使得 bk = a的整數 k。
離散對數在一些特殊情況下可以快速計算。然而，通常沒有具非常效率的方法來計算它們。公鑰密碼學中幾個重要算法的基礎，是假設尋找離散對數的問題解，在仔細選擇過的群中，並不存在有效率的求解算法。



定義


當模m{displaystyle m}m有原根時，設l{displaystyle l}l為模m{displaystyle m}m的一個原根，則當x≡lk(modm){displaystyle xequiv l^{k}{pmod {m}}}xequiv l^{k}{pmod {m}}時：


Indlx≡k(modϕ(m)){displaystyle Ind_{l}xequiv k{pmod {phi (m)}}}Ind_{{l}}xequiv k{pmod {phi (m)}}，此處的Indlx{displaystyle Ind_{l}x}Ind_{{l}}x為x{displaystyle x}x以整數l{displaystyle l}l為底，模ϕ(m){displaystyle phi (m)}phi (m)時的離散對數值



性質


離散對數和一般的對數有著相類似的性質：



  • Indlxy≡Indlx+Indly(modϕ(m)){displaystyle Ind_{l}xyequiv Ind_{l}x+Ind_{l}y{pmod {phi (m)}}}Ind_{{l}}xyequiv Ind_{{l}}x+Ind_{{l}}y{pmod {phi (m)}}

  • Indlxy≡yIndlx(modϕ(m)){displaystyle Ind_{l}x^{y}equiv yInd_{l}x{pmod {phi (m)}}}Ind_{{l}}x^{y}equiv yInd_{{l}}x{pmod {phi (m)}}



參見



  • 原根

  • 對數








Comments

Post a Comment

Popular posts from this blog

Information security

Image
This article is part of a series on Information security Related security categories Internet security Cyberwarfare Computer security Mobile security Network security Threats Computer crime Vulnerability Eavesdropping Malware Spyware Ransomware Trojans Viruses Worms Rootkits Bootkits Keyloggers Screen scrapers Exploits Backdoors Logic bombs Payloads Denial of service Defenses Computer access control Application security Antivirus software Secure coding Secure by default Secure by design Secure operating systems Authentication Multi-factor authentication Authorization Data-centric security Encryption Firewall Intrusion detection system Mobile secure gateway Runtime application self-protection (RASP) v t e Information security , sometimes shortened to InfoSec , is the practice of preventing unauthorized access, use, disclosure, disruption, modification, inspection, recording or destruction of information. Th...
Read more

Volkswagen Group MQB platform

Image
The Volkswagen Group MQB platform is the company's strategy for shared modular design construction of its transverse, front-engine, front-wheel-drive layout (optional front-engine, four-wheel-drive layout) automobiles. Volkswagen spent roughly $60bn [1] developing this new platform and the cars employing it. The platform underpins a wide range of cars from the supermini class to the mid size SUV class. MQB allows Volkswagen to assemble any of its cars based on this platform across all of its MQB ready factories. This allows the Volkswagen group flexibility to shift production as needed between its different factories. Beginning in 2012, Volkswagen Group marketed the strategy under the code name MQB , which stands for Modularer Querbaukasten , translating from German to "Modular Transversal Toolkit" or "Modular Transverse Matrix". [2] [3] MQB is one strategy within VW's overall MB (Modularer Baukasten or modular matrix) program which also includes th...
Read more

Daniel Guggenheim

Image
Daniel Guggenheim 1925 photo Born ( 1856-07-09 ) July 9, 1856 Philadelphia, Pennsylvania Died September 28, 1930 (1930-09-28) (aged 74) Port Washington, New York Alma mater Peirce College Known for Battle for control of ASARCO Daniel Guggenheim Medal Spouse(s) Florence Shloss Children Meyer Robert Guggenheim Harry Guggenheim Gladys Eleanor Guggenheim Parent(s) Meyer Guggenheim Barbara Guggenheim Daniel Guggenheim, 1910 Daniel Guggenheim (July 9, 1856 – September 28, 1930) was an American mining magnate and philanthropist, and a son of Meyer and Barbara Guggenheim. Contents 1 Biography 2 Personal life 2.1 Aviation 2.2 Alaska 3 See also 4 References 5 Further reading 6 External links Biography Born and raised in Philadelphia, Daniel Guggenheim was sent to Switzerland as a young man to study the Swiss lace and embroidery business, and to serve as a buyer for his father's import firm. The...
Read more