## Description

Arjen Markus 19 november 2002. In reaction to a discussion in the Tclers' chat room:

A function that is used quite regularly in cryptographic applications is:

`P(n,r,m) = n^r mod m`

(n^r denotes n to the power r, all three parameters are positive integers)

This function does not exist as such within the expr command, but it is simple to create a procedure that evaluates this function efficiently.

The parameters for this function are usually large enough to make a direct calculation impossible. But the trick is to recognise that n^r can be written as n^(r/2)*n^(r/2) when r is even. If r is odd, then write it as:

`n^r = n * (n^(r-1))`

and then we have the first case back.

Furthermore, the modulo function is very well behaved:

`(h * g) mod m = ( (h mod m) * (g mod m) ) mod m`

Given these observations, here is a recursive proc that evaluates the above function in at most 2*log2(r) steps. This can probably be improved, but I am a bit lazy.

## History

AM Repaired a stupid mistake at the bottom. rmax provided some useful comments - so changed the body into a if-elseif-chain

WARNING The code as shown only works correctly on 64-bits machines or when all intermediate results fit in a 32-bits integer. This requires some more work right now ...

AM: No, from 8.5 onwards, Tcl has arbitrary-precision integers, so that even 52131^53124 can be computed (even though it is a ridiculously large number). The code and comments should be updated.

## Code

```proc powm {n r m} {
#
# Take care of the trivial cases first (they also stop the recursion)
#
if { \$r == 0 } {
set result 1
} elseif { \$r == 1 } {
set result [expr {\$n % \$m}]
} elseif { \$r%2 == 0 } {
set nn [powm \$n [expr {\$r/2}] \$m]
set result [expr { (\$nn*\$nn) % \$m} ]
} else {
set nn [powm \$n [expr {\$r-1}] \$m]
set result [expr { (\$n*\$nn) % \$m} ]
}
return \$result
}

#
# Testing the function
#
# The following cases are easy to verify manually:
# powm(1,10,2) = 1
# powm(2,10,3) = 1024 mod 3 = 1
# powm(3,4,5) = 81 mod 5 = 1

puts "powm(1,10,2) = [powm 1 10 2 ]"
puts "powm(2,10,3) = [powm 2 10 3 ]"
puts "powm(3, 4,5) = [powm 3  4 5 ]"

#
# Larger numbers (results respectively, 1, 71, 381, 12685)
#
puts "powm(31,24,15)          = [powm 31 24 15 ]"
puts "powm(131,124,115)       = [powm 131 124 115 ]"
puts "powm(2131,3124,4115)    = [powm 2131 3124 4115 ]"
puts "powm(52131,53124,54115) = [powm 52131 53124 54115 ]"```

Note that in the last test cases the intermediate numbers would be much too big to deal with directly:

`    52131^53124 = Order(10^246334)`

or, to put it in another way, a figure with a quarter million digits

rmax -- If you want to use this function in real-world applications you might be interested in the following optimized version which runs 20..50% faster, depending on the Tcl version. Interpretation is left as an exercise to the reader.

```proc powm {n r m} {
expr {\$r & 1 ?
\$n * [powm \$n [expr {\$r-1}] \$m] % \$m : \$r ?
[set nn [powm \$n [expr {\$r >> 1}] \$m]] * \$nn % \$m : 1 }
}```

When you have Tcl 8.4 you can use the wide() function to promote n to a wide integer which raises the 32bit barrier noted above to 64bit:

```proc powm_wide {n r m} {
powm [expr {wide(\$n)}] \$r \$m
}```

 Category Cryptography Category Mathematics