(* 
      RSA  -  
        Verfahren *) 

p  =  Prime[2000]

    q  =  Prime [3000]

p * q

(p - 1) (q - 1)

GCD [23,  (p - 1) (q - 1)]

GCD [125,  (p - 1) (q - 1)]

k  =  125

ExtendedGCD [125,  (p - 1) (q - 1)]

t  =  (p - 1) (q - 1)  +  ExtendedGCD [
              125,  (p - 1) (q - 
                    1)] [[2]] [[1]]

FastPower [basis_,  0,  modulus_]  :=  1

FastPower [basis_,  exponent_,  
        modulus_]  := 
    If [
        EvenQ [exponent], 
                  (* then *) 
                 Mod [
                         (FastPower [basis, (exponent/2),  
                modulus])^2, 
                          modulus
                     ], 
                (* 
          else *) 
               Mod [
                        basis * (FastPower [basis,  (exponent  -  1) / 2,  
                  modulus])^2, 
                        modulus
                   ]]

FastPower [1000000,  k,  p q]

FastPower [449132563,  t,  p q]