フェルマーの小定理

概要 暗号化と復号 原理の証明 オイラーのφ関数 フェルマーの小定理 証明 まとめ 概要 RSA暗号は現在普及している公開鍵暗号の基礎となる暗号技術である。説明しているサイトは色々あるが、他人が書いたものなので読みにくかった。私にとって分かりやすいように書く。Wikipediaの同項目を参考にした。 証明中で用いたオイラーのφ関数とフェルマーの小定理については後半で解説した。 暗号化と復号 0以上n未満の整数の集合をとおく。 異なる２つの素数 をとり、 を定義する。 と互いに素であるような（公開鍵）を任意に設定する。 このとき、秘密鍵は \begin{align} d \equiv e^{-1…

昨日のABC F問題のように、既約分数（有理数）を「(mod 素数) における逆元を用いて整数として表現する」ことが問われる場合があります。 atcoder.jp この記事では 分数をなぜ整数として表現できるのか どうやってその値を算出するのか という辺りを丁寧にまとめてみます。 逆数と逆元（数学的に丁寧な話） この項目は数学的に込み入った話になるので、プログラミング的な話に注目する人は飛ばしても良いです。 まず、分数とは何かをあらためて考えてみます。， について、 です。言い換えれば、分数（＝除算）は割る数 の逆数 を掛ける操作（＝乗算）です。 では、逆数とは何でしょう。 の逆数を と表現す…

素数に関するオイラーの定理ここでは，(フェルマーの) 2平方定理の証明で用いる素数に関するオイラーの定理の証明をします． 2平方定理奇素数(奇数かつ素数，すなわち 3 以上の素数) が 4 で割ると 1 余るとき， は 2 つの平方数の和として表される．2平方定理については，詳しくは上のリンク先に記事がありますので，そちらをどうぞ． 以下が素数に関するオイラーの定理です．オイラーの名前が残っている数多くの定理のうちの一つです． 定理．奇素数 について，\begin{align*} p\equiv 1 \pmod{4} \end{align*}と\begin{align*} x^2\equiv …

フェルマーの小定理(Fermat's little theorem)フェルマーといえば, 360年間もの間証明されなかったことで有名な「フェルマーの最終定理」があります. まず, フェルマーの小定理の内容を紹介します.素数 と自然数 が互いに素であるとき,\begin{align*} a^{p-1}\equiv 1 \pmod{p} \end{align*}が成り立つ.つまり, を で割ると1余る, という意味です. (合同式についてはこちら). 証明ここでは証明を3通り挙げておきます. 1つ目, 2つ目の方が分かりやすいですが, 3つ目の方法はこの定理の一般化であるオイラーの定理の証明に応用…

3完。一生青パフォしか取れない。つまんなすぎる。 A - Chocolate 「ルジンの問題」（名前は知らなかったので今ググった）みたいなやばいのも存在するので怖い。ただ2冪ということでそんなに変なことは起こらなそうでもある。とりあえずサイズ毎にカウントしておく。左上から貪欲に取っていくというのはどうか。しかし貪欲といっても右に行くか下に行くかがあるし、小さいのを取ったら長方形がどんどん増える。1個チョコを取って3個の長方形に分割されたとして、長方形をまたぐような取り方が必要になることはおそらくないと思うが。AとBを交互に考えて途中から順位表も見ながら。全く解ける気がしない。横だけ見て、4+4…

こんにちは。リユナと申します。競プロでは考えより数学問題が結構出ますよ。今日はこれらをどう接近して解くのか、これらをためにどう勉強したらいいのかについて話そうとします！ 0.初めに 1.めっちゃ数学の問題を解くためには？ 2.数学問題ではなくても、数学的な考え方は役に立つ 3.終えて 0.初めに

三原和人の漫画「はじめアルゴリズム(2016年~2019年)」 以下エロ注意… はじめアルゴリズム、面白そうだぞ！！https://t.co/grdOB8hB7f pic.twitter.com/Eskwy9Bxrj — みちばな (@mswar777) 2023年2月9日 『はじめアルゴリズム』Dr.Stoneやはたらく細胞など子供の頃読んでおきたかったと思える漫画は多数あるが、こちらも新たにそこに追加された数学漫画。数学＝勉強というより、数学ってこんなに面白いんだ！と読んでて新たな発見があった。 https://t.co/SzQLZFAyDg — Duffy (@rht1023) 2023…

問題 人の人が一列に並んでおり、人 は先頭から 番目に並んでいる。 以下の操作を人が1人になるまで行う。 先頭に並んでいる人を、確率 で列から取り除き、確率 で列の最後尾に移す。 人 について、人 が最後の1人になる確率を で求めよ。 補足 この問題では、求める確率が有理数であることが保証される。 また、確率を既約分数で と表したときに、 が で割り切れないことが保証される。 このときに、 が成立する整数 （ただし、 ）が一意に定まるので、これを求めよ。 入力 最初の1行に、整数 が与えられる。 条件 実行時間制限: 2s メモリ制限: 1024MB 解法 まず、分数を で表すために、フェルマ…

#CakeCTF2022 from Crypto.Util.number import getPrime import os flag = os.getenv("FLAG", "FakeCTF{warmup_a_frozen_cake}") m = int(flag.encode().hex(), 16) p = getPrime(512) q = getPrime(512) n = p*q print("n =", n) print("a =", pow(m, p, n)) print("b =", pow(m, q, n)) print("c =", pow(m, n, n)) RSAで、…

フェルマーの小定理

これの続き sugarknri.hatenablog.com何を埋めてないかぐっと睨まれると垢バレする気がするけど気にしないぜ301 Nimの必勝法を知っていますか？302 上からDFS303 BFSやるだけ D - Small Multiple 桁数を2倍にしたときどうなるかのチェックを挟むと早くなるらしい 値の分布がランダムならexpectedでO(√N)になるのはわかるが、実際のところはよくわからず304 前半：区間篩なりミラーラビン 後半：fib[n]はO(logn)で求まるが、fib[10^14],fib[10^14+1]さえ求めたらあとは愚直でもオーダーは同じ305 切れ目がどこに…

20239月4日～2023年9月10日に読んだ中で気になったニュースとメモ書き（TLSらじお*1第122回の原稿）です。全文を公開している投銭スタイルです。 [TELNET over SSL/TLS (TCP Port 992)] [Bulletproof TLS and PKI翻訳予定] [その他のニュース] ▼OpenSSHのデフォルトアルゴリズム変更 ▼BoringSSLのHandshake hints ▼セミナー・シンポジウム情報 ▼Certainly構築の裏側 ▼CTの歴史 ▼CAAレコードのチェック順序 ▼FastlyのTLS脆弱性 [暗認本：21 RSA暗号] [まとめ] *1:…

皆さん、こんにちは。 ここ１か月は本業の仕事が忙しく、また旅行に行ったりコロナに罹ったりと色々あって記事を上げられずにいました。というわけで、１か月ぶりの記事になります。 今回は「フェルマー素数」について取り上げます。

皆さん、こんにちは。 今回は、「マスターデーモン」と呼ばれる整数問題を紹介します。 マスターデーモンは、国際数学オリンピック（以下「数オリ」）で出題された上のような問題で、世界中の数学強者が挑む数オリの数ある過去問の中でも「シンプルかつ超難問」としてよく知られている問題です。 ちなみに、幾多もの大学入試を解いてきた私も、数オリの問題は全く歯が立たず、今回のマスターデーモンも自力では解けておりません。執筆にあたっては、以下のブログ記事を参考にさせて頂きました。討伐！マスターデーモン！！｜大島学習塾のホームページ (oshima-gakushujuku.com)

部長が書いてたので解法だけ VRC競プロ部でCTF出ようぜ！って話があったのでノリで無言で参加したWriteup