Modular arithmetic is a form of arithmetic (a calculation technique involving the concepts of addition and multiplication) which is done on numbers with a defined equivalence relation called congruence.

For any positive integer 



p


{\displaystyle p}

 called the congruence modulus,
two numbers 



a


{\displaystyle a}

 and 



b


{\displaystyle b}

 are said to be congruent modulo p whenever there exists an integer 



k


{\displaystyle k}

 such that:





a
=
b
+
k

p


{\displaystyle a=b+k\,p}


The corresponding set of equivalence classes forms a ring denoted 






Z


p

Z






{\displaystyle {\frac {\mathbb {Z} }{p\mathbb {Z} }}}

.

Addition and multiplication on this ring have the same algebraic structure as in usual arithmetics, so that a function such as a polynomial expression could receive a ring element as argument and give a consistent result.

The purpose of this task is to show, if your programming language allows it,
how to redefine operators so that they can be used transparently on modular integers.
You can do it either by using a dedicated library, or by implementing your own class.

You will use the following function for demonstration:





f
(
x
)
=

x

100


+
x
+
1


{\displaystyle f(x)=x^{100}+x+1}


You will use 



13


{\displaystyle 13}

 as the congruence modulus and you will compute 



f
(
10
)


{\displaystyle f(10)}

.

It is important that the function 



f


{\displaystyle f}

 is agnostic about whether or not its argument is modular; it should behave the same way with normal and modular integers.
In other words, the function is an algebraic expression that could be used with any ring, not just integers.




\ We would normally define operators that have a suffix `m' in order
\ not to be confused:  +m -m *m /m **m
\ Also useful is %:m reduce a number modulo.

\ Words that may be not be present in the kernel.
\ This example loads them in ciforth.
WANT ALIAS VOCABULARY

VARIABLE _m ( Modulo number)
\ Set the modulus to  m .
: set-modulus  _m ! ;

\ For A B return C GCD where C*A+x*B=GCD
: XGCD 1 0 2SWAP   BEGIN OVER /MOD OVER WHILE >R SWAP
   2SWAP OVER R> * - SWAP 2SWAP REPEAT 2DROP NIP ;
\ Suffix n : normalized number.
: _norm_-m  DUP 0< _m @ AND + ; ( x -- xn ) \ -m<xn<+m
: +m   + _m @ - _norm_-m  ;   ( an bn -- sumn )
: -m   - _norm_-m  ;         ( an bn -- diffn)
: *m   M* _m @ SM/REM DROP ;  ( an bn -- prodn)
: /m    _m @ XGCD DROP _norm_-m  *m ; ( a b -- quotn)
: %:m  S>D _m @ SM/REM DROP _norm_-m  ;  ( a -- an)

\ Both steps: For A B and C: return A B en C.  Invariant A*B^C.
: _reduce_1-  1- >R >R    R@ *m   R> R> ;
: _reduce_2/  2/ >R    DUP *m        R> ;
( a b -- apowbn )
: **m    1 ROT ROT BEGIN   DUP 1 AND IF   _reduce_1-   THEN
    _reduce_2/ DUP 0= UNTIL   2DROP   ;  

\ The solution is
13 set-modulus
10  DUP 100 **m +m 1 +m . CR

\ In order to comply with the problem we can generate a separate namespace
\ and import the above definitions.

VOCABULARY MODULO
ALSO MODULO DEFINITIONS
' set-modulus ALIAS set-modulus
' +m   ALIAS   +
' -m   ALIAS   -
' *m   ALIAS   *
' /m   ALIAS   /
' **m  ALIAS   **
' %:m   ALIAS   %:m

\ now the calculation becomes
13 set-modulus
10  DUP 100 ** + 1 + . CR

