On the Number of Solutions of Exponential Congruences

2010/03/09 by Balog, Antal, Broughan, Kevin A., Shparlinski, Igor E.
#11B50 #Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT)

paper · doi:10.48550/arxiv.1003.1997

Abstract

For a prime p and an integer a ∈ \Z we obtain nontrivial upper bounds on the number of solutions to the congruence x^x ≡ a \pmod p, 1 ≤ x ≤ p-1. We use these estimates to estimate the number of solutions to the congruence x^x ≡ y^y \pmod p, 1 ≤ x,y ≤ p-1, which is of cryptographic relevance.

Related

• On the congruence x^x≡ λ\pmod p
• An incomplete variant of Wilson's congruence
• Multiplicative Congruences with Variables from Short Intervals
• Linear Congruences with Ratios
• On Congruences with Products of Variables from Short Intervals and Applications