Clear[RabinMillerPrime]
RabinMillerPrime::"pseudoprime" = "strenge Pseudoprimzahl zur \
Basis `1`";
RabinMillerPrime::"zusammengesetzt" = "`1` ist Zeuge f\
ür Zerlegbarkeit";
\(RabinMillerPrime[p_, a_] := 
      Module[{s, u, fertig, potenz}, 
s = 
          IntegerExponent[p - 1, 2]; 
u = \((p - 1)\)/
            2^s; 
potenz = 
          PowerMod[a, u, p]; 
If[potenz == 1, 
          Message[RabinMillerPrime::"pseudoprime", a]; 
          Return[True]]; 
fertig = 
          False; 
While[
          Not[fertig]\  && \ u < p - 1, 
If[
            potenz == p - 1, fertig = True, 
u = 2*u; 
            potenz = PowerMod[potenz, 2, p]]]; 
If[fertig, 
          Message[RabinMillerPrime::"pseudoprime", a], 
          Message[RabinMillerPrime::"zusammengesetzt", 
            a]
]; 
fertig
]\)
RabinMillerPrime[p_] := 
      Module[{a}, 
a = 
          Random[Integer, {2, p - 1}]; 
RabinMillerPrime[p, 
          a]
]

RabinMillerPrime[1234567, 2]

RabinMillerPrime[Prime[(10^9)]*Prime[(2^30)], 2]

Carmichaelzahlen

RabinMillerPrime[2465, 2]

RabinMillerPrime[41041, 2]

RabinMillerPrime[825265, 2]

NextPrime[n_] := n + 1 /; PrimeQ[n + 1]
NextPrime[n_] := NextPrime[n + 1]

p = NextPrime[(10^100)]

Union[Table[RabinMillerPrime[p, a], {a, 2, 10}]]

p = NextPrime[(10^100)]*NextPrime[(10^101)]

RabinMillerPrime[p]

0.25^100