### oursaco's blog

By oursaco, history, 2 years ago,

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.

• +27

 » 2 years ago, # | ← Rev. 2 →   +24 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.
•  » » 2 years ago, # ^ |   +3 Thanks!
•  » » 2 years ago, # ^ |   0 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).
•  » » » 2 years ago, # ^ |   0
•  » » » 2 years ago, # ^ |   0 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.
•  » » » » 2 years ago, # ^ |   0 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?
•  » » » » » 2 years ago, # ^ |   +3 https://codeforces.com/contest/1656/problem/H In this problem, even inputting the numbers would cause ll overflow.
•  » » » » 2 years ago, # ^ |   +13 In C++ you can use __int128. Also isn't bigint in python incredibly slow and you would better not use it in ntt?
•  » » » » » 2 years ago, # ^ |   0 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.
•  » » » » » » 2 years ago, # ^ | ← Rev. 3 →   +5 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