# GSoC 2019 - Week 11

11 Aug 2019This 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

- x**a
- 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