oursaco's blog

Very Big Mod
By oursaco, history, 3 years ago, In English

I've been working on an NTT implementation, which needs a big modulo in the form of x*2^k + 1. Does anyone know any mods of this form around 1e25. I rly don't want to use Chinese remainder theorem T-T.

  • Vote: I like it
  • +27
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 2   Vote: I like it +24 Vote: I do not like it

I used a Python snippet to find these examples:

$$$542110 \cdot 2^{64} + 1 = 10000164429798685026549761$$$
$$$1192092895510222934 \cdot 2^{23} + 1 = 10000000000020220185935873$$$
$$$1192092895510222937 \cdot 2^{23} + 1 = 10000000000020220211101697$$$

And for fun, I have this one as well:

$$$10002400000000000000000001$$$

It's easy enough to find such examples with sympy.isprime.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thanks!

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is there any way to implement it in other programming languages? Problem setters say that they are not biased towards any languages (Like giving any constraint which a programming language cannot compile or handle).

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, there is a way.

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The main difficulty in this (at least in my opinion) is not testing primality, for which Miller-Rabin is very common, but the requirement of a BigInteger library.

      In Python and Java, BigIntegers are built in.

      In Rust, it's easy to find a package that gives BigInteger support to find these numbers on your own computer, but afaik you can't use it in a solution since I believe codeforces compiles rust with rustc and not cargo.

      In C++, you can probably find biginteger libraries, which shouldn't be too hard, though I don't know any.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        In your experience of competitive programming, have you encountered any problem (Particularly on Codeforces or Atcoder) which required primality testing with a very big Constraint like 2e18 or smth?

        → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        In C++ you can use __int128. Also isn't bigint in python incredibly slow and you would better not use it in ntt?

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          However in Miller-Rabin when testing the primality of some $$$n$$$, you need to multiply two numbers of size around $$$n$$$ (specifically, you need to repeatedly calculate $$$a^2 \bmod n$$$), and multiplying two numbers around $$$10^{25}$$$ gives you a result around $$$10^{50}$$$. C++'s $$$\scriptsize\texttt{__int128}$$$ can only store numbers up to $$$3.4 \times 10^{38}$$$, so this is not viable.

          Yes, Python is slow, I should have mentioned that above. I'm not sure how much it could be optimized with numpy (on online judges that have support, like Atcoder I believe).

          Here's a problem (not in a contest though) that required $$$\scriptsize\texttt{__int128}$$$ since the inputs went up to the max $$$\scriptsize\texttt{long long}$$$ capacity. I'll tag SilentVisitor since they asked about it too. However I haven't seen any problem with larger inputs than this.

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
            ← Rev. 3   Vote: I like it +5 Vote: I do not like it

            Well, you can multiply two numbers too big to fit in the type by some modulo same way you find a (power of a number) too big to fit in the type

            → Reply