yspm's blog

Quadratic surplus and integer square root
By yspm, history, 3 years ago, In English

I've heard that if a number $$$n$$$ has quadratic surplus under a odd prime $$$p$$$ so it has around 50% accuracy to be a perfect square number.

Is it correct? How to prove?

If so,perhaps there exists a method to judge whether a big number $$$n$$$ is a perfect square number or not is that random amount of odd primes which are not divisors of $$$n$$$ and find Quadratic surplus of $$$n$$$ mod $$$p$$$. Failure appears means $$$n$$$ isn't a perfect square number.

  • Vote: I like it
  • +24
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +63 Vote: I do not like it

Just emotionally comprehend it

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +16 Vote: I do not like it

I think the meaning was lost in translation. I think you mean $$$n$$$ is a quadratic residue mod $$$p$$$. This can be verified using quadratic reciprocity. If something is a square mod $$$p$$$ then obviously it will be quadratic residue mod $$$p$$$. If something is not a square it has has a 50 % chance of being a square $$$\mod p$$$ because 50 % of residues are squares $$$\mod p$$$. It will be at most 50% but it is smaller for small $$$n$$$. Remember this tells us nothing if prime checks for one number is independent of another prime check, and how many tests could a non square number pass.

If anyone could find how many primes could a square free number pass or if they are mostly independent I am interested in your solution.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

Everule said '50% of residues are squares $$$\bmod p$$$', you can find detailed proof on this Chinese website. If you choose $$$p$$$ randomly, $$$n\bmod p$$$ will have a 50% chance of being a quadratic residue $$$\bmod p$$$

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your first sentence is true. What follows from it is that for a fixed p if you choose n randomly then n has ~50% chance of being a quadratic residue, what is a significantly different from your second sentence, where you fix n and choose random p. I suspect your second sentence is true as well though (and in fact this is the statement required to checking if a bignum is a square) and definitely can be assumed as "alright enough" on a cp competition, but I guess complexity of its proof could be anywhere between complex olympic problem to open problem

    → Reply
»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Nah mate, saying that "if a number has quadratic residue mod p then it has 50% of being a square" is a probabilistic blasphemy

→ Reply