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:
“We have good reason to believe that memories of early childhood do not persist in consciousness because of the absence or fragmentary character of language covering this period. Words serve as fixatives for mental images. . . . Even at the end of the second year of life when word tags exist for a number of objects in the child’s life, these words are discrete and do not yet bind together the parts of an experience or organize them in a way that can produce a coherent memory.”
—Selma H. Fraiberg (20th century)