Discrete Logarithms
Suppose we know that, for some r, and we wish to compute r, which is the discrete logarithm: . Consider the Abelian group where each factor corresponds to modular multiplication of nonzero values, assuming p is prime. Now, consider the function
This gives us an Abelian hidden subgroup problem, as f corresponds to a group homomorphism. The kernel corresponds to modular multiples of (r,1). So, if we can find the kernel, we can find r
Read more about this topic: Shor's Algorithm
Famous quotes containing the word discrete:
“One can describe a landscape in many different words and sentences, but one would not normally cut up a picture of a landscape and rearrange it in different patterns in order to describe it in different ways. Because a photograph is not composed of discrete units strung out in a linear row of meaningful pieces, we do not understand it by looking at one element after another in a set sequence. The photograph is understood in one act of seeing; it is perceived in a gestalt.”
—Joshua Meyrowitz, U.S. educator, media critic. “The Blurring of Public and Private Behaviors,” No Sense of Place: The Impact of Electronic Media on Social Behavior, Oxford University Press (1985)