When looking for 6 digit numbers, it will either be the public key, the cipher text or, possibly, p.

Possible primes, p > 304, with a prime root of 10:
313, 337, 367, 379, 383, 389, 419, 433, 461, 487, 491, 499, 503, 509, 541, 571, 577 ...