# GSoC 2019 - Week 11

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))
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)

# 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!!