# Find the modulo of large number

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)$ ?

• 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. – user451844 Aug 18 '17 at 21:13
• 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.\ \$ – Bill Dubuque Aug 18 '17 at 21:17
• You can reduce the factors modulo $y$ before you start and reduce sub-products modulo $y$ as you go along. – Mark Bennet Aug 18 '17 at 21:20
• @mark Already said above. – Bill Dubuque Aug 18 '17 at 21:21
• 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. – mdave16 Aug 18 '17 at 22:51

## 1 Answer

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