Solving Prime Algorithm Unit Circle on Zp - Complexity?

[khotsofalang]

Let x1 + x2 =1 be a unit circle upon a finite field Zp where p is prime. Is there any algorithm which can give all the possible solutions (x1,x2) an element of Zp*Zp as well as the total number of such solutions? If exists, what is the complexity of it?

 

[CRGreathouse]

I take the problem as: find the solutions (a, b) of
a^2+b^2\equiv1\pmod p, p prime.

Looping through all possible a and b would take time O(p^2 M(log p)) and very little space.

Enumerating the squares mod p and combining would take time something like O(p) and space O(p log p).

I can't think of any clever ways to do this.

 

[csprof2000]

If p > 2, then clearly you must have that p is odd and you can therefore deduce that a^2 + b^2 is even (it is 1 mod p, after all) so you don't have to consider (a, b) where a and b have opposite parity. This is 50% of the candidate solutions.

Also, clearly the order of a and b don't matter... you're looking for two-sets of numbers (possibly 1-sets, but you can just use two-bags instead and no problem). This is 50% of the original number of ordered pairs and 25% of the remaining candidates.

All of this doesn't lower the complexity any, but it's better than a "dumb" search of all p^2 solutions. Using these methods, you can check only 1/4 of all solutions. Still pretty brute-force, but not bad. I don't think this is what CRGreathouse was recommending, just to clarify, but I thought I'd go ahead and make this explicit.

I'll think about this some more. It seems like some trick should be forthcoming...

 

[CRGreathouse]

I was suggesting calculating all the squares mod p and putting them in a structure that would let you query "3" and get {} or query "5" and get {45, 56} -- in this case working mod 101.

Then you loop over the squares n, querying squares[p+1-n]. If it's nonempty, then the Cartesian product of squares[n] and squares[p+1-n] are solutions.

Enumerating squares takes p steps (no multiplication or division is really needed, but if the numbers are small it might actually be faster to just square and reduce).

Looping over the squares takes about p/2 loops, each of which takes 1-2 lookups and appending 0, 2, or 4 elements to a list.

 

[Hurkyl]

The 'number of solutions' is actually pretty easy: the trick is that any line intersects the circle in at most two points. (Exactly two points, if you count irrational and infinite points, as well as multiplicity) So, if you choose a point P on the circle, you can name any other point Q by the line passing through P and Q...

(for p > 2, you can show that through P, the circle has two asymptotes and one tangent line, thus there are p-1 points)

 

[CRGreathouse]

The 'number of solutions' is actually pretty easy: the trick is that any line intersects the circle in at most two points. (Exactly two points, if you count irrational and infinite points, as well as multiplicity) So, if you choose a point P on the circle, you can name any other point Q by the line passing through P and Q...

(for p > 2, you can show that through P, the circle has two asymptotes and one tangent line, thus there are p-1 points)

It looks like primes of the form 4n + 3 have p + 1 solutions, where primes of the form 4n + 1 have p - 1 solutions.

 

[Hurkyl]

It looks like primes of the form 4n + 3 have p + 1 solutions, where primes of the form 4n + 1 have p - 1 solutions.

Oh right, I knew that. I just got that wrong a couple weeks ago. The points at infinity have projective coordinates (1 : \sqrt{-1} : 0), and so to be rational, -1 must be a square mod p.

 

[dodo]

I was wondering if it would help to figure out which values 1 - b^2 are congruent to quadratic residues mod p, for each b = 0, 1, ... p-1.

If p is odd, and 1 - b^2 is reduced to a value r between 0 and p-1, then a criterion by Euler says that r is a quadratic residue iff r^{(p-1)/2} \equiv 1 (mod p). Then again, you don't get the actual solution.

 

[CRGreathouse]

I was wondering if it would help to figure out which values 1 - b^2 are congruent to quadratic residues mod p, for each b = 0, 1, ... p-1.

If p is odd, and 1 - b^2 is reduced to a value r between 0 and p-1, then a criterion by Euler says that r is a quadratic residue iff r^{(p-1)/2} \equiv 1 (mod p). Then again, you don't get the actual solution.

But if you want all the residues, why go through that much trouble? Just square all the values. (If they're large enough that squaring is a trouble, just add 2n+1 to the last value and subtract as needed to reduce.)

 

[dodo]

Hmm, right; actually calculating the powers in Euler's criterion is pretty expensive. So this reduces to list the squares, as you mentioned at the beginning.

One other thing. Leaving aside obvious solutions where one of a,b is zero, there are (p-1)/2 quadratic residues; so it seems that only 2 values of a for each one of b are possible (namely, a and -a), in order to total p-1 or p+1 solutions. So really you only need to run the squares up to half the list, I think.

 

[CRGreathouse]

so it seems that only 2 values of a for each one of b are possible (namely, a and -a), in order to total p-1 or p+1 solutions. So really you only need to run the squares up to half the list, I think.

Good point.