Chapter 6. Discrete Logarithms (2023)

Chapter6.Discrete Logarithms

Cyclic Groups and Generators

Some groups have an interesting property: all the elements in the group can be obtained by repeatedly applying the group operation to a particular group element. If a group has such a property, it is called a cyclic group and the particular group element is called a generator. A trivial example is the group Zn, the additive group of integers modulo n. In Zn, 1 is always a generator:

1 ≡ 1 mod n

1+1 ≡ 2 mod n

1+1+1 ≡ 3 mod n


1+1+1+...+1 ≡ n ≡ 0 mod n

If a group is cyclic, then there may exist multiple generators. For example, we know Z5 is a cyclic group. The element 1 is a generator for sure. And if we take a look at 2, we can find:

2 ≡ 2 mod 5

2+2 ≡ 4 mod 5

2+2+2 ≡ 6 ≡ 1 mod 5

2+2+2+2 ≡ 8 ≡ 3 mod 5

2+2+2+2+2 ≡ 10 ≡ 0 mod 5

So all the group elements {0,1,2,3,4} in Z5 can also be generated by 2. That is to say, 2 is also a generator for the group Z5.

Not every element in a group is a generator. For example, the identity element in a group will never be a generator. No matter how many times you apply the group operator to the identity element, the only element you can yield is the identity element itself. For example, in Zn, 0 is the identity element and 0+0+...+0 ≡ 0 mod n in all cases.

Not every group is cyclic. For example, Zn*, the multiplicative group modulo n, is cyclic if and only if n is 1 or 2 or 4 or pk or 2*pk for an odd prime number p and k ≥ 1. So Z5* must be a cyclic group because 5 is a prime number. Actually all the elements in Z5*, {1,2,3,4} can be generated by 2:

21 ≡ 2 mod 5

22 ≡ 4 mod 5

23 ≡ 8 ≡ 3 mod 5

24 ≡ 16 ≡ 1 mod 5

And Z12* is not a cyclic group. The elements in Z12* are: {1,5,7,11}. Obviously the identity element 1 cannot be a generator. Let's check the other three elements:

51 ≡ 5 mod 1271 ≡ 7 mod 12111 ≡ 11 mod 12
52 ≡25 ≡ 1 mod 1272 ≡ 49 ≡ 1 mod 12112 ≡ 121 ≡ 1 mod 12

None of the elements can generate the whole group. Therefore, none of them is a generator. So Z12* is indeed not cyclic.

If Zn* is cyclic and g is a generator of Zn*, then g is also called a primitive root modulo n.


How hard is the discrete logarithm problem? ›

So while the DLP is generally considered a “hard problem", its difficulty really depends not on the order of the group (or its structure), but on how the group is explicitly rep- resented. Every group of prime order p is isomorphic to Z/pZ; computing the discrete logarithm amounts to computing this isomorphism.

How do you solve a discrete logarithm? ›

Finding a discrete logarithm can be very easy. For example, say G = Z/mZ and g = 1. More specifically, say m = 100 and t = 17. Then logg t = 17 (or more precisely 17 mod 100).

What is discrete logarithm explained simply? ›

A discrete logarithm is just the inverse operation. For example, take the equation 3k≡12 (mod 23) for k. As shown above k=4 is a solution, but it is not the only solution. Since 322≡1 (mod 23), it also follows that if n is an integer, then 34+22n≡12×1n≡12 (mod 23).

What is the discrete log problem in Diffie-Hellman algorithm? ›

The discrete logarithm of x to the base g is the smallest non-negative integer a such that x = ga. We write logg x = a. The discrete logarithm problem in a cyclic group G is to find the discrete logarithm of x to the base g, when x has been chosen uniformly at random from the group.

Is discrete math boring? ›

Discrete math is fun.

Many students, especially bright and motivated students, find algebra, geometry, and even calculus dull and uninspiring. Rarely is this the case with most discrete math topics.

Why is logarithm so hard? ›

Logarithms is one material that is difficult for students [1]. Another study on the difficulties in learning logarithms said that students are more focused on the procedural approaches and depended too much on rules rather than the concept of logarithm itself[2].

How do you solve logarithms step by step? ›

Solving Logarithmic Equations
  1. Step 1: Use the rules of exponents to isolate a logarithmic expression (with the same base) on both sides of the equation.
  2. Step 2: Set the arguments equal to each other.
  3. Step 3: Solve the resulting equation.
  4. Step 4: Check your answers. ...
  5. Solve.

