JMIG5776 Fitness Freak

GSoC 2019 - Week 11

11 Aug 2019

This was the eleventh week meeting with the GSoC mentors which was scheduled on Sunday 11th August, 2019 between 11:30 - 12:30 PM (IST). Me, Yathartha and Amit were the attendees of the meeting. _solve_modular was discussed in this meeting.

Here is all the brief description about new solver _solve_modular for solving modular equations.

What type of equations to be considered and what domain?

A - Mod(B, C) = 0

    A -> This can or cannot be a function specifically(Linear, nth degree single
         Pow, a**f_x and Add and Mul) of symbol.(But currently its not a
        function of x)
    B -> This is surely a function of symbol.
    C -> It is an integer.
And domain should be a subset of S.Integers.

Filtering out equations

A check is being applied named _is_modular which verifies that only above mentioned type equation should return True.

Working of _solve_modular

In the starting of it there is a check if domain is a subset of Integers.

domain.is_subset(S.Integers)

Only domain of integers and it subset are being considered while solving these equations. Now after this it separates out a modterm and the rest term on either sides by this code.

modterm = list(f.atoms(Mod))[0]
rhs = -(S.One)*(f.subs(modterm, S.Zero))
if f.as_coefficients_dict()[modterm].is_negative:
    # f.as_coefficient(modterm) was returning None don't know why
    # checks if coefficient of modterm is negative in main equation.
    rhs *= -(S.One)

Now the equation is being inverted with the helper routine _invert_modular like this.

n = Dummy('n', integer=True)
f_x, g_n = _invert_modular(modterm, rhs, n, symbol)

I am defining n in _solve_modular because _invert_modular contains recursive calls to itself so if define the n there then it was going to have many instances which of no use. Thats y I am defining it in _solve_modular.

Now after the equation is inverted now solution finding takes place.

if f_x is modterm and g_n is rhs:
        return unsolved_result

First of all if _invert_modular fails to invert then a ConditionSet is being returned.

    if f_x is symbol:
        if domain is not S.Integers:
            return domain.intersect(g_n)
        return g_n

And if _invert_modular is fully able to invert the equation then only domain intersection needs to takes place. _invert_modular inverts the equation considering S.Integers as its default domain.

    if isinstance(g_n, ImageSet):
        lamda_expr = g_n.lamda.expr
        lamda_vars = g_n.lamda.variables
        base_set = g_n.base_set
        sol_set = _solveset(f_x - lamda_expr, symbol, S.Integers)
        if isinstance(sol_set, FiniteSet):
            tmp_sol = EmptySet()
            for sol in sol_set:
                tmp_sol += ImageSet(Lambda(lamda_vars, sol), base_set)
            sol_set = tmp_sol
        return domain.intersect(sol_set)

In this case when g_n is an ImageSet of n and f_x is not symbol so the equation is being solved by calling _solveset (this will not lead to recursion because equation to be entered is free from Mod) and then the domain intersection takes place.

What does _invert_modular do?

This function helps to convert the equation A - Mod(B, C) = 0 to a form (f_x, g_n). First of all it checks the possible instances of invertible cases if not then it returns the equation as it is.

a, m = modterm.args
if not isinstance(a, (Dummy, Symbol, Add, Mul, Pow)):
        return modterm, rhs

Now here is the check for complex arguments and returns the equation as it is if somewhere it finds I.

if rhs.is_real is False or any(term.is_real is False \
            for term in list(_term_factors(a))):
        # Check for complex arguments
        return modterm, rhs

Now after this we check of emptyset as a solution by checking range of both sides of equation. As modterm can have values between [0, m - 1] and if rhs is out of this range then emptySet is being returned.

if (abs(rhs) - abs(m)).is_positive or (abs(rhs) - abs(m)) is S.Zero:
        # if rhs has value greater than value of m.
        return symbol, EmptySet()

Now the equation haveing these types are being returned as the following

if a is symbol:
        return symbol, ImageSet(Lambda(n, m*n + rhs), S.Integers)

    if a.is_Add:
        # g + h = a
        g, h = a.as_independent(symbol)
        if g is not S.Zero:
            return _invert_modular(Mod(h, m), (rhs - Mod(g, m)) % m, n, symbol)

    if a.is_Mul:
        # g*h = a
        g, h = a.as_independent(symbol)
        if g is not S.One:
            return _invert_modular(Mod(h, m), (rhs*invert(g, m)) % m, n, symbol)

The more peculiar case is of a.is_Pow which is handled as following.

if a.is_Pow:
        # base**expo = a
        base, expo = a.args
        if expo.has(symbol) and not base.has(symbol):
            # remainder -> solution independent of n of equation.
            # m, rhs are made coprime by dividing igcd(m, rhs)
            try:
                remainder = discrete_log(m / igcd(m, rhs), rhs, a.base)
            except ValueError: # log does not exist
                return modterm, rhs
            # period -> coefficient of n in the solution and also referred as
            # the least period of expo in which it is repeats itself.
            # (a**(totient(m)) - 1) divides m. Here is link of theoram:
            # (https://en.wikipedia.org/wiki/Euler's_theorem)
            period = totient(m)
            for p in divisors(period):
                # there might a lesser period exist than totient(m).
                if pow(a.base, p, m / igcd(m, a.base)) == 1:
                    period = p
                    break
            return expo, ImageSet(Lambda(n, period*n + remainder), S.Naturals0)
        elif base.has(symbol) and not expo.has(symbol):
            remainder_list = nthroot_mod(rhs, expo, m, all_roots=True)
            if remainder_list is None:
                return symbol, EmptySet()
            g_n = EmptySet()
            for rem in remainder_list:
                g_n += ImageSet(Lambda(n, m*n + rem), S.Integers)
            return base, g_n

Two cases are being created based of a.is_Pow

  1. x**a
  2. a**x

x**a - It is being handled by the helper function nthroot_mod which returns required solution. I am not going into very mch detail for more information you can read the documentation of nthroot_mod.

a**x - For this totient is being used in the picture whose meaning can be find on this Wikipedia page. And then its divisors are being checked to find the least period of solutions.

Hope I am able to clear out everything!!

Code improvement takes time!!

Follow @jmig5776

Related Posts