modular exponentiation?

[Thomas Klemm]

(07-08-2018 09:50 PM)Bill Duncan Wrote:  Has anyone written a POWMOD -like function for the HP-48?

Cf. Modular Arithmetic for the HP-48

Since PLUS is only used by TIMES it can be inlined.
And then you can keep TIMES in a local variable leading to:

Code:

@POWER ( a b n -- a ^ b % n )
« @TIMES ( a b n -- a * b % n )
  « 1000000 → a b n k
    « a k / IP a k MOD
      b k / IP b k MOD
      → x y u v
      « x u * k SQ *
        x v * k *
        y u * k *
        y v *
        4 →LIST
        n MOD
        @PLUS ( a b -- a + b (mod n) )
        « → a b
          « a b +
            IF n OVER ≤
            THEN DROP a n - b +
            END
          »
        »
        STREAM
      »
    »
  »
  → 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
  »
»

(07-09-2018 02:32 AM)Joe Horn Wrote:  There's a "Fast Powering algorithm f exponentiation (mod n)" program called PWR in Anthony Shaw's "MODULO" package for the 48: https://www.hpcalc.org/details/6015

Quote:MODPND
Returns a (mod n). This function assumes that a and n have been entered using the # symbol, which allows for large integers (up to about 10^18). By using MODPND in PRODN, numbers whose product do not exceed 10^18 can be multiplied (mod n). If these programs were implemented in machine language, larger integer arithmetic could be made feasible. For me, small numbers have plenty of interesting properties, so I'm not so concerned about this.

#9876543210987654
#1234567890123456 ---> #90000006

Thus I assume that it will work only up to 10⁹.

Quote:Just wondering before I go off and try it myself.

Just go for it! And post your result.

Cheers
Thomas