# Modular multiplication without overflow

**URL:** <https://discourse.julialang.org/t/modular-multiplication-without-overflow/90421>\
**Category:** Performance\
**Created:** [November 18, 2022, 1:47am UTC](https://discourse.julialang.org/t/modular-multiplication-without-overflow/90421 "2022-11-18T01:47:32Z")\
**Posts on this page:** 1\
**Showing post:** 4

<div class="post-metadata">

**Author:** ![jd-foster](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jd-foster/32/35824_2.png) [@jd-foster](https://discourse.julialang.org/u/jd-foster)\
**Post date:** [November 18, 2022, 11:33am UTC](https://discourse.julialang.org/t/modular-multiplication-without-overflow/90421/4 "2022-11-18T11:33:44Z")

</div>

Translating the (completely opaque and unverified) wikipedia code to an equally dodgy julia version:

> **Listing: \`mul\_mod(a,b,c)\`**
>
> ```julia
> function mul_mod(a::UInt128, b::UInt128, m::Integer)
> 
> magic1 = (UInt128(0xFFFFFFFF) << 32)
> magic2 = UInt128(0x8000000000000000)
> 
> if iszero(((a | b) & magic1))
> return (a * b) % m
> end
> 
> d = zero(UInt128)
> mp2 = m >> 1
>     
> if a >= m; a %= m; end
> if b >= m; b %= m; end
> 
> for _ in 1:64
> (d > mp2) ? d = ((d << 1) - m) : d = (d << 1)
> if !iszero(a & magic2)
> d += b
> end
> if d >= m
> d -= m 
> end
> a <<= 1
> end
> 
> return d
> end
> 
> function mul_mod(a::Integer, b::Integer, m::Integer)
> sa, sb = UInt128.(unsigned.((a,b)))
> return mul_mod(sa, sb, m)
> end
> 
> ```

“Testing”:

```julia
julia> a, b, c = (4856388669903036, 6493747681980967, 3860134847225580)
(4856388669903036, 6493747681980967, 3860134847225580)

julia> (big(a) * big(b)) % big(c) ## Correct, but using BigInt
3059575088694852

julia> (a * b) % c ## Incorrect
2569083244915888

julia> ((a % c) * (b % c)) % c ## Also incorrect due to overflow of multiplication
226995574897440

julia> mul_mod(a, b, c) |> Int128 ## Correct, without BigInt conversion
3059575088694852
```

---

_[View the full topic](https://discourse.julialang.org/t/modular-multiplication-without-overflow/90421)._