Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prime algorhithms

  1. Feb 24, 2009 #1
    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?
     
    Last edited: Feb 24, 2009
  2. jcsd
  3. Feb 24, 2009 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    I take the problem as: find the solutions (a, b) of
    [tex]a^2+b^2\equiv1\pmod p[/tex], 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.
     
  4. Feb 24, 2009 #3
    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...
     
  5. Feb 24, 2009 #4

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  6. Feb 24, 2009 #5

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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)
     
  7. Feb 24, 2009 #6

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    It looks like primes of the form 4n + 3 have p + 1 solutions, where primes of the form 4n + 1 have p - 1 solutions.
     
  8. Feb 24, 2009 #7

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Oh right, I knew that. I just got that wrong a couple weeks ago. :redface: The points at infinity have projective coordinates [itex](1 : \sqrt{-1} : 0)[/itex], and so to be rational, -1 must be a square mod p.
     
  9. Feb 25, 2009 #8
    I was wondering if it would help to figure out which values [tex]1 - b^2[/tex] are congruent to quadratic residues mod p, for each b = 0, 1, ... p-1.

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

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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.)
     
  11. Feb 25, 2009 #10
    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.
     
  12. Feb 25, 2009 #11

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Good point.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Prime algorhithms
  1. Prime question (Replies: 3)

  2. Ramsey Primes (Replies: 8)

  3. Prime Numbers (Replies: 1)

  4. Prime ideals (Replies: 9)

  5. Prime Ideals (Replies: 1)

Loading...