_Added in 3.6_

*$powmod(base, exponent, modulus)*

('base' raised to the 'exponent' power) modulo 'modulus'

'modulus' is the name for the operand following the % operator. In this next example, the modulus is 1907.

<pre>//echo -a $powmod(2,111,1907) same as $calcint( (2^111) % 1907)</pre>

This identifier can be used for:
public key encryption
modular inverse
testing if numbers are prime.

The most common use for $powmod is in public key encryption, though there are also some pseudo-random number generators which use the math of powmod to create random-looking output and to disguise future randoms from someone who knows prior randoms.

However, when 'exponent' becomes too large, it's very slow if not impossible to obtain the result using the above $calcint() method directly. When N is approx 12 digits or longer, $calcint() returns 0 for 2^N. Somewhere just short of that, your client freezes for a long time while $calcint(2^123456789012) tries to calculate a number with more than a million digits.

All 3 parameters MUST be integers. If any parameter has a fraction, result is as if that parameter were zero.

* 'base' should be an integer except 0 or 1, where the results are simplistic. If 'base' = 1, output is 1. If 'base' = 0, output is 0. If 'base' is negative N, then output is same as output for 'base' being $abs(N)

* 'exponent' should be an integer 2 or greater. If 'exponent' = 1, result is the remainder from "base divided by modulus", which is always 'base' if it's less than 'modulus'. If exponent is 0 or negative, result is 1.

* 'modulus' should be non-zero to avoid divide by zero. If 'modulus' is 0, result is 0. If 'modulus' is negative, result is same as for modulus $abs(modulus)

The rest of this explanation describes how $powmod() is used for the portion of the Diffie-Hellman key exchange described at https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange as it relates to the DH1080 key exchange performed by the FiSH dll. DH is not a way to simplify the choosing of encryption keys, it's a way to share them in a way which hides the key from an observer who can see all communications between the two people.

In the DH key exchange, powmod is the easy way to create the 'hard problem' that protects the shared secret when the prime is a sufficiently large "safe prime". In this example, Alice and Bob perform DH key exchange using safe prime 1907 to hide the shared secret from Eve the eavesdropper. Private key MUST be chosen less than 'prime' and MUST be greater than 1. All 'safe prime' divided by 24 have a remainder either 11 or 23. If 'safe prime' were divisible by 23, private key should be further limited to be no greater than q=(prime-1)/2. However, when 'safe prime' divided by 24 is 11, then the private key is an even number when $powmod(public_key,q,prime) is 1, otherwise the private key is odd. If 'exponent' is greater than 'modulus', it has an equivalent result to another 'exponents' which can be easily calculated. i.e. this is always the same: //var %prime 1907 , %n $rand(0,99) | echo -a $powmod(2,$calc( (%prime -1)* %n +321),%prime)

prime = 1907
a = Alice private key 456
A = Alice public key = $powmod(2,456,1907) = 1892
b = Bob private key 789
B = Bob public key = $powmod(2,789,1907) = 1193

Identical shared secret can be calculated 2 different ways:
$powmod(B,a,prime)
$powmod(A,b,prime)

<pre>//echo -a $powmod(1193,456,1907) same as $powmod(1862,789,1907) = same shared secret 719</pre>

Eve sees Alice and Bob sharing the 1892 and 1193 public keys, but must search to find $powmod(2, unknown exponent,1907) which results in 1892.

<pre>//var %i 2 | while (%i isnum 2-1906) { if ($powmod(2,%i,1907) = 1193) { echo -a bob private key is %i | halt } | inc %i } | echo -a private key somehow not found</pre>

Because 1907 % 24 is 11, Eve had a shortcut to test only half the private keys within the 2 thru prime-1 range, instead of all the keys in the 2 through (prime-1)/2 range if the result were 23:
<pre>
//echo -a $powmod(1892,953,1907) is 1, so Eve knows that Alice's private key is even
//echo -a $powmod(1193,953,1907) is (prime-1), so Eve knows that Bob's private key is odd</pre>

This task is much harder in the math used by FiSH_10.dll, where the 'safe prime' is 1080 bits in size. In actual usage, the private key would be much larger than 20 digits:

<pre>//var %prime 12745216229761186769575009943944198619149164746831579719941140425076456621824834322853258804883232842877311723249782818608677050956745409379781245497526069657222703636504651898833151008222772087491045206203033063108075098874712912417029101508315117935752962862335062591404043092163187352352197487303798807791605274487594646923 , %private_key 12345678901234567890 | echo -a public key is $powmod(2,%private_key,%prime)
</pre>
result: public key is 9096966601866802454683190856290401982846740225771867061600052568524959430855875148034766550337128449963518566421940946368033643297332206037516752463116368229254753990477791648737943826345055751194771858378452414281379237175301877700199154665816026591638021196652764283978525694745846158272612738555767737982450470691841483186

DH needs authentication, a way to guarantee that the public keys Alice and Bob receive from each other are actually the public keys sent by the other person. Alice and Bob's communication can be intercepted by Mallory who can then send their own Fake-Alice-public-key to Bob and send a Fake-Bob-public-key to Alice. When Bob and Alice generate their secret key, they are actually sharing a key with Mallory instead of with each other, and the secret Mallory shares with Alice is different than Mallory's secret shared with Bob, and is different than the secret that would've been shared if Alice and Bob had used each other's true public keys.

Mallory can then intercept Bob's messages to Alice using the Mallory/Bob secret, decrypt the messages, then re-encrypt the messages using the Mallory/Alice secret and send the messages to Alice. Without authentication, Alice and Bob don't realize that Mallory has read all their messages, and possibly is editing them, until Mallory is no longer there to intercept and substitute messages.

*Modular Inverse*

Another use for $powmod is that it's sufficient for calculating the 'multiplicative modular inverse' of a number, using Euler's theorem where, in the case when 'm' is a prime, this inverse of 'a' is $powmod(2,a,m-2). Because this always works when 'm' is prime, and usually fails when 'm' is not prime, this also can serve as a tool to test whether large numbers are actually primes. The more 'a' values you test against an 'm' without a failure, the more likely that 'm' is prime.

<pre>alias invmod return $powmod($2,$calcint($3 -2),$3)</pre>

The multiplicative modular inverse is not quite the same as the normal inverse having a fraction. In normal inverse, the inverse of 9 is 1/9 because 9 * 1/9 is 1. With modular inverse, the answer can be different for each prime used as the modulus, and is a number which multiplies against the original number to obtain a product which divided by the modulus is 1.

For example, the modular inverse of 111 when using the prime 1907 is 1048. $invmod(2,111,1907) This can be tested by multiplying 111 * 1048 = 116328, then verifying the result is 1:

<pre>//echo -a $calcint(116328 % 1907)</pre>

When the modulus is prime, even though there are many possible numbers which could return the correct answer, for purposes of the modular inverse there is only 1 good answer, and checking the answer's inverse always returns the original number:

<pre>//var -s %a $invmod(2,111,1907) , %b $invmod(2,%a,1907)</pre>

*Primality Testing*

From a brute-force test of all numbers from 2 through N-1, you can see that, when N is a prime, all values in that range generate the correct inverse, while when N is not prime it fails for the vast majority of values in the range:

//var %candidate 65537 , %i 2 , %yes 0 , %no 0 | while (%i < %candidate) { var %a $calcint( ($invmod(2,%i,%candidate) * %i) % %candidate) | if (%a == 1) inc %yes | else inc %no | inc %i } | echo -a candidate %candidate : yes %yes no %no

Result: candidate 65537 : yes 65536 no 0

When the candidate is not a prime, then it fails most of the time:

candidate 65535 : yes 15 no 65518
candidate 6789 : yes 15 no 6772

When testing very large numbers, it does not need to be a brute-force test of all numbers in the range, since only 1 failure is enough to reject the number as not-prime. For example, the following number was carefully crafted to pass 15 rounds of the Miller-Rabin primality test, however when you use this test where 'a' is the numbers in the range 2-65535, approximately half the numbers fail, so you wouldn't need to test many 'a' values to find one which fails.

candidate 57913900247347612352672951286823975508416170127795120339917871892777383057003 : yes 32843 no 32691

For most not-prime numbers, the number of 'yes' results is a very small percentage. For example, running the same test against the latest candidate where the last digit is changed from 3 to 1, only 1 of 65534 numbers gave the correct result.