modMath.py

from math import floor
from math import gcd
from LoopChain import methodLoop
import Fraction as fr
import FactNum as fn


def modInverse(num: int, modulus: int):
    """
    Finds the inverse in mod n of a number.

    :param num: number to find the inverse of
    :param modulus: mod to find the inverse in
    :return: num^-1 (mod modulus); None if invalid input
    """
    if gcd(num, modulus) != 1 or num == 0 or modulus == 0:
        return None
    elif num == 1:
        return 1
    else:
        currMod = modulus
        currNum = num
        currRem = currMod % currNum
        equationList = [[currMod, currNum, floor(currMod / currNum), currRem]]
        while currRem != 1:
            currMod = currNum
            currNum = currRem
            currRem = currMod % currNum
            equationList += [[currMod, currNum, floor(currMod / currNum), currRem]]
        if len(equationList) > 1:
            currCoeff = fr.Fraction(1, equationList[-1][2])
            currCon = fr.Fraction(-equationList[-1][3], equationList[-1][2])
            # currVar = equationList[-1][0]
            for r in reversed(equationList[1:-1]):
                tempCoeff = currCoeff + r[2]
                tempCon = currCon
                # currVar = r[1]
                currCoeff = 1 / tempCoeff
                currCon = -tempCon / tempCoeff
            currCoeff += equationList[0][2]
            # currVar = equationList[0][1]
            return int(-currCoeff / currCon)
        else:
            return -floor(equationList[0][0] / equationList[0][1])


def loopModInverse(num: int, modulus: int):
    """
    Finds the inverse in mod n of a number using the digit loop method.

    :param num: number to find the inverse of
    :param modulus: mod to find the inverse in
    :return: num^-1 (mod modulus)
    """
    if gcd(num, modulus) != 1:
        return None
    elif num == 1:
        return 1
    else:
        digitList = methodLoop(num, lambda x: x * num % modulus)
        if 1 in digitList:
            return digitList[digitList.index(1) - 1]
        else:
            return None


def isPowerOf(num1: int, num2: int) -> bool:
    x = num1
    y = num2
    if x == 0 or y == 0 or x == 1 or y == 1:
        return False
    while x % y == 0:
        x = x / y
    return x == 1


def powerOf(num1: int, num2: int):
    x = num1
    y = num2
    ret = 0
    while x % y == 0:
        x = x / y
        ret += 1
    return ret


def totient(inputNum: int):
    """
    Finds the totient of a positive integer.

    :param inputNum: positive integer to find the totient of
    :return: totient of the positive integer; none if invalid input
    """
    if type(inputNum) is int or isinstance(inputNum, fn.FactNum):
        facNum = fn.FactNum(abs(inputNum))
        if facNum == 0:
            return 0
        elif facNum == 1:
            return 1
        else:
            tot = 1
            for p, n in facNum.factors.items():
                tot *= (p ** (n - 1)) * (p - 1)
            return tot
    else:
        return None


def simpleTotient(inputPrime: int, inputPower: int):
    return (inputPrime ** (inputPower - 1)) * (inputPrime - 1)


def reducedTotient(inputNum: int):
    """
    Finds the reduced totient of a positive integer.

    :param inputNum: positive integer to find the reduced totient of
    :return: reduced totient of the positive integer; none if invalid input
    """
    if type(inputNum) is int or isinstance(inputNum, fn.FactNum):
        facNum = fn.FactNum(abs(inputNum))
        if facNum == 0:
            return 0
        elif facNum == 1:
            return 1
        else:
            tot = 1
            totList = []
            for p, n in facNum.factors.items():
                if p == 2 and n > 2:
                    tot *= int((p ** (n - 1)) * (p - 1) * (1 / 2))
                    totList += [int((p ** (n - 1)) * (p - 1) * (1 / 2))]
                else:
                    tot *= ((p ** (n - 1)) * (p - 1))
                    totList += [((p ** (n - 1)) * (p - 1))]
            if len(totList) == 1:
                return tot
            totDen = totList[0]
            for i in range(1, len(totList)):
                totDen = gcd(totDen, totList[i])
            tot = int(tot / totDen)
            return tot
    else:
        return None


