20210705, 19:24  #1 
Mar 2016
3^{2}·41 Posts 
an²+bn+c = 0 mod p
Let f(n)=an²+bn+c = 0 mod p
with n element of N and p prime. n=? Is there a better way than calculating f(n) for n=0 ...p1 Thanks if you spend me some lines. 
20210705, 20:31  #2 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
9,629 Posts 
Solve it like you were taught in elementary school, only remember that operations are mod p.
Instead of "there is no square root for negative numbers > there is no solution" you will use "D is not a quadratic character > there is no solution". 
20210706, 06:49  #3 
Dec 2012
The Netherlands
3·587 Posts 
Yes, in this subforum already!
https://www.mersenneforum.org/showthread.php?t=22058 
20210706, 11:45  #4  
Jan 2020
2^{2}×3^{2} Posts 
Quote:
About efficiently computing square roots modulo a large prime (hundreds of digits or more), there are two good algorithms by TonelliShanks and by Cipolla. Last fiddled with by 0scar on 20210706 at 11:46 

20210707, 02:56  #5  
Mar 2016
3^{2}×41 Posts 
Quote:
b²4ac is a quadratic residue, but not always a square. 

20210707, 09:20  #6  
Dec 2012
The Netherlands
3×587 Posts 
Quote:
"Prime Numbers , a computational perspective" 

20210708, 21:18  #7 
Mar 2016
3^{2}·41 Posts 
Let an²+bn+c = 0 mod p
If I want to calculate the discriminant, can I first calculate a*=a mod p, b*=b mod p and c*=c mod p and then discr=(b*)²4a*c* ? 
20210708, 21:57  #8  
Dec 2012
The Netherlands
3×587 Posts 
Quote:
That is what we mean by Propostion 22 here 

20210709, 20:32  #9 
Mar 2016
3^{2}·41 Posts 
@Nick, thanks a lot for your work and help.
an useful implementation in c and gmp of tonellishanks algorithm is: http://www.codecodex.com/wiki/ShanksTonelli_algorithm Let : 2ax+b≡y(mod4an) I did not understand, how you solve it. gcd (2a,4an)=2a>1 so the inverse does not exist. Dividing by 4a seems to be possible x/2=(yb)*(4a)⁻¹ mod (n) with a=/=0 multiplying with 2 is x =(yb)*(2a)⁻¹ mod n Is that ok ? Last fiddled with by bhelmes on 20210709 at 20:36 
20210710, 08:19  #10 
Dec 2012
The Netherlands
3341_{8} Posts 
We have \(2ax+by\equiv 0\pmod{4an}\) and \(\gcd(2a,4an)=2a\neq 1\).
If 2a does not divide by then there is no solution. If instead by=2at for some integer t then \(x\equiv t\pmod{2n}\). 