>>253
多倍長がどれほど多倍長かというのにもよりますが、とにかく速いQ1の回答はカラツバ法とか整数環上でFFTして畳み込みだと思います
Q3はそもそも多倍長整数をどう持つかによるので、仕様を確定しないと難しいんじゃないでしょうか