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, 2016 at 3:40
  • 1
    $\begingroup$ Meysam, if you have some numerical results, it is better to add them here for visualization. $\endgroup$
    – Shahrooz
    Apr 7, 2016 at 11:37

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.