{"record":{"id":"85d73ff92f516786","repo":"TheAlgorithms/Go","slug":"integer-overflow","errorCode":null,"errorMessage":"integer overflow","messagePattern":"integer overflow","errorType":"validation","errorClass":null,"httpStatus":null,"severity":"error","filePath":"math/modular/exponentiation.go","lineNumber":18,"sourceCode":"// exponentiation.go\n// description: Implementation of Modular Exponentiation Algorithm\n// details:\n// A simple implementation of Modular Exponentiation - [Modular Exponenetation wiki](https://en.wikipedia.org/wiki/Modular_exponentiation)\n// time complexity: O(log(n)) where n is the exponent\n// space complexity: O(1)\n// author(s) [Taj](https://github.com/tjgurwara99)\n// see exponentiation_test.go\n\npackage modular\n\nimport (\n\t\"errors\"\n\t\"math\"\n)\n\n// ErrorIntOverflow For asserting that the values do not overflow in Int64\nvar ErrorIntOverflow = errors.New(\"integer overflow\")\n\n// ErrorNegativeExponent for asserting that the exponent we receive is positive\nvar ErrorNegativeExponent = errors.New(\"negative Exponent provided\")\n\n// Exponentiation returns base^exponent % mod\nfunc Exponentiation(base, exponent, mod int64) (int64, error) {\n\tif mod == 1 {\n\t\treturn 0, nil\n\t}\n\n\tif exponent < 0 {\n\t\treturn -1, ErrorNegativeExponent\n\t}\n\t_, err := Multiply64BitInt(mod-1, mod-1)\n\n\tif err != nil {\n\t\treturn -1, err\n\t}","sourceCodeStart":1,"sourceCodeEnd":36,"githubUrl":"https://github.com/TheAlgorithms/Go/blob/5ba447ec5ff3d1213de65b92e726ee74c5d5cc19/math/modular/exponentiation.go#L1-L36","documentation":"ErrorIntOverflow is the sentinel error returned by Multiply64BitInt when multiplying two int64 values would exceed int64 range (|left| * |right| > MaxInt64). It protects modular exponentiation internals from silent wrap-around.","triggerScenarios":"Calling modular.Multiply64BitInt(left, right) with large magnitudes, e.g. Multiply64BitInt(math.MaxInt64, 2), or Exponentiation with a large base/mod whose intermediate products exceed int64.","commonSituations":"Cryptography/competitive-programming code with moduli near 2^63; using int64 instead of big.Int for very large exponents; float64-based magnitude precheck losing precision near MaxInt64.","solutions":["Reduce operands modulo mod before multiplying (use modular.Multiply via Exponentiation semantics so values stay < mod).","Use math/big (big.Int.Mul / MulMod-style logic) for values approaching MaxInt64.","Check operands before the call: if |a| > MaxInt64/|b| the multiply will overflow.","Handle the error with errors.Is(err, modular.ErrorIntOverflow) and switch to a wider representation."],"exampleFix":"// before\nr, err := modular.Multiply64BitInt(math.MaxInt64, 2) // ErrorIntOverflow\n\n// after\nbigA, bigB := new(big.Int).SetInt64(a), new(big.Int).SetInt64(b)\nr := new(big.Int).Mul(bigA, bigB) // arbitrary precision","handlingStrategy":"validation","validationCode":"func safeMul(a, b int64) bool {\n    if a == 0 || b == 0 {\n        return true\n    }\n    return math.Abs(float64(a)) <= float64(math.MaxInt64)/math.Abs(float64(b))\n}\n\nif !safeMul(left, right) {\n    // use big.Int instead\n}\nr, err := modular.Multiply64BitInt(left, right)","typeGuard":null,"tryCatchPattern":"r, err := modular.Multiply64BitInt(left, right)\nif errors.Is(err, modular.ErrorIntOverflow) {\n    // fall back to big.Int arithmetic\n}\nif err != nil {\n    return 0, err\n}","preventionTips":["Reduce operands mod mod before multiplying so values stay below MaxInt64.","Reach for math/big when moduli approach 2^63.","Compare with errors.Is against the exported sentinel.","Add boundary tests with MaxInt64 operands."],"tags":["math","integer-overflow","int64","modular-arithmetic","go"],"backgroundTag":"integer-overflow","analyzedSha":"5ba447ec5ff3d1213de65b92e726ee74c5d5cc19","analyzedAt":"2026-09-02T21:54:30.227Z","contentChangedAt":null,"schemaVersion":2},"datasetVersion":"2026-09-10T02:17:09.455Z"}