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.

By Shayan

Before stream
16:07:16

# | User | Rating |
---|---|---|

1 | tourist | 3845 |

2 | jiangly | 3707 |

3 | Benq | 3630 |

4 | orzdevinwang | 3573 |

5 | Geothermal | 3569 |

5 | cnnfls_csy | 3569 |

7 | jqdai0815 | 3532 |

8 | ecnerwala | 3501 |

9 | gyh20 | 3447 |

10 | Rebelz | 3409 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 171 |

2 | adamant | 163 |

3 | awoo | 162 |

4 | nor | 153 |

5 | maroonrk | 152 |

6 | -is-this-fft- | 151 |

6 | TheScrasse | 151 |

8 | Petr | 145 |

9 | pajenegod | 144 |

10 | orz | 143 |

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.

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/22/2024 03:52:44 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

I used a Python snippet to find these examples:

And for fun, I have this one as well:

It's easy enough to find such examples with

`sympy.isprime`

.Thanks!

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).

Yes, there is a way.

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.

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?

https://codeforces.com/contest/1656/problem/H In this problem, even inputting the numbers would cause ll overflow.

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

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.

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