How to solve really large (exponential) equations

Question

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.

Answer 1

No problem with Pari/GP (http://pari.math.u-bordeaux.fr/)

(09:13) gp > m=6661*94351^71
%31 = 10728560771015633819707207064874692244328700208929760582498189621675783080
20207856546548894585257127883097219939984939643949924262349813577842378181026096
94871715213643797538411151142055451998935805409949386505519146662609279671130973
41460721844136867736767019936070901807174213913734136267620800872781338800800516
81396011396326568731149461927372045730084011
(09:14) gp > n=16983000*94351^70
%32 = 28991449799688614798167598522182541297839008402277778440727848792763473447
83694755140024823912392464974647866417199003946287365173926080216879715371822056
28566383280561497208001611363012272840568357988048958798139964863302941370736289
08197701596448091428770771396260656290585337601764231348244410716079681845051199
432250391089913018833087400470662252983000
(09:14) gp > Mod(2,m)^n
%33 = Mod(1, 1072856077101563381970720706487469224432870020892976058249818962167
57830802020785654654889458525712788309721993998493964394992426234981357784237818
10260969487171521364379753841115114205545199893580540994938650551914666260927967
11309734146072184413686773676701993607090180717421391373413626762080087278133880
080051681396011396326568731149461927372045730084011)
(09:14) gp > Mod(3,m)^n
%34 = Mod(1, 1072856077101563381970720706487469224432870020892976058249818962167
57830802020785654654889458525712788309721993998493964394992426234981357784237818
10260969487171521364379753841115114205545199893580540994938650551914666260927967
11309734146072184413686773676701993607090180717421391373413626762080087278133880
080051681396011396326568731149461927372045730084011)

I.e. both expressions are $1 \pmod m$.

Answer 2

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: