#### X to the power N, and X to the power N mod M

```check_determ
domains
int = integer
predicates
power(int,int,int)
power_1(int,int,int,int)
powermod(int,int,int,int)
powermod_1(int,int,int,int,int)
clauses

/* power(X, N, Y) is true if Y is the result of raising X to the power N,  */
/*   where N is a positive integer.                                        */
power(X, N, Y):-
N >= 0,
power_1(N, X, 1, Y).

power_1(0, _, Y, Y):-!.
power_1(N, X, Y0, Y):-
1 = N mod 2,
!,
N1 = N div 2,
X1 = X * X,
Y1 = Y0 * X,
power_1(N1, X1, Y1, Y).
power_1(N, X, Y0, Y):-
N1 = N div 2,
X1 = X * X,
power_1(N1, X1, Y0, Y).

/* powermod(X, N, M, Y) is true if Y is the result of raising X to the     */
/*   power N, mod M, where N and M are positive integers.                  */
powermod(X, N, M, Y):-
N >= 0,
M > 0,
powermod_1(N, X, M, 1, Y).

powermod_1(0, _, _, Y, Y):-!.
powermod_1(N, X, M, Y0, Y):-
1 = N mod 2,
!,
N1 = N div 2,
X1 = X * X mod M,
Y1 = Y0 * X mod M,
powermod_1(N1, X1, M, Y1, Y).
powermod_1(N, X, M, Y0, Y):-
N1 = N div 2,
X1 = X * X mod M,
powermod_1(N1, X1, M, Y0, Y).
```