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:
“You are a problem and rune,
you are mystery;
writ on a stone.”
—Hilda Doolittle (1886–1961)
“The honor my country shall never be stained by an apology from me for the statement of truth and the performance of duty; nor can I give any explanation of my official acts except such as is due to integrity and justice and consistent with the principles on which our institutions have been framed.”
—Andrew Jackson (1767–1845)