mersenneforum.org > Math an²+bn+c = 0 mod p
 Register FAQ Search Today's Posts Mark Forums Read

 2021-07-05, 19:24 #1 bhelmes     Mar 2016 1011100012 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-05, 20:31 #2 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 100101100110012 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-06, 06:49   #3
Nick

Dec 2012
The Netherlands

175910 Posts

Quote:
 Originally Posted by bhelmes Is there a better way than calculating f(n) for n=0 ...p-1

2021-07-06, 11:45   #4
0scar

Jan 2020

2416 Posts

Quote:
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.

Last fiddled with by 0scar on 2021-07-06 at 11:46

2021-07-07, 02:56   #5
bhelmes

Mar 2016

5618 Posts

Quote:
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.

2021-07-07, 09:20   #6
Nick

Dec 2012
The Netherlands

110110111112 Posts

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"

 2021-07-08, 21:18 #7 bhelmes     Mar 2016 32·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* ?
2021-07-08, 21:57   #8
Nick

Dec 2012
The Netherlands

110110111112 Posts

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

 2021-07-09, 20:32 #9 bhelmes     Mar 2016 1011100012 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-10, 08:19 #10 Nick     Dec 2012 The Netherlands 175910 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}$$.

All times are UTC. The time now is 07:02.

Tue Dec 7 07:02:14 UTC 2021 up 137 days, 1:31, 0 users, load averages: 1.75, 1.68, 1.45

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.