How to solve really large (exponential) equations For the purpose of field extensions, and other field properties, is there a program capable of computing
$2^{16983000*94351^{70}}$ $\pmod {6661*94351^{71}}$
$3^{16983000*94351^{70}}$ $\pmod {6661*94351^{71}}$
Please give examples of some. Thank you.
I am aware this is not a direct mathematical concept, but if someone can give me an example of a program able to perform such direct computations, the results of the modulo reduction can be used for applications to field extensions.
 A: Below is an implementation of Exponentiation by squaring in Scheme (Guile):
(use-modules (srfi srfi-1))

(let ((a 2)
      (a* 3)
      (n (* 16983000 (expt 94351 70)))
      (m (* 6661 (expt 94351 71))))

  (define (binary-representation n)
    (number->string n 2))

  (define (number-of-bits n)
    (string-length (binary-representation n)))

  (define (kth-most-significant-bit n k)
    (string-ref (binary-representation n)
                k))

  (define (expt-table a n m)
    (fold (lambda (k accum)
            (if (zero? k)
                (list a)
                (let ((last-elt (car accum)))
                  (cons (modulo (expt last-elt 2)
                                m)
                        accum))))
          '()
          (iota (number-of-bits n))))

  (define (expt-by-squaring a n m)
    (fold (lambda (k accum)
            (if (char=? (kth-most-significant-bit n k)
                        #\1)
                (modulo (* accum
                           (list-ref (expt-table a n m)
                                     k))
                        m)
                accum))
          1
          (iota (number-of-bits n))))

  (display (expt-by-squaring a n m))
  (newline)
  (display (expt-by-squaring a* n m))
  (newline))

Demo:

Source code with syntax-highlighting:


