0
$\begingroup$

Suppose that i need to compute product $~\phi(1) \dots \phi(n)~$ modulo prime $500009$ as fast as possible. Memory limitations are rather tough: $64$ mb so i can't just keep all the values of totient function. $n$ can be as large as $10^9$ and time given is $2$ s.

My main idea is to somehow estimate the prime factors and their exponents in factorization of this product. And then apply fast modular exponentiation. But i don't understand yet how to do such estimation.

Any ideas are highly appreciated. Thanks in advance.

P.S. This is not a hometask or a problem from a current contest. I'm just surfing number theory problem bank and solving them for fun.

$\endgroup$

1 Answer 1

0
$\begingroup$

Let $p=500009$ and $m=12p+1$. One possibility is to use the fact that $\phi(m) \equiv 0 \pmod{p}$, and hence it's enough to pre-calculate all values up to $m$. Storing each answer in a 32-bit integer, this is a table of size 24MB.

If you don't like pre-calculating everything, you can use in some other way the fact that only numbers below $m$ need to be considered. Be creative.

$\endgroup$
2
  • $\begingroup$ I was trying to deduce some limit after which the product is zero modulo $p$ but didn't succeed. How did you deduce such $m$? Am i right that you were looking for the first prime of the form $kp + 1$? $\endgroup$
    – Igor
    Mar 20, 2016 at 20:55
  • $\begingroup$ That's exactly right. $\endgroup$ Mar 20, 2016 at 20:55

Your Answer

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

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