DEFINT A-Z
DIM Table(1 TO 1000) AS DOUBLE
CLS
PRINT "Teste Congruencia"
PRINT
INPUT "Base :", b#
INPUT "Expoente :", expo&
INPUT "Congruencia modulo ", modulo&
PRINT b#; "^"; expo&; "ð";
np = INT(LOG(expo&) / LOG(2)) + 1
t& = 1
b# = b# MOD modulo&
IF b# > modulo& \ 2 THEN b# = b# - modulo&
Table(1) = b#
n = 1
DO
   t& = t& * 2
   n = n + 1
   IF t& > expo& THEN EXIT DO
   b# = b# * b#
   b# = b# MOD modulo&
   IF b# > modulo& \ 2 THEN b# = b# - modulo&
   Table(n) = b#
LOOP
result# = 0
flag = -1
DO
   t& = t& \ 2
   n = n - 1
   IF n = 0 THEN EXIT DO
   IF t& <= expo& THEN
      expo& = expo& - t&
      IF flag THEN
         flag = 0
         result# = Table(n)
      ELSE
         result# = result# * Table(n)
         result# = result# MOD modulo&
         IF result# > modulo& \ 2 THEN result# = result# - modulo&
      END IF
   END IF
LOOP
IF result# < 0 THEN result# = result# + modulo&
PRINT result#; " mod."; modulo&
SYSTEM