modular exponentiation?

[Thomas Klemm]

(03-15-2015 08:22 AM)Gerald H Wrote:  The programme MMOD finds

X * H MOD M.

MMOD

X MOD 1000000►I:
X-Ans►X:
H MOD 1000000►J:
H-Ans:
((X*Ans MOD M+((X*J MOD M+I*Ans MOD -M)
MOD -M))MOD -M+I*J )MOD M►X:

Stealing this idea I reduced the TIMES program:

Code:

@POWER ( a b n -- a ^ b % n )
« @TIMES ( a b n -- a * b % n )
  « 1000000 → a b n k
    « a k MOD a OVER -
      b k MOD b OVER -
      → y x v u
      « x u * n NEG MOD
        x v * n MOD
        + n NEG MOD
        y u * n MOD
        + n NEG MOD
        y v *
        + n MOD
      »
    »
  »
  → n TIMES
  « 1 ROT ROT
    WHILE DUP
    REPEAT → r a b
      « IF b 2 MOD
        THEN a r n TIMES EVAL @ r → a * r (mod n)
        ELSE r
        END
        a DUP n TIMES EVAL @ a → a ^ 2 (mod n)
        b 2 / IP
      »
    END
    DROP2
  »
»

Thanks to Gerald and kind regards
Thomas