On the distribution of pseudopowers

Sergei V. Konyagin; Carl Pomerance; Igor E. Shparlinski

doi:10.4153/CJM-2010-020-4

On the distribution of pseudopowers

Sergei V. Konyagin, Carl Pomerance, Igor E. Shparlinski

School of Computing

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

Abstract

An x-pseudopower to base g is a positive integer that is not a power of g, yet is so modulo p for all primes p ≤ x. We improve an upper bound for the least such number, due to E. Bach, R. Lukes, J. Shallit, and H. C. Williams. The method is based on a combination of some bounds of exponential sums with new results about the average behaviour of the multiplicative order of g modulo prime numbers.

Original language	English
Pages (from-to)	582-594
Number of pages	13
Journal	Canadian Journal of Mathematics
Volume	62
Issue number	3
DOIs	https://doi.org/10.4153/CJM-2010-020-4
Publication status	Published - Jun 2010

Access to Document

10.4153/CJM-2010-020-4

Cite this

@article{5827bdc42aab4c0ab601b4ca27170cb4,

title = "On the distribution of pseudopowers",

abstract = "An x-pseudopower to base g is a positive integer that is not a power of g, yet is so modulo p for all primes p ≤ x. We improve an upper bound for the least such number, due to E. Bach, R. Lukes, J. Shallit, and H. C. Williams. The method is based on a combination of some bounds of exponential sums with new results about the average behaviour of the multiplicative order of g modulo prime numbers.",

author = "Konyagin, \{Sergei V.\} and Carl Pomerance and Shparlinski, \{Igor E.\}",

year = "2010",

month = jun,

doi = "10.4153/CJM-2010-020-4",

language = "English",

volume = "62",

pages = "582--594",

journal = "Canadian Journal of Mathematics",

issn = "0008-414X",

publisher = "Cambridge University Press (CUP)",

number = "3",

}

TY - JOUR

T1 - On the distribution of pseudopowers

AU - Konyagin, Sergei V.

AU - Pomerance, Carl

AU - Shparlinski, Igor E.

PY - 2010/6

Y1 - 2010/6

N2 - An x-pseudopower to base g is a positive integer that is not a power of g, yet is so modulo p for all primes p ≤ x. We improve an upper bound for the least such number, due to E. Bach, R. Lukes, J. Shallit, and H. C. Williams. The method is based on a combination of some bounds of exponential sums with new results about the average behaviour of the multiplicative order of g modulo prime numbers.

AB - An x-pseudopower to base g is a positive integer that is not a power of g, yet is so modulo p for all primes p ≤ x. We improve an upper bound for the least such number, due to E. Bach, R. Lukes, J. Shallit, and H. C. Williams. The method is based on a combination of some bounds of exponential sums with new results about the average behaviour of the multiplicative order of g modulo prime numbers.

UR - https://www.scopus.com/pages/publications/78049506971

U2 - 10.4153/CJM-2010-020-4

DO - 10.4153/CJM-2010-020-4

M3 - Article

AN - SCOPUS:78049506971

SN - 0008-414X

VL - 62

SP - 582

EP - 594

JO - Canadian Journal of Mathematics

JF - Canadian Journal of Mathematics

IS - 3

ER -

On the distribution of pseudopowers

Abstract

Access to Document

Other files and links

Fingerprint

Cite this