ADIC

GF(p^1000) とかを作りたい気がするけど、遅い。そこで高速化テクです そもそもp-adic numberを使えばいい気がする まず、コンストラクタには生成多項式を与えたほうが早くなります 自分で作ってもsageに作らせても変わらない気がするけどなぜか早くなる def gen_gfpm(p, m, name="a"): PR = PolynomialRing(GF(p), name=name) f = PR.irreducible_element(m) return GF(p^m, modulus=f, name=name) sageの GF の内部実装は↓なんだけど、 に対する isP…

この記事は統治行為論アドベントカレンダー 6日目の記事です．adventar.orgこんにちは！ Cuです． みなさんは層をご存じですか？ もちろんご存じですね！ それでは偏屈層はご存じでしょうか？ こちらは知らないよ～という人も多いかもしれません！ この記事では偏屈層の勉強方法を紹介していきます！ 定義 層 位相空間 *1 上の前層 というのは，各開集合 に対して 上ベクトル空間*2 を対応させ，さらに に対して が良い感じの条件 に対し となる． を満たすように定義されたものでした．ここで に対して を と表します．これに加えて に対して が，任意の に対して であれば が成立する．（局所…

#corctf2021 from Crypto.Util.number import getPrime, long_to_bytes from pwn import * import random, binascii flag = open('flag.txt').read() def v(p, k): ans = 0 while k % p == 0: k /= p ans += 1 return ans p, q, r = getPrime(2048), getPrime(2048), getPrime(2048) print(p, q, r) n = pow(p, q) * r a1 =…

p-adic number関連の用語 数のにおけるp進付値 というのはを素因数分解したときのにおけるの値 要するにに含まれるの個数 性質 Lifting The Exponent Lemma LTE Lemma が成立する

#m0lecon2021 #good_challenges_2021 https://keltecc.github.io/ctf/writeup/2021/05/15/m0lecon-ctf-2021-teaser-giant-log.html import random from secret import flag, fast_exp import signal p = 0x83f39daf527c6cf6360999dc47c4f0944ca1a67858a11bd915ee337f8897f36eff98355d7c35c2accdf4555b03a9552b4bf400915320c…

どうも、わーはやです。今回は自分のテンプレのコードを解説していきたいと思います。 と言っても、普段あまり使わないやつはリファレンスだけ置いて軽く流します。 長くなりそうなので前半と後半に分けようと思います。 前置きはこのあたりにして早速解説していきます。 コンパイルオプション 最初の方 マクロ シリーズ 入出力 便利なやつまとめ 終わりに コンパイルオプション /*#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops")//*/ //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,p…

クイズです。$p/q \equiv 714236805 \pmod{998244353}$ を満たす互いに素な整数のペア $(p, q)$ はなんでしょうか。 答えは $(113, 355)$ です*1。今日の話は、これを一般的に求める方法です。 裏話 $1/3 \equiv 332748118$ みたいなのだとパターンマッチで答えられてしまいそうな気がしたので、適当に難しそうな分数が欲しくなりました。 適当な分数と言えば、$1/\pi \approx 113/355$ だな〜と思って求めてみたところ、$876543210$ のアナグラムになっていてびっくりしました。 （追記）ねむかったので …