>From
>[https://github.com/mratsim/number-theory/blob/12c54a7476327cf9ab00989c9964732e3eb68be7/src/modular_arithmetic.nim](https://github.com/mratsim/number-theory/blob/12c54a7476327cf9ab00989c9964732e3eb68be7/src/modular_arithmetic.nim)
Modular addition
proc addmod*[T: SomeInteger](a, b, m: T): T =
## Modular addition
let a_m = if a < m: a
else: a mod m
if b == 0.T:
return a_m
let b_m = if b < m: b
else: b mod m
# We don't do a + b to avoid overflows
# But we know that m at least is inferior to biggest T
let b_from_m = m - b_m
if a_m >= b_from_m:
return a_m - b_from_m
return m - b_from_m + a_m
Run
Modular multiplication
proc mulmod*[T: SomeInteger](a, b, m: T): T =
## Modular multiplication
var a_m = a mod m
var b_m = b mod m
if b_m > a_m:
swap(a_m, b_m)
while b_m > 0.T:
if b_m.isOdd:
result = addmod(result, a_m, m)
#a_m = doublemod(a_m, m)
a_m = (a_m shl 1) - (if a_m >= (m - a): m else: 0)
b_m = b_m shr 1
Run
Modular inversion (via GCD, so can return the GCD)
proc invmod*[T:SomeInteger](a, m: T): T =
## Modular multiplication inverse
## Input:
## - 2 positive integers a and m
## Result:
## - An integer z that solves `az ≡ 1 mod m`
# Adapted from Knuth, The Art of Computer Programming, Vol2 p342
# and Menezes, Handbook of Applied Cryptography (HAC), p610
# to avoid requiring signed integers
# http://cacr.uwaterloo.ca/hac/about/chap14.pdf
# Starting from the extended GCD formula (Bezout identity),
# `ax + by = gcd(x,y)`
# with input x,y and outputs a, b, gcd
# We assume a and m are coprimes, i.e. gcd is 1, otherwise no inverse
# `ax + my = 1`
# `ax + my ≡ 1 mod m`
# `ax ≡ 1 mod m``
# Meaning we can use the Extended Euclid Algorithm
# `ax + by` with
# a = a, x = result, b = m, y = 0
var
a = a
x = 1.T
b = m
y = 0.T
oddIter = true # instead of requiring signed int, we keep track of
even/odd iterations which would be in negative
while b != 0.T:
let
(q, r) = divmod(a,b)
t = x + q * y
x = y; y = t; a = b; b = r
oddIter = not oddIter
if a != 1.T:
# a now holds the gcd(a, m) and should equal 1
raise newException(ValueError, "No modular inverse exists")
if oddIter:
return x
return m - x
Run
The whole point of proof-of-work is to have non-trivial computation.
Factorizing small number is very fast hence you need them at a decent bit-width
but if you're really desperate, I have an arbitrary bigint factorization
algorithm in BrainFuck here ;):
[https://github.com/numforge/laser/blob/d1e6ae61/examples/ex07_jit_brainfuck_src/factor.bf](https://github.com/numforge/laser/blob/d1e6ae61/examples/ex07_jit_brainfuck_src/factor.bf)
