On factorisation, with a suggested new approach
Author: J. C. P. Miller
Journal: Math. Comp. 29 (1975), 155-172
MSC: Primary 10A25; Secondary 10-04
MathSciNet review: 0366796
Full-text PDF Free Access
Abstract: This paper gives a brief survey of methods based mainly on Fermat's Theorem, for testing and establishing primality of large integers. It gives an extension of the Fermat-Lucas-Lehmer Theorems which allows us to establish primality, or to factorise composites, in cases where the Carmichael -exponent is known (or a multiple or submultiple of it, by a moderate factor). The main part of the paper is concerned with describing a method for determining the -exponent in cases where the Fermat test is not satisfied. This method is a variation of A. E. Western's method for finding indices and primitive roots, based on congruences , where N is the number whose exponent is required, and both a and b are -numbers, that is, having no factor larger than , the kth prime. The most onerous problem lies in the finding of a sufficient number of congruences (at least k) and in the choice of a suitable value of k. The determination of the approximate number of -splittings available is considered, to allow an estimate of the amount of labour (human or electronic) needed to be made.
The final suggestion, rather inconclusive, is that the method has possibilities worth exploring further and may be as economical, after development, as existing methods, and possibly more so when N is large.
- [J] John Brillhart and J. L. Selfridge, Some factorizations of 2ⁿ±1 and related results, Math. Comp. 21 (1967), 87-96; corrigendum, ibid. 21 (1967), 751. MR 0224532, https://doi.org/10.1090/S0025-5718-67-99898-5
- [N] N. G. de Bruijn, On the number of positive integers ≤𝑥 and free of prime factors >𝑦, Nederl. Acad. Wetensch. Proc. Ser. A. 54 (1951), 50–60. MR 0046375
- [R] CARMICHAEL 1914, The Theory of Numbers.
- [G] H. HARDY 1940, Ramanujan, Cambridge Univ. Press, Cambridge. MR 3, 71.
- [D] D. G. Hazlewood, On integers all of whose prime factors are small, Bull. London Math. Soc. 5 (1973), 159–163. MR 337846, https://doi.org/10.1112/blms/5.2.159
- [D] D. H. Lehmer, Some new factorizations of 2ⁿ±1, Bull. Amer. Math. Soc. 39 (1933), no. 2, 105–108. MR 1562560, https://doi.org/10.1090/S0002-9904-1933-05571-4
- [D] D. H. Lehmer, On the Converse of Fermat’s Theorem, Amer. Math. Monthly 43 (1936), no. 6, 347–354. MR 1523680, https://doi.org/10.2307/2301798
- [D] D. H. Lehmer, A factorization theorem applied to a test for primality, Bull. Amer. Math. Soc. 45 (1939), no. 2, 132–137. MR 1563926, https://doi.org/10.1090/S0002-9904-1939-06917-6
- [P] POULET 1928, Sphinx-Oedipe, 23, 1928.
- [A] A. E. Western and J. C. P. Miller, Tables of indices and primitive roots, Royal Society Mathematical Tables, Vol. 9, Published for the Royal Society at the Cambridge University Press, London, 1968. MR 0246488
- BRILLHART & J. L. SELFRIDGE 1967, "Some factorizations of and related results," Math. Comp., v. 21, 1967, pp. 87-96; Corrigendum, ibid., v. 21, 1967, p. 751. MR 37 #131. MR 0224532 (37:131)
- G. DE BRUIJN 1951, "On the number of positive integers and free of prime factors ," Nederl. Akad. Wetensch. Proc. Ser. A, v. 54, 1951, pp. 50-60. MR 13, 724. MR 0046375 (13:724e)
- CARMICHAEL 1914, The Theory of Numbers.
- H. HARDY 1940, Ramanujan, Cambridge Univ. Press, Cambridge. MR 3, 71.
- G. HAZLEWOOD 1973, Bull. London Math. Soc., v. 5, 1973, pp. 159-163. MR 0337846 (49:2615)
- H. LEHMER 1933, "Some new factorizations of ," Bull. Amer. Math. Soc., v. 39, 1933, pp. 105-108. MR 1562560
- H. LEHMER 1936, Amer. Math. Monthly, v. 43, 1936, pp. 347-354. MR 1523680
- H. LEHMER 1939, "A factorization theorem applied to a test for primality," Bull. Amer. Math. Soc., v. 45, 1939, pp. 132-137. MR 1563926
- POULET 1928, Sphinx-Oedipe, 23, 1928.
- E. WESTERN & J. C. P. MILLER 1968, Tables of Indices and Primitive Roots, Roy. Soc. Math. Tables, vol. 9, Cambridge Univ. Press, London. MR 39 #7792. MR 0246488 (39:7792)