Resíduo quadrático e fatoração inteira

Costumo ler que decidir se um número é um resíduo quadrático módulo é um problema interessante (e difícil) da teoria dos números (especialmente se não for primo).$r$$n$$n$

Estou analisando o seguinte caso especial desse problema: Vamos $p$ e $q$ ser dois números primos diferentes e $n:=pq$. Dado$r$ entre $1$ e $n$. Decida se existe um$x\in\mathbb{Z}/n\mathbb{Z}$tal que .$x^2\equiv r\pmod{n}$

Minha pergunta é: A versão funcional desse problema, ou seja, "Encontre um como o anterior", gera um algoritmo aleatório para fatoração inteira. Portanto, é muito interessante por razões práticas, como "quebrar a RSA". Existe algum resultado para a versão de decisão desse problema? Caso contrário, quais são os problemas típicos que pensamos que decidir a residuosidade quadrática é um problema difícil?$x$

Além disso, o caso especial que eu estou vendo é realmente um caso especial? Ou posso resolver o caso geral com um arbitrário com um oráculo para o problema de decisão acima?$n$

Tibor Jager e Jörg Schwenk mostram em A dureza genérica dos problemas de associação a subconjuntos sob a suposição de fatoração que o fatoramento reduz a distinção entre resíduos quadráticos e números com o símbolo 1 de Jacobi, para algoritmos de anel genéricos . Estes são algoritmos cuja única "API" para números inteiros são operações em anel (adição, multiplicação, subtração, divisão), comparações de igualdade e geração de um elemento aleatório. Eles também mostram que o símbolo de Jacobi, que pode ser calculado com eficiência em tempo polinomial, não possui algoritmo genérico de anel eficiente. Portanto, o resultado deles não responde à sua pergunta, além de implicar que a resposta não é conhecida.