GitHub - rahulsudhu/primes_of_the_form · GitHub
/" data-turbo-transient="true" />
Skip to content
Search or jump to...
Search code, repositories, users, issues, pull requests...
-->
Search
Clear
Search syntax tips
Provide feedback
--><br>We read every piece of feedback, and take your input very seriously.
Include my email address so I can be contacted
Cancel
Submit feedback
Saved searches
Use saved searches to filter your results more quickly
-->
Name
Query
To see all available qualifiers, see our documentation.
Cancel
Create saved search
Sign in
/;ref_cta:Sign up;ref_loc:header logged out"}"<br>Sign up
Appearance settings
Resetting focus
You signed in with another tab or window. Reload to refresh your session.<br>You signed out in another tab or window. Reload to refresh your session.<br>You switched accounts on another tab or window. Reload to refresh your session.
Dismiss alert
{{ message }}
rahulsudhu
primes_of_the_form
Public
Notifications<br>You must be signed in to change notification settings
Fork
Star
main
BranchesTags
Go to file
CodeOpen more actions menu
Folders and files<br>NameNameLast commit message<br>Last commit date<br>Latest commit
History<br>4 Commits<br>4 Commits
cmd/potf
cmd/potf
qf
qf
.gitignore
.gitignore
README.md
README.md
go.mod
go.mod
View all files
Repository files navigation
primes of the form x² + n·y²
A Go implementation of the prime-representation algorithm (Algorithm 39, Section 10) from<br>Quadratic Forms, built on<br>Conway's topograph.
Given any nonzero integer n (with −n not a perfect square), the tool computes a<br>modulus m and residues d₁, …, d_l such that
if an odd prime p ∤ Δ is represented by x² + n·y², then p mod m ∈ {d₁, …, d_l}.
When the genus map is injective — equivalently, when every primitive topograph of<br>discriminant Δ = −4n has reflectional symmetry (Corollary 38) — the condition is exact :<br>those congruence classes contain precisely the represented odd primes p ∤ Δ. Otherwise<br>the tool reports them as necessary only . The special primes (2 and p | Δ) are checked<br>individually by searching the topograph of the form itself.
Negative n works too and classifies x² − |n|·y² via periodic rivers.
Usage
$ go run ./cmd/potf 5<br>...<br>p ≡ 1, 9 (mod 20)
EXACT: the genus map is injective ...
$ go run ./cmd/potf 14 # x²+14y², the paper's necessary-only example<br>$ go run ./cmd/potf -- -5 # x²−5y² (indefinite, river topograph)<br>$ go run ./cmd/potf 1848 # the largest known idoneal number
Flags: -quiet (result only), -no-topo (skip drawings),<br>-max-classes N (cap on enumerated residues; the exact count l is always printed).
The CLI narrates all six algorithm steps and draws the relevant topograph features:
——(-4)————(-2)—————(0)——— ··· ———(2)——————(0)—————(-2)——> (repeats)<br>-bank -1 | -4 | -5 -1
segments of one period:<br># a h b<br>1 1 -4 -1<br>2 1 -2 -4<br>3 1 0 -5<br>⋮ ⋮ ⋮ ⋮<br>6 4 2 -1<br>7 5 0 -1<br>8 4 -2 -1"> class 1: x² + 5y² genus (+1 +1) [principal; reflection-symmetric]<br>\ 2 2 /<br>6 o———————0———————o 6<br>/ 10 10 \
class 1: x² - 5y² (river, Δ = 20)<br>+bank 1 4 | 5 | 4<br>river >——(-4)————(-2)—————(0)——— ··· ———(2)——————(0)—————(-2)——> (repeats)<br>-bank -1 | -4 | -5 -1
segments of one period:<br># a h b<br>1 1 -4 -1<br>2 1 -2 -4<br>3 1 0 -5<br>⋮ ⋮ ⋮ ⋮<br>6 4 2 -1<br>7 5 0 -1<br>8 4 -2 -1
River drawings show the first and last three segments of the period; the full<br>(a, h, b) data accompanies them as a table (also elided for long periods).
How it works (Algorithm 39)
Discriminant. Δ = −4n; reject perfect squares (those topographs have lakes and<br>the form factors).
Classification (Algorithm 15). For Δ , enumerate wells: solutions of<br>ab = (−Δ + h²)/4 with a, b ≥ h ≥ 0, deduplicated by the canonical cyclic order of<br>the three values around the well (mirror wells are distinct classes). For Δ > 0,<br>enumerate river segments a(−b) = (Δ − h²)/4 and follow each river downstream until<br>its period closes; each periodic river is one class. Only primitive forms enter C(Δ).
Reflectional symmetry. A double well is always symmetric; a simple well is symmetric<br>iff two of its three values coincide; a river is symmetric iff the mirror segment<br>generates the same cycle. Cross-checked against the counting identity<br>#ambiguous = 2^(μ−1) = #genera, and genus injectivity is decided by H(Δ) = 2^(μ−1).
Special primes. 2 and each p | Δ are searched on the topograph of f: values<br>strictly grow away from the well / the river's positive bank (climbing lemma), so a<br>pruned flood over the finite band of regions with values ≤ p is an exact<br>membership test and returns a witness vector.
Genus of f. The principal form represents 1, so its signature is (+1, …, +1).
Congruences by CRT. Each character contributes a local constraint — χ₋₁ mod 4,<br>χ₂/χ₋₂ mod 8, χ_p the quadratic (non-)residues mod p generated by squaring —<br>and the locals are glued by the Chinese Remainder Theorem. No sweep over all residues<br>mod m ever happens; work is proportional to the output size, and above -max-classes<br>only the exact count l is...