En théorie algorithmique des nombres, le problème de la résiduosité quadratique est celui de distinguer, à l'aide de calculs, les résidus quadratiques modulo un nombre composé N fixé. Ce problème est considéré comme étant calculatoirement difficile dans le cas général et sans information supplémentaire. Par conséquent, il s'agit d'un problème important en cryptographie où il est utilisé comme hypothèse calculatoire comme indiqué dans la section .
En théorie algorithmique des nombres, le problème de la résiduosité quadratique est celui de distinguer, à l'aide de calculs, les résidus quadratiques modulo un nombre composé N fixé. Ce problème est considéré comme étant calculatoirement difficile dans le cas général et sans information supplémentaire. Par conséquent, il s'agit d'un problème important en cryptographie où il est utilisé comme hypothèse calculatoire comme indiqué dans la section . (fr) The quadratic residuosity problem (QRP) in computational number theory is to decide, given integers and , whether is a quadratic residue modulo or not.Here for two unknown primes and , and is among the numbers which are not obviously quadratic non-residues (see below). The problem was first described by Gauss in his Disquisitiones Arithmeticae in 1801. This problem is believed to be computationally difficult.Several cryptographic methods rely on its hardness, see . An efficient algorithm for the quadratic residuosity problem immediately implies efficient algorithms for other number theoretic problems, such as deciding whether a composite of unknown factorization is the product of 2 or 3 primes. (en)
En théorie algorithmique des nombres, le problème de la résiduosité quadratique est celui de distinguer, à l'aide de calculs, les résidus quadratiques modulo un nombre composé N fixé. Ce problème est considéré comme étant calculatoirement difficile dans le cas général et sans information supplémentaire. Par conséquent, il s'agit d'un problème important en cryptographie où il est utilisé comme hypothèse calculatoire comme indiqué dans la section . (fr) The quadratic residuosity problem (QRP) in computational number theory is to decide, given integers and , whether is a quadratic residue modulo or not.Here for two unknown primes and , and is among the numbers which are not obviously quadratic non-residues (see below). The problem was first described by Gauss in his Disquisitiones Arithmeticae in 1801. This problem is believed to be computationally difficult.Several cryptographic methods rely on its hardness, see . (en)
