Modular Equation Solver in Solveset

Ishan Joshi edited this page Mar 14, 2018 · 1 revision

Understanding Modular equations

Modular equations deals with the Modular arithmetic and the Modulo operation.

  • a mod n refers to the remainder when a is divided by n
    From the Euclid's division Lemma, we know that,
    a = q * n + r
  • Modulo equivalence : a ~ b mod n , iff n divides (a - b)
    We will say that a and b are equivalent modulo, where ~ is the congruence modulo operator

An important thing to be noted is that modular equations deals with integer solutions

More about congruence can be found out here.
The application of modular equations can seen in the generation of random numbers with Linear congruential generator as explained here

The Basic Idea

There are a bunch of equations involving the modular arithmetic which solveset currently is not able to solve. Issue #13178 relates to the same. Fixing this would make solveset a versatile solver. The basic idea to be used here is solving such equations by gradually inverting it.
The current invert() would fail to do so because :

  • It does not incorporate the "wrap around" technique, where an integer upon reaching a certain value repeats itself.
  • Multiplication and division operations are different from those of the conventional arithmetic. Here the logic multiplicative inverse has to be used.
  • Exponential equations cannot be solved by the general log method, rather a different method involving discrete_log has to be used.

So here comes a need of a different invert() which would solve these types of equations with a different logic, but the same technique. This has to be done by implementing the invert_modular() which would add-on solveset's ability to solve Modular equations

This would require two things:
1. Identification of Modular equations
2. Solving via inversion

Clone this wiki locally
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.
Press h to open a hovercard with more details.