По-моему, p - простое, и 1 <= x < p. Вроде больше нет условий :)
Но я RSA уже очень давно не трогаю и этот алгоритм в частности, поэтому могу ошибаться. p может и не быть простым, но это связано с тем, что для очень больших чисел нельзя быть на 100% уверенным, что данное число является простым, если есть ограниченные временные рамки.