mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2021-07-05, 19:24   #1
bhelmes
 
bhelmes's Avatar
 
Mar 2016

419 Posts
Default 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.
bhelmes is offline   Reply With Quote
Old 2021-07-05, 20:31   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

274216 Posts
Default

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".
Batalov is offline   Reply With Quote
Old 2021-07-06, 06:49   #3
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

1,801 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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
Nick is offline   Reply With Quote
Old 2021-07-06, 11:45   #4
0scar
 
Jan 2020

2416 Posts
Default

Quote:
Originally Posted by Nick View Post
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
0scar is offline   Reply With Quote
Old 2021-07-07, 02:56   #5
bhelmes
 
bhelmes's Avatar
 
Mar 2016

41910 Posts
Default

Quote:
Originally Posted by Nick View Post
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.
bhelmes is offline   Reply With Quote
Old 2021-07-07, 09:20   #6
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

34118 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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"
Nick is offline   Reply With Quote
Old 2021-07-08, 21:18   #7
bhelmes
 
bhelmes's Avatar
 
Mar 2016

419 Posts
Default

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* ?
bhelmes is offline   Reply With Quote
Old 2021-07-08, 21:57   #8
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

1,801 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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
Nick is offline   Reply With Quote
Old 2021-07-09, 20:32   #9
bhelmes
 
bhelmes's Avatar
 
Mar 2016

6438 Posts
Default

@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+by(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
bhelmes is offline   Reply With Quote
Old 2021-07-10, 08:19   #10
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

1,801 Posts
Default

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}\).
Nick is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 19:55.


Sat Jan 28 19:55:27 UTC 2023 up 163 days, 17:24, 0 users, load averages: 0.84, 1.07, 1.19

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