modexp

README

go-modular-exponentiation

Modular Exponentiation in Golang

• Assume all arguments are positive.
• ModExpGoBigInteger calculates modular exponentiation using math/big package.
• ModExpGoBigIntegerExp calculates modular exponentiation using native Exp method from math/big package.
• ModExp calculates modular exponentiation in O(exponent).
• ModExpWithSquaring calculates modular exponentiation with exponentiation by squaring, O(log exponent).

Benchmarks

# run tests
go test .

# benchmark
go test -bench .

Tested under Golang 1.9.2, 2.8 GHz Intel Core i7, macOS 10.13, calculating 81792 ^ 73363 mod 233.

goos: darwin
goarch: amd64
BenchmarkModExp-8                  	    1000	   1341863 ns/op
BenchmarkModExpWithSquaring-8      	 2000000	       754 ns/op
BenchmarkModExpGoBigInteger-8      	      50	  26960333 ns/op
BenchmarkModExpGoBigIntegerExp-8   	  500000	      2352 ns/op

Documentation

Index

• func ModExp(base, exponent, modulus int64) int64
• func ModExpGoBigInteger(base, exponent, modulus int64) int64
• func ModExpGoBigIntegerExp(base, exponent, modulus int64) int64
• func ModExpWithSquaring(base, exponent, modulus int64) int64

Functions

func ModExp

func ModExp(base, exponent, modulus int64) int64

ModExp calculates modular exponentiation in O(exponent).

func ModExpGoBigInteger

func ModExpGoBigInteger(base, exponent, modulus int64) int64

ModExpGoBigInteger calculates modular exponentiation using math/big package.

func ModExpGoBigIntegerExp

func ModExpGoBigIntegerExp(base, exponent, modulus int64) int64

ModExpGoBigIntegerExp calculates modular exponentiation using native Exp method from math/big package.

func ModExpWithSquaring

func ModExpWithSquaring(base, exponent, modulus int64) int64

ModExpWithSquaring calculates modular exponentiation with exponentiation by squaring, O(log exponent).