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:
“The mastery of one’s phonemes may be compared to the violinist’s mastery of fingering. The violin string lends itself to a continuous gradation of tones, but the musician learns the discrete intervals at which to stop the string in order to play the conventional notes. We sound our phonemes like poor violinists, approximating each time to a fancied norm, and we receive our neighbor’s renderings indulgently, mentally rectifying the more glaring inaccuracies.”
—W.V. Quine (b. 1908)