What is a discrete formula? ›

The discrete probability distribution variance gives the dispersion of the distribution about the mean. It can be defined as the average of the squared differences of the distribution from the mean, μ μ . The formula is given below: Var[X] = ∑(x - μ μ )2 P(X = x)

Is discrete math hard? ›

There are several reasons why discrete math can be difficult, including its abstract nature, the use of unfamiliar mathematical notation, and the need to master multiple problem-solving strategies. Overall, it is safe to say that discrete math is indeed a challenging subject.

What are the 3 types of logarithms? ›

The most common types of logarithms are common logarithms, where the base is 10, binary logarithms, where the base is 2, and natural logarithms, where the base is e ≈ 2.71828.

What is the importance of discrete logarithms? ›

Aside from the intrinsic interest that the problem of computing discrete logarithms has, it is of considerable importance in cryptography. An efficient algorithm for discrete logarithms would make several authentication and key-exchange systems insecure.

Is Diffie-Hellman a discrete logarithm? ›

Diffie- Hellman key exchange is based upon the discrete logarithm problem. g a n = determine x. There is no known efficient, non-quantum algorithm to solve the discrete logarithm problem.

What is discrete logarithm what are their properties? ›

Discrete logarithm is only the inverse operation. For instance, it can take the equation 3k = 13 (mod 17) for k. In this k = 4 is a solution. Since 316 ≡ 1(mod 17), it also follows that if n is an integer then 34+16n ≡ 13 x 1n ≡ 13 (mod 17). Therefore, the equation has infinitely some solutions of the form 4 + 16n.

How do I fix weak Diffie-Hellman? ›

Weak Diffie Hellman Logjam Attack Fix
  1. Disable Export Cipher Suites.
  2. Deploy ECDHE and.
  3. Use a Strong Diffie Hellman Group.

Is discrete harder than calculus? ›

Many people will find discrete math more difficult than calculus because of the way they are exposed to both of the areas.

What grade level is discrete mathematics? ›

Because many discrete math problems are simply stated and have few mathematical prerequisites, they can be easily be introduced at the middle school grade level.

What grade is discrete math for? ›

First, Princi- ples and Standards recommends including discrete mathematics in the curriculum for all grades, from prekindergarten through grade 12.

What grade level math is logarithms? ›

Answer and Explanation: In general, logarithms are taught in high school. Normally, beginning high school students (grade 9) are introduced to logarithms.

Is logarithm needed for calculus? ›

When calculus is involved, natural logarithms are usually used. For special purposes, other logarithms are used, mainly logarithms with base 10 or with base 2.

Is log2 faster than log? ›

In contrast, for single precision, both functions log and log2 are the same apart from division by ln2 in the log2 case, hence the same speed.

What are the 5 rules of logarithms? ›

Logarithm Rules and Properties

Product rule. Division rule. Power rule/Exponential Rule. Change of base rule.

What are all the rules of logarithms? ›

The rules apply for any logarithm logbx, except that you have to replace any occurence of e with the new base b. The natural log was defined by equations (1) and (2).
Basic rules for logarithms.
Rule or special caseFormula
Log of powerln(xy)=yln(x)
Log of eln(e)=1
Log of oneln(1)=0
2 more rows

What are the four formulas for logarithms? ›

Basic Logarithm Formulas
  • ⁡ ( x y ) = log b ⁡ ( x ) + log b ⁡
  • log b ⁡ ( x y ) = log b ⁡ ( x ) – log b ⁡
  • log b ⁡ ( x d ) = d log b ⁡
  • c log b ⁡ ( x ) + d log b ⁡ ( y ) = log b ⁡
  • ⁡ ( a + c ) = log b ⁡ a + log b ⁡
  • log b ⁡ ( a − c ) = log b ⁡ a + log b ⁡

What is the general formula for logarithms? ›

Recall the general form of a logarithmic function is: f ( x ) = k + a log b ⁡ where a, b, k, and h are real numbers such that b is a positive number ≠ 1, and x - h > 0. A logarithmic function is transformed into the equation: f ( x ) = 4 + 3 log ⁡ .

Is discrete math actually math? ›

Discrete mathematics is a branch of mathematics concerned with the study of objects that can be represented finitely (or countably).

Is discrete finite or infinite? ›

