History Of The Theory Of Numbers - I

CHAP. XJV]
METHODS OP FACTORING.
369
in view of the theorem of Lagrange: If x2—Ry2= *=1) has relatively prime integral solutions x, y, where D< \/R, then D is a denominator of a complete quotient in the expansion of \/R as a continued fraction.
FACTORING BY TJSE or VARIOUS MODULI.
C. F. Gauss110 gave a "method of exclusion," based on the use of various small moduli, to express a given number in a given form mx2+ny2.
V. Bouniakowsky111 noted that information as to the prime factors of a number N may be obtained by comparing the solution x=<t>(N) of 2*z=l (mod N) with the least positive solution x = a found by a direct process such as the following: Since 2a=NK+l, multiply the given AT by the unknown K, each expressed in the binary scale (base 2), add 1 and equate the result to 10... 0. The digits of K are found seriatim and very simply.
H. J. Woodall112 expressed the number N to be factored in the form a°+/3b+... +r, where r< 1000, while a, £,... are small, but not necessarily distinct. Hence the residues of N with respect to various moduli are readily found by tables of residues.
F. Landry113 employed the method of exclusion by small moduli.
D. Biddle114 investigated factors 2Ap+l by using moduli A2, 4A2.
C. E. Bickmore, A. Cunningham and J. Cullen115 each treated the large factor of 1025+1 by use of various moduli, and proved it is prime.
J. Cullen1150 gave an effective graphical process to factor numbers by the use of various moduli; the numbers to be searched for in a diagram are all small.
Alfred Johnsen116 used Rt(p) to denote the numerically least residue of p modulo t. Then, for every p, t, k,
[Rt(k)]2+Rt(p-k2)^Rt(p) (mod*).
If t is a factor of the given number p, the left member will be divisible by t. In practice take k2 to be the nearest square to p, larger or smaller. For example, let p = 4699, k2 = 4624 = 682, p - k2 = 75. Then
t »<68)P 4(75) Sum
7 4 -2 2
13 9 -3 6
*37 '36 i '37
Thus 37 is the least factor of p.
"°Disq. Arith., 1801, Arts. 323-6.
ulMe*m. Ac. Sc. St. P&ersbourg, Math.-Phys., (6), 2, 1841, 447-69. Extract in Bull. Ac. Sc., 6,
p. 97. Cf. Nordlund.117
ll2Math. Quest. Educat. Times, 70, 1899, 68-71; 71, 1899, 124. U3Proce*des nouveaux..., Paris, 1859. Cf. A. Aubry,147 pp. 214-7. 114Mess. Math., 30, 1900-1, 98, 190. Math. Quest. Educat. Times, 74, 1901, 147-152. 116Math. Quest. Educat. Times, 72. 1900, 99-103. iualbid., 73, 1900, 133-5; 75, 1901, 102-4. Proc. London Math. Soc., 34, 1901-2, 323-334;
(2), 2, 1905, 138-141. »«Nyt Tidsskrift for Mat., 15 A, 1904, 109-110.