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
0.9166198
0 references
0.9089472
0 references
0 references
0.9020358
0 references
0.9006252
0 references
0.8993858
0 references
0.8970862
0 references
0.89583415
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