an²+bn+c = 0 mod p

bhelmes · 2021-07-05, 19:24

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 ...p-1

Thanks if you spend me some lines.

Batalov · 2021-07-05, 20:31

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".

Nick · 2021-07-06, 06:49

Quote:

Originally Posted by bhelmes

Is there a better way than calculating f(n) for n=0 ...p-1

Yes, in this subforum already!
https://www.mersenneforum.org/showthread.php?t=22058

0scar · 2021-07-06, 11:45

Quote:

Originally Posted by Nick

Yes, in this subforum already!
https://www.mersenneforum.org/showthread.php?t=22058

Great explanation from the given subforum.
About efficiently computing square roots modulo a large prime (hundreds of digits or more), there are two good algorithms by Tonelli-Shanks and by Cipolla.

bhelmes · 2021-07-07, 02:56

Quote:

Originally Posted by Nick

Yes, in this subforum already!
https://www.mersenneforum.org/showthread.php?t=22058

I did not understand how to find the square of the discriminant b²-4ac mod 4an.
b²-4ac is a quadratic residue, but not always a square.

Nick · 2021-07-07, 09:20

Quote:

Originally Posted by bhelmes

I did not understand how to find the square of the discriminant b²-4ac mod 4an.

See section 2.3.2 in the 2nd edition of the book by Crandall and Pomerance:
"Prime Numbers , a computational perspective"

bhelmes · 2021-07-08, 21:18

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* ?

Nick · 2021-07-08, 21:57

Quote:

Originally Posted by bhelmes

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* ?

Yes (assuming you mean discr=(b*)²-4a*c* mod p).
That is what we mean by Propostion 22 here

bhelmes · 2021-07-09, 20:32

@Nick, thanks a lot for your work and help.

an useful implementation in c and gmp of tonelli-shanks algorithm is:
http://www.codecodex.com/wiki/Shanks-Tonelli_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=(y-b)*(4a)⁻¹ mod (n) with a=/=0
multiplying with 2 is x =(y-b)*(2a)⁻¹ mod n

Is that ok ?

Nick · 2021-07-10, 08:19

We have \(2ax+b-y\equiv 0\pmod{4an}\) and \(\gcd(2a,4an)=2a\neq 1\).
If 2a does not divide b-y then there is no solution.
If instead b-y=2at for some integer t then \(x\equiv -t\pmod{2n}\).

2021-07-05, 19:24	#1
bhelmes Mar 2016 1AA₁₆ 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 ...p-1 Thanks if you spend me some lines.

2021-07-09, 20:32	#9
bhelmes Mar 2016 2×3×71 Posts	@Nick, thanks a lot for your work and help. an useful implementation in c and gmp of tonelli-shanks algorithm is: http://www.codecodex.com/wiki/Shanks-Tonelli_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=(y-b)(4a)⁻¹ mod (n) with a=/=0 multiplying with 2 is x =(y-b)(2a)⁻¹ mod n Is that ok ? Last fiddled with by bhelmes on 2021-07-09 at 20:36

2021-07-05, 20:31	#2
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2771₁₆ 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".

2021-07-08, 21:18	#7
bhelmes Mar 2016 2·3·71 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)²-4ac ?

2021-07-10, 08:19	#10
Nick Dec 2012 The Netherlands 3446₈ Posts	We have \(2ax+b-y\equiv 0\pmod{4an}\) and \(\gcd(2a,4an)=2a\neq 1\). If 2a does not divide b-y then there is no solution. If instead b-y=2at for some integer t then \(x\equiv -t\pmod{2n}\).