3
$\begingroup$

Let $p$ be a prime number, let $m$ be a fixed number (for example $2^{20}$), and $i=k^{-1}\cdot (j-t) \pmod{p}$ where $j \leq m$ and $m<k$.

In the general case we have $t=0$, and $k,j$ are variable and in special case $t$ and $k$ are fix and we know its values.

is there a way to find the minimum value of $i$?

Example: In special case, let $p=7$,$t=3$,$k=3$ and $m=2$.

if $j=1$ then $i=4$ and if $j=2$ then $i=2$. So minimum value of $i$ is $2$.

In general case we can search all possible cases for $k,j$ and then find the minimum value of $i$'s.

If $m$ be so large we cant search all possible $j$. So Im looking for general method to solve this problem without searching.

$\endgroup$
2
  • 2
    $\begingroup$ Do you really mean the general case to be $t = 0$, and the special case to be $t \ne 0$? (I guess you also mean to take remainders, rather than congruence classes, which aren't ordered.) $\endgroup$
    – LSpice
    Apr 7 '16 at 3:40
  • 1
    $\begingroup$ Meysam, if you have some numerical results, it is better to add them here for visualization. $\endgroup$
    – Shah Rooz
    Apr 7 '16 at 11:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.