function value = prime_power ( a, n, p )

%*****************************************************************************80
%
%% prime_power() computes a^n mod p.
%
%  Licensing:
%
%    This code is distributed under the MIT license. 
%
%  Modified:
%
%    20 September 2024
%
%  Author:
%
%    Original C++ code on Geeks for Geeks.
%    This version by John Burkardt.
%
%  Input:
%
%    integer a: the base.
%
%    integer n: the power.
%
%    integer p: the calculation is to be done mod p.
%
%  Output:
%
%    integer value: the value of a^n mod p.
%
  value = 1;
%
%  Reduce a if p <= a.
%
  a = mod ( a, p );
 
  while ( 0 < n )
%
%  If n is odd, multiply by a.
%
    if ( mod ( n, 2 ) == 1 )
      value = mod ( ( value * a ), p );
    end
%
%  Divide n by 2.
%
    n = floor ( n / 2 );
    a = mod ( ( a * a ), p );

  end

  return;
end