A random variable is called discrete if it has either a finite or a countable number of possible values. A random variable is called continuous if its possible values contain a whole interval of numbers.

Is discrete math like calculus? ›

"Discrete Math" is not the name of a branch of mathematics, like number theory, algebra, calculus, etc. Rather, it's a description of a set of branches of math that all have in common the feature that they are "discrete" rather than "continuous".

Can you learn discrete math on your own? ›

Can you learn discrete math on your own? Yes. The key to learning anything new is to have a desire to learn. But you also need to have the right resources.

Is discrete math before calculus? ›

Calculus is inherent in every other subject, even discrete structures. Discrete mathematics comes in mind. But calculus is already inherent in discrete mathematics. Combinatorics, set theory or graph theory are usually core elements in a discrete math course.

Is Log10 and log the same? ›

Re: What is the difference between log and log10 transformation in JMP? A common logarithm, Log10(), uses 10 as the base and a natural logarithm, Log(), uses the number e (approximately 2.71828) as the base.

What are the 7 properties of logarithms? ›

Properties of Logarithms
  • Logarithm Base Properties.
  • Product Property.
  • Quotient Property.
  • Power rule.
  • Change of Base rule.
  • Reciprocal rule.
  • Exponent law vs Logarithm law.
  • Natural Logarithm properties.

What are the two laws of logarithms? ›

There are three laws of logarithms that are derived using the basic rules of exponents. The laws are the product rule law, quotient rule law, power rule law.

Which is the best discrete logarithm algorithm? ›

Currently, the best-known algorithm for computing discrete logarithms in Z∗p (for p prime) is the general number field sieve.

What is the purpose of logarithms in math? ›

A logarithm (or log) is the mathematical expression used to answer the question: How many times must one “base” number be multiplied by itself to get some other particular number? For instance, how many times must a base of 10 be multiplied by itself to get 1,000? The answer is 3 (1,000 = 10 × 10 × 10).

What is the purpose of studying logarithm? ›

Logarithms can be used to solve exponential equations and to explore the properties of exponential functions. They will also become extremely valuable in calculus, where they will be used to calculate the slope of certain functions and the area bounded by certain curves.

Is RSA based on discrete log? ›

The discrete logarithm problem bears the same relation to these systems as factoring does to the RSA system: the security of these systems rests on the assumption that discrete logarithms are difficult to compute.

Is the discrete log unique? ›

The discrete logarithm (logarithm) of an element β to the base α in G is an integer x such that α x = β. If x is restricted to the interval 0 ≤ x < #G then the discrete logarithm of β to the base α is unique.

What cryptographic algorithms use discrete logarithms? ›

Public key cryptography using discrete logarithms
  • Diffie-Hellman Key Exchange - with a large cyclical subgroup.
  • MQV Key Agreement - an improvement on Diffie-Hellman.
  • ElGamal Encryption.
  • Digital Signature Algorithm (DSA)
Aug 25, 2013

Are discrete logarithms fundamental? ›

Discrete logarithms are fundamental to a number of public-key algorithms, includ- ing Diffie-Hellman key exchange and the digital signature algorithm (DSA). Discrete logarithms are fundamental to a number of public-key algorithms, includ- ing Diffie-Hellman key exchange and the digital signature algorithm (DSA).

What is the difference between an index and a discrete logarithm? ›

What is the difference between an index and a discrete logarithm? The two terms are synonymous. Which of the following states that if p is prime and a is a positive integer not divisible by p, then a^p−1≡1 (mod p)?

How is discrete logarithm evaluated for a number? ›

Finally, to compute the discrete logarithm d = loga b, assemble all of the individual values d modulo qc via the Chinese remainder theorem to obtain the value of d modulo p − 1. has small prime divisors, then we can evaluate all of the ingredients in the computation rapidly.

How long does it take to break Diffie-Hellman? ›

Many Diffie-Hellman implementations use numbers of a little over 300 digits long (1024 bits). These keys, the paper showed, can be cracked within a year for around 100 million US dollars. (Some people believe it can be done even more cheaply, but only the ballpark figure matters here.)

How do I turn off weak ciphers? ›

You can do this using GPO or Local security policy under Computer configuration -> Administrative Templates -> Network -> SSL Configuration Settings -> SSL Cipher Suite Order. Set this policy to enable. Each cipher suite should be separated with a comma. Remove as needed based on the list below.

