|
|||||
 |
|
|
|
|
|
New algorithms
for modular inversion and representation by the form $x^2 +
3xy + y^2$
Christina Doran, Shen Lu and Barry R. Smith
Vol. 10 (2017), No. 4, 541–554
|
Abstract |
|
We observe structure in the sequences of quotients and remainders of the Euclidean algorithm with two families of inputs. Analyzing the remainders, we obtain new algorithms for computing modular inverses and representing prime numbers by the binary quadratic form . The Euclidean algorithm is commenced with inputs from one of the families, and the first remainder less than a predetermined size produces the modular inverse or representation. |
Keywords
number theory, continued fraction, binary quadratic form,
algorithm
|
Mathematical Subject Classification 2010
Primary: 11A05
|
Milestones
Received: 10 September 2013
Revised: 6 May 2015
Accepted: 11 July 2016
Published: 7 March 2017
Communicated by Filip Saidak
|
Authors |
| Christina Doran | |
| Lebanon Valley College 101 College Ave. Annville, PA 17003 United States |
|
| Shen Lu | |
| Lebanon Valley College 101 College Ave. Annville, PA 17003 United States |
|
| Barry R. Smith | |
| Lebanon Valley College 101 College Ave. Annville, PA 17003 United States |
|
|
