On the greatest prime factor of $p-1$ with effective constants (Q5315433)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 2203633
Language Label Description Also known as
default for all languages
No label defined
    English
    On the greatest prime factor of $p-1$ with effective constants
    scientific article; zbMATH DE number 2203633

      Statements

      On the greatest prime factor of $p-1$ with effective constants (English)
      0 references
      8 September 2005
      0 references
      It was shown by \textit{M. Goldfeld} [Mathematika 16, Part 1, No. 31, 23--27 (1969; Zbl 0201.05301)] that if \(\theta=0.583\dots\) then there are infinitely many primes \(p\) for which the largest prime factor of \(p-1\) exceeds \(p^\theta\). Various authors have given successively larger admissible values of the constant \(\theta\), the current record being \(\theta=0.677\), due to [\textit{R. C. Baker} and \textit{G. Harman} [Acta Arith. 83, No. 4, 331--361 (1998; Zbl 0994.11033)]. The original version of the polynomial time primality test of \textit{M. Agrawal}, \textit{N. Kayal} and \textit{N. Saxena} [Ann. Math. (2) 160, 781--793 (2004; Zbl 1071.11070)] depended on having such a result with \(\theta>0.5\), although subsequent treatments avoid this. Previously all such results have depended on the standard version of the Bombieri-Vinogradov function, and are therefore ineffective. Certainly it would be unsatisfactory to have a primality testing algorithm which was deterministic, with a rigorously proven running-time bound, but in which the order constant was ineffective! The present paper shows how to obtain an effective result, with \(\theta=0.6105\dots\). The main idea is to use an effective version of the Bombieri-Vinogradov Theorem, in which the moduli are restricted to be primes \(p\) in the range \((\log x)^{10}\leq p\leq x^{1/2} (\log x)^{-10}\). The remaining primes, below \((\log x)^{10}\), can be treated trivially, and make a negligible contribution in the analysis. The value of \(\theta\) is doubtless subject to improvement by the established methods.
      0 references

      Identifiers