bigInt

local littleBASE = 2
local base_exponent = 25
local BASE = littleBASE^base_exponent
local BASE_LEN = math.ceil(math.log10(BASE))

local ZERO, ONE, TWO

--===== MAIN ARITHMETIC METHODS =====--
function add(x, y)
    if x == nil or y == nil then
        error("bigInt add: missing parameter")
    elseif x.isBig ~= true or y.isBig ~= true then
        error("bigInt add: invalid parameter")
    elseif not x.sign and y.sign then
        y.sign = not y.sign
        local ans = sub(x, y)
        y.sign = not y.sign
        return ans
    elseif x.sign and not y.sign then
        x.sign = not x.sign
        local ans = sub(y, x)
        x.sign = not x.sign
        return ans
    elseif x.sign and y.sign then
        x.sign, y.sign = not x.sign, not y.sign
        local ans = -add(x, y)
        x.sign = not x.sign
        y.sign = not y.sign
        return ans
    end
    local ans = new()
    local carry = 0
    for i = 0, math.max(#x, #y) do
        ans[i] = (x[i] or 0) + (y[i] or 0) + carry
        if ans[i] >= BASE then
            ans[i] = ans[i] - BASE
            carry = 1
        else
            carry = 0
        end
    end
    ans[math.max(#x, #y) + 1] = carry
    removeZeroes(ans)
    return ans
end

function sub(x, y)
    if x == nil or y == nil then
        error("bigInt sub: missing parameter")
    elseif x.isBig ~= true or y.isBig ~= true then
        error("bigInt sub: invalid parameter")
    elseif not x.sign and y.sign then
        y.sign = not y.sign
        local ans = add(x, y)
        y.sign = not y.sign
        return ans
    elseif x.sign and not y.sign then
        x.sign = not x.sign
        local ans = -add(x, y)
        x.sign = not x.sign
        return ans
    elseif x.sign and y.sign then
        x.sign, y.sign = not x.sign, not y.sign
        local ans = sub(y, x)
        x.sign = not x.sign
        y.sign = not y.sign
        return ans
    elseif compareAbs(x, y) == -1 then
        return -sub(y, x)
    end
    local ans = new()
    local carry = 0
    for i = 0, #x do
        ans[i] = (x[i] or 0) - (y[i] or 0) - carry
        if ans[i] < 0 then
            ans[i] = ans[i] + BASE
            carry = 1
        else
            carry = 0
        end
    end
    removeZeroes(ans)
    return ans
end

function mul(x, y)
    if x == nil or y == nil then
        error("bigInt mul: missing parameter")
    elseif x.isBig ~= true or y.isBig ~= true then
        error("bigInt mul: invalid parameter")
    elseif x.sign and not y.sign then
        x.sign = not x.sign
        local ans = -mul(x, y)
        x.sign = not x.sign
        return ans
    elseif not x.sign and y.sign then
        y.sign = not y.sign
        local ans = -mul(x, y)
        y.sign = not y.sign
        return ans
    elseif x.sign and y.sign then
        x.sign, y.sign = not x.sign, not y.sign
        local ans = mul(x, y)
        x.sign, y.sign = not x.sign, not y.sign
        return ans
    end
    local ans = new()
    local carry = 0
    local temp = 0
    for i = 0, #y do
        carry = 0
        for j = 0, #x do
            temp = (ans[i + j] or 0) + (x[j]*y[i]) + carry
            ans[i + j] = temp % BASE
            carry = math.floor(temp/BASE)
        end
        ans[i + #x + 1] = carry
    end
    removeZeroes(ans)
    return ans
end

function div(x, y)
    if x == nil or y == nil then
        error("bigInt div: missing parameter")
    elseif x.isBig ~= true or y.isBig ~= true then
        error("bigInt div: invalid parameter")
    elseif compareAbs(y, ZERO) == 0 then
        error("bigInt div: attempt to divide by zero")
    elseif not x.sign and y.sign then
        y.sign = not y.sign
        local quot, rem = div(x, y)
        y.sign = not y.sign
        return -quot, rem
    elseif x.sign and not y.sign then
        x.sign = not x.sign
        local quot, rem = div(x, y)
        x.sign = not x.sign
        if compare(rem, ZERO) == -1 then
            quot = add(quot, ONE)
            rem = sub(y, rem)
        end
        return -quot, rem
    elseif x.sign and y.sign then
        x.sign, y.sign = not x.sign, not y.sign
        local quot, rem = div(x, y)
        if compare(rem, ZERO) == -1 then
            quot = add(quot, ONE)
            rem = sub(y, rem)
        end
        x.sign, y.sign = not x.sign, not y.sign
        return quot, rem
    elseif #x == 0 and #y == 0 then
        return new(math.floor(x[0]/y[0])), new(x[0] % y[0])
    elseif compareAbs(x, y) == -1 then
        return new(), copy(x)
    end

    --Normalisation
    local scaledY = copy(y)
    local scaledX = copy(x)
    local lambda = 0
    while scaledY[#scaledY] < BASE/littleBASE do
        lambda = lambda + 1
        left_shift(scaledY, 1)
        left_shift(scaledX, 1)
    end
    --Step 1
    local n, t = #scaledX, #scaledY
    local quot = alloc(n - t)

    --Step 2
    local tempY = copy(scaledY)
    shift_base(tempY, n - t)
    while compare(scaledX, tempY) ~= -1 do
        quot[n - t] = quot[n - t] + 1
        scaledX = sub(scaledX, tempY)
    end

    --Step 3
    local topY = new()
    topY[1] = scaledY[t]
    topY[0] = scaledY[t - 1] or 0
    local tempX = new()
    for i = n, t + 1, -1 do

        os.queueEvent("bigInt_yield")
        os.pullEvent()

        tempX[2] = scaledX[i] or 0
        tempX[1] = scaledX[i - 1] or 0
        tempX[0] = scaledX[i - 2] or 0

        --Step 3.1
        if tempX[2] == scaledY[t] then
            quot[i - t - 1] = BASE - 1
        else
            quot[i - t - 1] = math.floor((tempX[2]*BASE + tempX[1])/scaledY[t])
        end

        --Step 3.2
        local step = 0
        while compare(mul(topY, new(quot[i - t - 1])), tempX) == 1 do
            step = step + 1
            quot[i - t - 1] = quot[i - t - 1] - 1
        end

        --Step 3.3
        tempY = copy(scaledY)
        shift_base(tempY, i - t - 1)
        scaledX = sub(scaledX, mul(tempY, new(quot[i - t - 1])))

        --Step 3.4
        if compare(scaledX, ZERO) == -1 then
            scaledX = add(scaledX, tempY)
            quot[i - t - 1] = quot[i - t - 1] - 1
        end
    end

    if lambda > 0 then
        right_shift(scaledX, lambda)
    end

    removeZeroes(quot)
    removeZeroes(scaledX)

    return quot, scaledX
end

function pow(x, y)
    if x == nil or y == nil then
        error("bigInt pow: missing parameter")
    elseif x.isBig ~= true or y.isBig ~= true then
        error("bigInt pow: invalid parameter")
    elseif compareAbs(y, ZERO) == -1 then
        error("bigInt pow: negative exponent not allowed")
    elseif compareAbs(y, ZERO) == 0 then
        return new(1)
    elseif compareAbs(y, ONE) == 0 then
        return new(x)
    end
    local n = copy(y)
    local z = copy(x)
    local w = new(1)
    while true do
        if n[0] % 2 == 0 then
            right_shift(n, 1)
        else
            right_shift(n, 1, true)
            w = mul(z, w)
            if compareAbs(n, ZERO) == 0 then
                return w
            end
        end
        z = square(z)
    end
end

--===== OTHER ARITHMETIC METHODS =====--
function abs(x)
    local bNum1 = new(x)
    bNum1.sign = false
    return bNum1
end

function square(x)
    if x == nil then
        error("bigInt square: missing parameter")
    elseif type(x) ~= "table" or not x.isBig then
        error("bigInt square: invalid parameter")
    end

    local ans = alloc(#x*2 + 1)
    local carry = 0
    local temp = 0
    for i = 0, #x do
        temp = ans[2*i] + x[i]*x[i]
        ans[2*i] = temp % BASE
        carry = math.floor(temp/BASE)
        for j = i + 1, #x do
            temp = ans[i + j] + 2*x[j]*x[i] + carry
            ans[i + j] = temp % BASE
            carry = math.floor(temp/BASE)
        end
        ans[i + #x + 1] = carry
    end
    removeZeroes(ans)
    return ans
end

function gcd(x, y)
    if x == nil or y == nil then
        error("bigInt gcd: missing parameter")
    elseif type(x) ~= "table" or x.isBig ~= true or type(y) ~= "table" or y.isBig ~= true then
        error("bigInt gcd: invalid parameter")
    elseif compareAbs(x, y) == -1 then
        return gcd(y, x)
    end

    local g = new(1)
    local tempX = copy(x)
    local tempY = copy(y)

    while tempX[0] % 2 == 0 and tempY[0] % 2 == 0 do
        right_shift(tempX, 1)
        right_shift(tempY, 1)
        left_shift(g, 1)
    end

    while compareAbs(tempX, ZERO) ~= 0 do
        while tempX[0] % 2 == 0 do
            right_shift(tempX, 1)
        end
        while tempY[0] % 2 == 0 do
            right_shift(tempY, 1)
        end
        local t = sub(tempX, tempY)
        t.sign = false
        right_shift(t, 1)
        if compare(tempX, tempY) == -1 then
            tempY = t
        else
            tempX = t
        end
    end

    return mul(g, tempY)
end

function egcd(x, y)
    if x == nil or y == nil then
        error("bigInt egcd: missing parameter")
    elseif type(x) ~= "table" or x.isBig ~= true or type(y) ~= "table" or y.isBig ~= true then
        error("bigInt egcd: invalid parameter")
    end

    local g = new(1)
    local tempX = copy(x)
    local tempY = copy(y)
    tempX.sign = false
    tempY.sign = false

    while tempX[0] % 2 == 0 and tempY[0] % 2 == 0 do
        right_shift(tempX, 1)
        right_shift(tempY, 1)
        left_shift(g, 1)
    end

    local u = copy(tempX)
    local v = copy(tempY)
    local A = new(1)
    local B = new()
    local C = new()
    local D = new(1)
    repeat
        while u[0] % 2 == 0 do
            right_shift(u, 1)
            if A[0] % 2 ~= 0 or B[0] % 2 ~= 0 then
                A = add(A, tempY)
                B = sub(B, tempX)
            end
            right_shift(A, 1, true)
            right_shift(B, 1, true)
        end
        while v[0] % 2 == 0 do
            right_shift(v, 1)
            if C[0] % 2 ~= 0 or D[0] % 2 ~= 0 then
                C = add(C, tempY)
                D = sub(D, tempX)
            end
            right_shift(C, 1, true)
            right_shift(D, 1, true)
        end
        if compare(u, v) ~= -1 then
            u = sub(u, v)
            A = sub(A, C)
            B = sub(B, D)
        else
            v = sub(v, u)
            C = sub(C, A)
            D = sub(D, B)
        end
    until compareAbs(u, ZERO) == 0
    return C, D, mul(g, v)
end

function powMod(x, y, m)
    local n = copy(y)
    local z = copy(x)
    local w = new(1)
    while true do
        if n[0] % 2 == 0 then
            right_shift(n, 1)
        else
            right_shift(n, 1, true)
            w = mul(z, w) % m
            if compareAbs(n, ZERO) == 0 then
                return w
            end
        end
        z = square(z) % m
    end
end

--===== BITWISE METHODS =====--
function left_shift(x, n)
    if x == nil then
        error("bigInt left_shift: parameter missing")
    elseif type(x) == "table" and x.isBig == true then
        for i = 1, n do
            local carry = 0
            local temp = 0
            for i = 0, #x do
                temp = x[i]*littleBASE
                x[i] = (temp % BASE) + carry
                carry = math.floor(temp/BASE)
            end
            if carry > 0 then
                table.insert(x, carry)
            end
        end
    else
        error("bigInt left_shift: invalid parameter")
    end
end

function right_shift(x, n, noWarn)
    if x == nil then
        error("bigInt right_shift: parameter missing")
    elseif type(x) == "table" and x.isBig == true then
        for j = 1, n do
            local carry = 0
            local temp = 0
            for i = #x, 0, -1 do
                temp = x[i]
                x[i] = math.floor(temp/littleBASE) + (carry*BASE)/littleBASE
                carry = temp % littleBASE
            end
            if carry > 0 and noWarn ~= true then
                error("bigInt right_shift: carry left over", 2)
            end
        end
        removeZeroes(x)
    else
        error("bigInt right_shift: invalid parameter")
    end
end

function shift_base(x, n)
    if x == nil then
        error("bigInt shift_base: parameter missing")
    elseif type(x) == "table" and x.isBig == true then
        if n > 0 then
            for i = #x + n, 0, -1 do
                x[i] = x[i - n] or 0
            end
        elseif n < 0 then
            for i = 0, #x do
                x[i] = x[i - n] or 0
            end
        end
        removeZeroes(x)
    else
        error("bigInt shift_base: invalid parameter")
    end
end

--===== RELATIONAL METHODS =====--
function compareAbs(x, y)
    if x == nil or y == nil then
        error("bigInt compareAbs: missing parameter")
    elseif type(x) == "table" and x.isBig == true and type(y) == "table" and y.isBig == true then
        if #x > #y then
            return 1
        elseif #x < #y then
            return -1
        else
            for i = #x, 0, -1 do
                if x[i] > y[i] then
                    return 1
                elseif x[i] < y[i] then
                    return -1
                end
            end
        end
        return 0
    else
        error("bigInt compareAbs: invalid parameter")
    end
end

function compare(x, y)
    if x == nil or y == nil then
        error("bigInt compare: missing parameter")
    elseif type(x) == "table" and x.isBig == true and type(y) == "table" and y.isBig == true then
        if not x.sign and y.sign then
            return 1
        elseif x.sign and not y.sign then
            return -1
        elseif x.sign and y.sign then
            return -compareAbs(x, y)
        else
            return compareAbs(x, y)
        end
    else
        error("bigInt compare: invalid parameter")
    end
end

--===== MISC METHODS =====--
function tostring(bNum)
    if type(bNum) == "table" and bNum.isBig then
        if compareAbs(bNum, ZERO) == 0 then
            return "0"
        end
        local temp = ""
        local tempN = copy(bNum)
        local tempM
        local modulus = new(10^(BASE_LEN - 1))
        while compareAbs(tempN, ZERO) ~= 0 do
            os.queueEvent("bigInt_yield")
            os.pullEvent()
            tempN, tempM = div(tempN, modulus)
            if tempM[0] then
                local a = tempM[0]
                local temp1 = ""
                if string.len(a) < BASE_LEN - 1 then
                    temp1 = string.rep("0", BASE_LEN - 1 - string.len(a))
                end
                local temp2 = a
                temp = temp1..temp2..temp
            else
                temp = string.rep("0", BASE_LEN - 1)..temp
            end
        end
        while string.sub(temp, 1, 1) == "0" do
            temp = string.sub(temp, 2)
        end
        if bNum.sign then
            temp = "-"..temp
        end
        return temp
    end
end

function removeZeroes(bNum)
    if bNum == nil then
        error("bigInt removeZeroes: missing parameter")
    elseif type(bNum) == "table" and bNum.isBig == true then
        for i = #bNum, 1, -1 do
            if bNum[i] == 0 then
                bNum[i] = nil
            else
                break
            end
        end
    else
        error("bigInt removeZeroes: invalid parameter")
    end
end

function change(x, y)
    if x == nil or y == nil then
        error("bigInt change: missing parameter", 3)
    elseif type(x) == "table" and x.isBig == true and type(y) == "table" and y.isBig == true then
        for i = 0, #y do
            x[i] = y[i]
        end
        for i = #y + 1, #x do
            x[i] = nil
        end
        x.sign = y.sign
    else
        error("bigInt change: invalid parameter", 3)
    end
end

function copy(x)
    local temp = new()
    change(temp, x)
    return temp
end

function alloc(n)
    local temp = new()
    for i = 0, n do
        temp[i] = 0
    end
    return temp
end

function serialise(a)
    local out = ""
    for i = 0, #a do
        out = out..":"..a[i]
    end
    if a.sign then
        out = "-"..out
    end
    return out
end

function unserialise(a)
    local out = new()
    if string.sub(a, 1, 1) == "-" then
        out.sign = true
    end

    local size = 0
    local word, seek = string.match(a, ":([^:]+)()", 1)
    while word do
        out[size] = tonumber(word)
        size = size + 1
        word, seek = string.match(a, ":([^:]+)()", seek)
    end

    return out
end

--===== PRIME NUMBER GENERATION =====--
function randKBitInt(k)
    local fullWords = math.floor(k/base_exponent)
    local lastWord = k % base_exponent
    local ans = alloc(fullWords)
    for i = 0, fullWords - 1 do
        ans[i] = math.random(0, BASE - 1)
    end
    ans[#ans] = math.random(math.floor(2^(lastWord - 1)), math.max(0, 2^lastWord - 1))
    return ans
end

function millerRabin(n, t)
    local r = n - 1
    local s = 0
    while r[0] % 2 == 0 do
        right_shift(r, 1)
        s = s + 1
    end
    local nMinusOne = n - 1
    local isFirstPass = true
    for i = 1, t do
        os.queueEvent("bigInt_yield")
        os.pullEvent()
        local a
        if isFirstPass then
            a = new(2)
            isFirstPass = false
        else
            repeat
                a = copy(n) - 2
                right_shift(a, 1, true)
                a = a + math.random(-1000, 1000)
            until TWO <= a and a <= n - 2
        end
        local y = powMod(a, r, n)
        if y ~= ONE and y ~= nMinusOne then
            local j = 1
            while j <= s - 1 and y ~= nMinusOne do
                os.queueEvent("bigInt_yield")
                os.pullEvent()
                y = square(y) % n
                if y == ONE then
                    return false
                end
                j = j + 1
            end
            if y ~= nMinusOne then
                return false
            end
        end
    end
    return true
end

local rounds = {
    {150, 18},
    {200, 15},
    {250, 12},
    {300, 9},
    {350, 8},
    {400, 7},
    {450, 6},
    {550, 5},
    {650, 4},
    {850, 3},
    {1300, 2},
}

function kBitPrime(bitLength)
    local millerRabinRounds = 27
    for i = 1, #rounds do
        if bitLength < rounds[i][1] then
            break
        else
            millerRabinRounds = rounds[i][2]
        end
    end
    local isPrime, number = false, nil
    repeat
        number = randKBitInt(bitLength)
        if number[0] == 0 then
            number[0] = 1
        elseif number[0] % 2 == 0 then
            number[0] = number[0] - 1
        end
        isPrime = millerRabin(number, millerRabinRounds)
    until isPrime
    return number
end

--===== METATABLES =====--
local bigIntMethods = {
    abs = abs,
    gcd = gcd,
    egcd = egcd,
    powMod = powMod,
    left_shift = left_shift,
    right_shift = right_shift,
    shift_base = shift_base,
    copy = copy,
    serialise = serialise,
}
local bigIntMetatable = {
    __index = bigIntMethods,

    __add = function(x, y)
        return add(new(x), new(y))
    end,
    __sub = function(x, y)
        return sub(new(x), new(y))
    end,
    __mul = function(x, y)
        return mul(new(x), new(y))
    end,
    __div = function(x, y)
        local quot = div(new(x), new(y))
        return quot
    end,
    __mod = function(x, y)
        local _, rem = div(new(x), new(y))
        return rem
    end,
    __pow = function(x, y)
        return pow(new(x), new(y))
    end,
    __unm = function(x)
        local y = new(x)
        y.sign = not y.sign
        return y
    end,

    __eq = function(x, y)
        return compare(new(x), new(y)) == 0
    end,
    __lt = function(x, y)
        return compare(new(x), new(y)) == -1
    end,
    __le = function(x, y)
        return compare(new(x), new(y)) < 1
    end,

    __tostring = tostring,
}

function new(num)
    local bNum = {}
    setmetatable(bNum, bigIntMetatable)
    if num == nil then
        bNum[0] = 0
        bNum.sign = false
    elseif type(num) == "table" then
        if num.isBig == true then
            return copy(num)
        end
    elseif type(num) == "number" and math.abs(num) ~= math.huge then
        if num < 0 then
            bNum.sign = true
        else
            bNum.sign = false
        end
        local temp = math.abs(num)
        if temp == 0 then
            bNum[0] = 0
        else
            local i = 0
            while temp > 0 do
                bNum[i] = temp % BASE
                i = i + 1
                temp = math.floor(temp/BASE)
            end
        end
    else
        error("bigInt new: invalid parameter")
    end
    bNum.isBig = true
    return bNum
end

ZERO, ONE, TWO = new(0), new(1), new(2)