def chiRemTheSolveDict(modDict: dict) -> int:
    """
    Uses the chinese remainder theorem to find the solution to a set of congruencies. The congruencies must be in the
    form of a dict with the key being the modulus and the value being the remainder at that modulus.

    :param modDict: dict of the congruencies with key = modulus and value = x % modulus
    :return: solution to the set of congruencies
    """
    retValue = 0
    retMod = 1
    for modulus, value in modDict.items():
        # print("modulus: " + str(modulus) + " value: " + str(value))
        retMod *= modulus
        currM = 1
        for m2, v2 in modDict.items():
            if m2 != modulus:
                currM *= m2
        if value != 0:
            # print("value: " + str(value) + " currM: " + str(currM) + " modulus: " + str(modulus))
            retValue += value * currM * modInverse(currM, modulus)
    retValue = retValue % retMod
    return retValue


def loopModPow(base: int, exponent: int, modulus: int):
    if exponent == 0:
        return 1
    elif exponent > 0:
        redExp = exponent % reducedTotient(modulus)
        retVal = 1
        for i in range(redExp):
            retVal = (retVal * base) % modulus
        return retVal
    else:
        ibase = modInverse(base, modulus)
        if ibase is None:
            return None
        else:
            redExp = (-exponent) % reducedTotient(modulus)
            retVal = 1
            for i in range(redExp):
                retVal = (retVal * ibase) % modulus
            return retVal


def isPrimRoot(num: int, modulus: int) -> bool:
    if len(methodLoop(num, lambda x: x * num % modulus)) == modulus - 1:
        return True
    else:
        return False


def discLogBrute(num: int, base: int, modulus: int):
    """
    for an equation of the form b = a^x (mod p), where b = num, a = base, and p = modulus

    :param num:
    :param base:
    :param modulus:
    :return:
    """

    redBase = base % modulus
    redNum = num % modulus
    currBase = 1
    # print(reducedTotient(modulus))
    # print("redBase: " + str(redBase))
    # print("redNum: " + str(redNum))
    if redNum == 1:
        return 0
    elif isPowerOf(redNum, redBase):
        return powerOf(redNum, redBase)
    elif not isPrimRoot(redBase, modulus):
        return None
    for i in range(reducedTotient(modulus)):
        if currBase == redNum:
            return i
        else:
            currBase = (currBase * redBase) % modulus
            # print("currBase: " + str(currBase))
            # print("i: " + str(i))
    return None


def discLogComp(num: int, base: int, modulus: int, compBase: int, compPower: int):
    """
    for an equation of the form b = a^x (mod p), where b = num, a = base, and p = modulus

    :param num:
    :param base:
    :param modulus:
    :param compBase:
    :param compPower:
    :return:
    """
    xList = []
    for i in range(1, compPower + 1):
        currPow = 0
        for x in xList:
            currPow -= x
        # print("base: " + str(base) + " currPow: " + str(currPow) + " modulus: " + str(modulus))
        currNum = loopModPow(((num * loopModPow(base, currPow, modulus)) % modulus),
                             int((modulus - 1) / (compBase ** i)),
                             modulus)
        for j in range(compBase):
            currRes = loopModPow(base, int(j * (modulus - 1) / compBase), modulus)
            if currRes == currNum:
                xList += [j]
                break
    retVal = 0
    for i in range(len(xList)):
        retVal += xList[i] * (compBase ** i)
    return retVal


def discLog(num: int, base: int, modulus: int):
    redBase = base % modulus
    redNum = num % modulus
    if redNum == 1:
        return 0
    elif isPowerOf(redNum, redBase):
        return powerOf(redNum, redBase)
    if not isPrimRoot(redBase, modulus):
        return None
    factMod = fn.FactNum(modulus - 1)
    congDict = {}
    for p, n in factMod.factors.items():
        congDict[(p ** n)] = discLogComp(redNum, redBase, modulus, p, n)
    # print("dict: " + str(congDict))
    # print("for equation: " + str(num) + " = " + str(base) + "^x (mod " + str(modulus) + ")")
    retVal = chiRemTheSolveDict(congDict)
    if retVal == 0 and redBase != 1:
        return None
    else:
        return retVal


def loopSigPow(base: int, exponent: int, modulus: int):
    if exponent == 0:
        return 1
    elif exponent > 0:
        retVal = 1
        currPow = 1
        for i in range(exponent):
            currPow = (currPow * base) % modulus
            retVal += currPow
        return retVal % modulus
    else:
        return None


def loopSigPowLen(base: int, exponent: int, modulus: int, stopVal: int = 1):
    if exponent > 0:
        retVal = 1
        currPow = 1
        for i in range(exponent):
            currPow = (currPow * base) % modulus
            retVal += currPow
            retVal %= modulus
            if retVal == stopVal:
                return i+1
        return None
    else:
        return None