I'm not entirely sure what you're asking here OP, but a couple of things popped into my mind while RE-reading:

1. Using the formula for new_x i presented, if we have to start with x = 9, then we have (x2 - 1)2 = 6400, which means the formula will never reach 10 for any p where 6400 = 0 (mod p), or for which (64002 - 1)2 = 1677721518080001 = 0 (mod p), etc.
 
2. Though you possibly qualified it by saying "at least in the context of...", I just thought I'd note that 2 is not necessarily a generator of ℤp× where p is prime. Consider, for example, p = 7.

Of course, I may be misunderstanding entirely what you're wanting to do.