1
$\begingroup$

I need to find the value of y%mod where mod is a prime number and y is defined below

$y = a_1\cdot a_2 \cdot a_3 \cdot a_4\cdots a_n$

I know the value of $t = \log a_1 +\log a_2+\cdots+\log a_n$.

How to find the exact value of y%mod since y can be very large so i can't simple used $(Math.E^t)$ ?

$\endgroup$
  • 1
    $\begingroup$ you could try doing the mod for all it's factors one at a time if you hit even one that is 0 remainder you know the whole product is. $\endgroup$ – user451844 Aug 18 '17 at 21:13
  • 1
    $\begingroup$ Without any further special properties the best you can do is recursively compute the product of the reduced arguments, e.g. $\ y_1 := \overline{a_1},\,\ y_{k+1} := \overline{(\overline{a_{k+1}}\,{y_k})}\ $ where $\,\overline{x} := x\bmod p.\ \ $ $\endgroup$ – Bill Dubuque Aug 18 '17 at 21:17
  • $\begingroup$ You can reduce the factors modulo $y$ before you start and reduce sub-products modulo $y$ as you go along. $\endgroup$ – Mark Bennet Aug 18 '17 at 21:20
  • $\begingroup$ @mark Already said above. $\endgroup$ – Bill Dubuque Aug 18 '17 at 21:21
  • 1
    $\begingroup$ do you know the values of the $a_i$? the help in the comments would only work if you did, and you haven't explicitly stated you do. $\endgroup$ – mdave16 Aug 18 '17 at 22:51
1
$\begingroup$

Hint: $y \equiv k_1 \cdot k_2\cdots k_n \mod{p}$, where $a_i \equiv k_i \mod{p}$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.