Prime number algorithm

  • #1

Main Question or Discussion Point

i am sorry guys, the last time i posted this problem it was completely different but this time if we
Let x12+x22=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?
 

Answers and Replies

  • #2
CRGreathouse
Science Advisor
Homework Helper
2,820
0
You could check all possibilities. That takes something like O(p^2 log^2 p).

Now you just need a *good* way to solve it.
 
  • #3
all right, but what i actually need is that good way of solving it
 
  • #4
i need a solution to such an equation for stregthening my extended essay,anibody with a gud way of solving it?
 
  • #5
695
2
If I understood correctly, you are looking for two quadratic residues that add up to 1. It may be easier for primes congruent to 1 modulo 4, because quadratic residues for those primes are 'symmetric': r is a quadratic residue iif p-r is. In this case you just look for contiguous quadratic residues on the lower half, from 2 to (p-1)/2: if r and r+1 are quadratic residues, then p-r also is, and (p-r)+(r+1) add to 1. My 2 cents.
 

Related Threads for: Prime number algorithm

  • Last Post
Replies
3
Views
4K
  • Last Post
Replies
1
Views
3K
Replies
1
Views
3K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
2
Replies
44
Views
11K
  • Last Post
2
Replies
28
Views
7K
  • Last Post
Replies
24
Views
6K
Top