[bug-gawk] missing function powm and friends

[Michael Plugge]

Hello,
some days ago I wanted to check a php script for the paillier krypto system via awk (http://services.informatik.hs-mannheim.de/kryptolern/paillier_gmp.php; a description of the system can be found in http://en.wikipedia.org/wiki/Paillier_cryptosystem).

When using very small parameters, the validation is no problem, but already p=76907, q=41113, g=77453, r=451653 leads to

c = g^m * rⁿ mod n² = 77453²³³¹² * 451653^3161877491 mod 9997469268092455081

gawk fails on the second exponentiation due to memory problems, because first the exponentiation is done, then modulus.

I wrote a small patch to use the powm() function (and also gcd() and next_prime()) of gmp; this works even for very large parameters and exponents. The appended patch file includes also an integer version of the routines. It would be really great if it could be integrated into gawk :-).

Best regards

Michael

powm.zip
Description: Zip archive