Representing a prime p=5n ± 1 as x2 + 3xy + y2, where x > y ≥ 1
The underlying algorithm was published in
New algorithms for modular inversion and representation by binary quadratic forms arising from structure in the Euclidean algorithm, Christina Doran, Shen Lu and Barry R. Smith.
First find the solution v of the congruence v2 + v - 1 ≡ 0 (mod p), where v < p/2.
Then perform the Euclidean algorithm with p and v.
The length of the Euclidean algorithm is 2s + 1 and the sequence of quotients has the form
q1, … , qs-1, qs + (-1)s+1, 1, qs, qs-1, … , q1.
Then rs+1 is the first remainder less than √(p/5) and rs-1 = rs + rs+1. Also
- p = x2 + 3xy + y2, where y = rs+1 and x = rs or rs – rs+1, according as s is odd or even;
- p = x2 + xy - y2, where y = rs+1 and x = rs or rs + rs+1, according as s is even or odd.
The representation in positive integers x and y with x > y, is unique.
This is a BCmath version of a BC program.
Last modified 22nd May 2015
Return to main page