The most powerful algorithm for computing this quantity can do so in sub-exponential time but is complicated by the fact that the selection of the factor base represents a tradeoff; that is the index calculus algorithm.
One way of computing this quantity in exponential time is to employ a Monte Carlo algorithm developed by John Pollard, known as his namesake "kangaroo" algorithm. An algorithm for computing this quantity that works relatively well for orders that are smooth integers is partially named after Silver and Pohlig. The most powerful algorithm for computing this quantity can do so in sub-exponential time but is complicated by the fact that the selection of the factor base represents a tradeoff; that is the index calculus algorithm. The difficulty of computing this quantity is at the heart of a signature scheme developed by El Gamal. (*) The ability to compute this quantity efficiently would solve the problem of computing g to the power x times y given a group generator g, integers x and y, and the values of g to the x and g to the y, known as the Diffie-Hellman problem. In general, computing this quantity means that given a group element g and an element a of the cyclic subgroup generated by g, one must find an integer x such that g to the x equals a. For 10 points, identify this so-far-intractable problem, the finite analogue to the continuous function that is the inverse of exponentiation.
One way of computing this quantity in exponential time is to employ a Monte Carlo algorithm developed by John Pollard, known as his namesake "kangaroo" algorithm.
discrete logarithm