Introduction
The contemporary name for a problem-solving technique, algorithm, is often used nowadays for the rules that a machine, particularly a computer, must follow to achieve a specific objective. It is not necessarily applicable to computer-mediated activities. This article discusses how the lower bounds on the complexity of generic algorithms work. Let's get started.
Algorithm
An algorithm composes well-defined instructions for solving a specific issue in computer programming.
Example:
An algorithm for multiplying two numbers:
- Consider two numerical inputs.
- Using the * operator.
- Multiply two integers together.
- Display result.
Generic Algorithm
A generic algorithm accepts a collection of inputs and outputs the desired result since it is not dependent on any attribute of the group's representation.
- A generic algorithm may be used with any encoding.
- It is also a general-purpose algorithm.
- It makes no use of any representation characteristic of the group elements. Each element of the group has its representation.
Shanks' algorithm, the Pollard-Rho algorithm, and the Pohlig-Hellman algorithm are a few examples of generic algorithms for the discrete logarithm issue.
Discrete Logarithm Problem
Logarithms that are groups of multiplicative cyclic groups are referred to as discrete logarithms.
If "A" is a multiplicative cyclic group and "a" is a generator of "A," then every element h in "A" may be expressed as an ax for any x, according to the definition of cyclic groups. The element of x is the discrete logarithm to the base "a" of h in group A. It finds the discrete logarithm to the base "a" of h in group A given a group A, a generator "a" of the group, and an element h of A.
The difficulty of obtaining discrete logarithms varies according to the groupings. For example, Zp*, where p is a prime number, is a frequent group choice for discrete logarithm-based cryptosystems.
By definition, the discrete logarithm issue occurs in a cyclic subgroup of order n, which is isomorphic and is well known and very straightforward to establish. It means that we may be able to solve the discrete logarithm issue in any subgroup of order n of any group A by "reducing" the problem to the easily solvable version in (Zn, +).
568+ registered 
