Problem Statement
Given an integer n = pq where p and q are unknown, an integer d such that d divides p-1, and an integer x < n, it is infeasible to determine whether x is a dth power (equivalently dth residue) modulo n.
Notice that if p and q are known it is easy to determine whether x is a dth residue modulo n because x will be a dth residue modulo p if and only if
When d=2, this is called the quadratic residuosity problem.
Read more about this topic: Higher Residuosity Problem
Famous quotes containing the words problem and/or statement:
“It is commonplace that a problem stated is well on its way to solution, for statement of the nature of a problem signifies that the underlying quality is being transformed into determinate distinctions of terms and relations or has become an object of articulate thought.”
—John Dewey (1859–1952)
“It is commonplace that a problem stated is well on its way to solution, for statement of the nature of a problem signifies that the underlying quality is being transformed into determinate distinctions of terms and relations or has become an object of articulate thought.”
—John Dewey (1859–1952)