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:
“Involuntary mental hospitalization is like slavery. Refining the standards for commitment is like prettifying the slave plantations. The problem is not how to improve commitment, but how to abolish it.”
—Thomas Szasz (b. 1920)
“A sentence is made up of words, a statement is made in words.... Statements are made, words or sentences are used.”
—J.L. (John Langshaw)