I am conducting a new Miller Rabin (SPRP test) and editing the first step. Can someone please help me with the last step. Thanks.
Original: Write $n$ $=$ $2^sd+1$ with $d$ odd. Replace:
New Test: Write $n$ $=$ $b^sd+1$ with $d$ not a multiple of $b$.
The second step to the test is the same as the original Miller Rabin Test:
Original: If $a^d$ = $1 \pmod n$ or $a^{2^td} =$ $-1$ $\pmod n$ where $0$ $<$ $t$ $<$ $s$, then $n$ is an $a$-SPRP.
New Test: If If $a^d$ = $1 \pmod n$ then $n$ is an $a$-SPPP.
I am confused at this part:
If $a^{b^td} =$ $x$ $\pmod n$ where $0$ $<$ $t$ $<$ $s$, then $n$ is an $a$-SPRP.
Shouldn't there be $b$ choices for $x$? I do not know how to find these possibilities for $x$.