How do you use a 2048 bit or stronger Diffie-Hellman group? ›

Use a 2048-bit Diffie-Hellman group.
  1. Run the following command to determine the path to the server.crt file: cat /etc/httpd/conf.d/0ssl.conf | grep SSLCertificateFile.
  2. Generate a 2048-bit Diffie-Hellman group: openssl dhparam -out dhparams.pem 2048.
Mar 6, 2020

Is the discrete logarithm problem NP hard? ›

So while the DLP is generally considered a “hard problem", its difficulty really depends not on the order of the group (or its structure), but on how the group is explicitly rep- resented. Every group of prime order p is isomorphic to Z/pZ; computing the discrete logarithm amounts to computing this isomorphism.

Are discrete functions hard? ›

Many students find that discrete math is harder than calculus. Discrete math is a branch of mathematics that deals with objects that are discrete, meaning they can be counted or listed. This includes things like integers, graphs, and boolean values.

Is discrete structures a hard course? ›

Reasons why discrete math can be a hard class

Discrete math often involves working with concepts that are not directly related to the physical world, such as graphs, sets, and logic. These abstract ideas can be difficult for students to grasp, especially if they are more comfortable with concrete, real-world concepts.

Why is NP-complete that hardest? ›

"NP-complete problems are difficult because there are so many different solutions." On the one hand, there are many problems that have a solution space just as large, but can be solved in polynomial time (for example minimum spanning tree).

Can the discrete log problem be solved? ›

Discrete logarithms are quickly computable in a few special cases. However, no efficient method is known for computing them in general.

Does NP-hard mean unsolvable? ›

No. “NP-hard” applies to problems that receive an input of arbitrary length and produce a yes/no response as a decision for that input. Problems that require no input, such as “does P=NP”, can be solved in O(1) time (constant time).

What should I learn before discrete math? ›

What math do I need to learn before discrete mathematics? Students with a solid understanding of algebra, geometry, and precalculus will do very well in discrete math.

Is discrete math worth? ›

Discrete Mathematics provides an essential foundation for virtually every area of computer science, and its applications are correspondingly vast. At the most fundamental level, all of a computer's data is represented as bits (zeros and ones).

Do I need to know calculus before discrete math? ›

Calculus isn't really needed to understand discrete math, but if calculus is a prerequisite for the class, there are a number of good examples and homework problems that the professor might use that would indeed require calculus.

What is the highest math class? ›

Therefore, according to the Common Core standards, a typical order of core High School Math curriculum from freshman to senior year is:
  • Algebra 1.
  • Geometry.
  • Algebra 2/Trigonometry.
  • Pre-Calculus.
  • Calculus.
Mar 1, 2021

What level of math is 11th grade? ›

Typically, students in grade 11 take Algebra II (if they followed the traditional course sequence: Algebra I in 9th grade, and Geometry in 10th grade). However, some students may be able to take Algebra I while still in 8th grade. In those cases, both 11th and 12th grade become open for advanced math options.

Which is the easiest data structure to learn? ›

1. Arrays. The first in our list of basic data structures is one of the simplest data structures. An array is a fixed-size structure that stores multiple items of the same kind of data sequentially.

Is discrete or linear algebra harder? ›

I think discrete math is harder than calculus or linear algebra, but that may be a personal thing. Discrete math covers a diverse number of topics which have their own particular methods, whereas calculus relies on a handful of tricks which you can apply over and over again.

How hard is statistics in college? ›

Statistics has gotten a reputation for being a very hard class, especially when taken in college, because it combines math concepts in order to form an analysis of a data set that can be used to understand an association in the data (whoo that was a mouthful).


Top Articles
Latest Posts
Article information

Author: Melvina Ondricka

Last Updated: 11/15/2023

Views: 5281

Rating: 4.8 / 5 (68 voted)

Reviews: 91% of readers found this page helpful

Author information

Name: Melvina Ondricka

Birthday: 2000-12-23

Address: Suite 382 139 Shaniqua Locks, Paulaborough, UT 90498

Phone: +636383657021

Job: Dynamic Government Specialist

Hobby: Kite flying, Watching movies, Knitting, Model building, Reading, Wood carving, Paintball

Introduction: My name is Melvina Ondricka, I am a helpful, fancy, friendly, innocent, outstanding, courageous, thoughtful person who loves writing and wants to share my knowledge and understanding with you.