Let $n = p^a$$q^b$ where p and q are distinct primes and a and b are positive integers. How to construct a zero knowledge proof that n is of such form?
This is actually a homework problem with a hint that if a $n = p^a$$q^b$ then exactly half of the elements in $Z_n$ with jacobi symbol +1 are quadratic residues mod n and we assume that initially verifier knows a quadratic non-residue x with jacobi symbol +1.
I stuck there because it seems extremely difficult to convince Verifier that n is of given form. It is not simply like after Verfier sends a challenge number to Prover and Prover shows that he knows the fact that if the challenge number is QNR or QR. For me to convince Verfier all jacobi +1 elements have to be generated in $Z_n$ and Prover has show that exactly half of them are QR. (Assume that Verifier can generate with x itself thus it does not violate Zero knowledge. But I am not sure if it is easy(polynomial time consuming) to generate all Jacobi +1 elements yet. Well it is true that if we let $z = r^2$ for a randomly picked r from $Z_n$ then $y = r^2x$ is also a QNR with jacobi symbol +1... So finding another QNR with jacobi symbol +1 is easy for verifier... ) But To show "exactly half" then Prover will need to show which one is QR and which is are QNR then it will violate Zero knowledge property since V is not suppose know that. But any other way to show "exactly half"?
Any hint or help is greatly appreciated. Thanks!