【2次合同方程式の解法②】

【2次合同方程式の解法②】

pを奇素数、aはpの倍数でないとする。

ax^2+bx+c≡0 (mod p)

❶a=1→x^2+bx+c≡0 (mod p)のとき

【Step1】1次の係数bが偶数b=2s

x^2+2sx+c≡0 (mod p)

x^2+2sx+s^2≡s^2-c

(x+s)^2≡s^2-c→[平方完成]

s^2-c≡t^2 (mod p)となるt

存在しないときは、解なし

【可解性】を参照

(x+s)^2≡t^2

x+s≡±t

x≡-s+t,-s-t (mod p)

【Step2】1次の係数 bが奇数

x^2+bx+c≡0

b+p, b-pは偶数→[1次の係数を偶数に]

x^2+(b+p)x+c≡0→【Step1】へ

❷a≠1→ax^2+bx+c≡0 (mod p)

【Step3】[a→1にする]

ay≡1 (mod p)→y≡k

akx^2+kbx+kc≡0

x^2+Bx+C≡0 (mod p)型

→【Step1】or【Step2】

【例】x^2-2x-9≡0 (mod 13)

x^2-2x+1≡10

(x-1)^2≡10

(x-1)^2≡10+13×2≡36≡6^2

x-1≡±6

x≡7, -5 (mod 13)

【例】x^2+3x+16≡0 (mod 13)

x^2-10x+16≡0

(x-5)^2≡9≡3^2

x-5≡±3

x≡8,2 (mod 13)

【例】2x^2+9x-10≡0 (mod 17)

2y≡1 (mod 17)→y≡9

18x^2+81x-90≡0

x^2+13x-5≡0

x^2-4x+4≡9

(x-2)^2≡3^2

x-2≡±3

x≡5,16 (mod 17)

【例】3x^2-5x+5≡0 (mod 11)

3y≡1 (mod 11)→y≡4

12x^2-20x+20≡0

x^2+2x-2≡0

x^2+2x+1≡3

(x+1)^2≡3+11×3≡36≡6^2

x+1≡±6

x≡5,4 (mod 11)

(2022/11/4)

【2次合同方程式の解法】

pを奇素数とする。

x^2≡q (mod p)を解く。

x^2≡q≡q+pk=m^2 (mod p)のとき

x≡±m (mod p)

kを見つければ解くことができる。

【解法】

q≡a (mod 3)

p≡b (mod 3) とする。

m^2≡a+bk (mod 3)

n^2≡0,1 (mod 3)より、

a+bk≡0,1

→bk≡-a,1-a→k≡s,t (mod 3)

q≡c (mod 8)

p≡d (mod 8)とする。

m^2≡c+dk (mod 8)

n^2≡0,1,4 (mod 8)より、

c+dk≡0,1,4

→dk≡-c,1-c,4-c→k≡u,v,w (mod 8)

k≡x (mod 3), k≡y (mod 8)

→k≡16x+9y (mod 24)

r[1]≡16s+9u,r[2]≡16s+9v, r[3]≡16s+9w

r[4]≡16t+9u, r[5]≡16t+9v, r[6]≡16t+9w

q+p×r[i]が平方数かどうか調べる。

n^2≡0,1,4,5,6,9 (mod 10)を活用

(一の位に着目する)

[2]4で割れる？→下2桁が4の倍数

[3]9で割れる？→各位の和が9の倍数

[5]25で割れる？→下2桁が00,25,50,75

q+p×r[i]=j^2

x≡±j≡j,p-j (mod p)

【例】x^2≡42 (mod 89)

❲42/89❳

42=2×3×7

❲42/89❳=❲2/89❳×❲3/89❳×❲7/89❳

=❲2/89❳×❲89/3❳×❲89/7❳

=❲2/89❳×❲1/3❳×❲5/7❳

=❲2/89❳×1×❲7/5❳

=❲2/89❳×❲2/5❳

=1×1=1

よって、解あり

42≡0 (mod 3)

89≡-1 (mod 3)

-k≡0,1→k≡0,2 (mod 3)

42≡2 (mod 8)

89≡1 (mod 8)

k≡-2,-1,2→k≡2,6,7 (mod 8)

k≡16x+9y (mod 24)

r[1]≡18

r[2]≡54≡6

r[3]≡63≡15

r[4]≡32+18≡8+18≡2

r[5]≡32+6≡8+6≡14

r[6]≡32+15≡8+15≡23

よって、r≡2,6,14,15,18,23 (mod 24)

42+89r

42+89×2=220=4×55

42+89×6=576=9×64=24^2

x^2≡42≡42+89×6=24^2

x≡±24≡24,65 (mod 89)

【例】x^2≡23 (mod 83)

【解】

23≡2 (mod 3)

83≡2 (mod 3)

2k≡-2,-1→k≡-4,-2→k≡1,2 (mod 3)

23≡-1 (mod 8)

83≡3 (mod 8)

3k≡1,2,5→k≡3,6,7 (mod 8)

k≡16x+9y (mod 24)

r[1]≡16+27≡19

r[2]≡16+54≡22

r[3]≡16+63≡7

r[4]≡32+27≡11

r[5]≡32+54≡14

r[6]≡32+63≡23

よって、

r≡7,11,14,19,22,23 (mod 24)

23+83r

23+83×7=604=4×151

23+83×11=936=9×104

23+83×14=1185

23+83×19=1600=40^2

よって、

x^2≡23≡23+83×19=1600=40^2

x≡±40≡40,43 (mod 83)

【例】x^2≡10 (mod 43)を解け。

【解】

10≡1 (mod 3)

43≡1 (mod 3)

k≡-1,0→k≡0,2 (mod 3)

10≡2 (mod 8)

43≡3 (mod 8)

3k≡-2,-1,2→k≡-6,-3,6≡2,5,6 (mod 8)

k≡16x+9y (mod 24)

r[1]≡18

r[2]≡45≡21

r[3]≡54≡6

r[4]≡32+18≡2

r[5]≡32+21≡5

r[6]≡32+6≡14

よって、

r≡2,5,6,14,18,23 (mod 24)

10+43r

10+43×2=10+86=96=3×32=3×2^5

10+43×5=10+215=225=15^2

よって、

x^2≡10≡10+43×5≡225≡15^2

x≡±15≡15,28 (mod 43)

(2022/10/30)

今日の？【2022/12/21】(情報漏洩の確率上がる？)

マイナカードの本人確認「“郵便局”でもできるように…」次期通常国会で法改正検討 松本総務大臣

マイナカードの申請はオンラインや郵送で行いますが、受け取る際には本人確認が必要で、自治体の窓口に行く必要がありました。これについて松本総務大臣は岸田総理との面会後、本人確認を“郵便局”の窓口でもできるよう法改正を検討していることを明らかにしました。

受け取る際、カードを利用するために最低2つの暗証番号を設定する必要がある。

民間企業の窓口で手続きするとなると、情報漏洩が心配である。

法により罰則を強化しても、それ以上の利益があればやった者勝ちである。

時事川柳【2022/12/21】(障害者施設の現実)

「ちょっと待て」 言われてからが 3時間(鯉正)

(2022/12/21)

車椅子の私が入所している障害者施設。

コールをすると、1回目は無視。

2回目、「ちょっと待て」とあるものの対応してもらえなかった。待った時間は3時間以上。

その間なしのつぶて。

結局障害者のコールは無視された。

少しは"人間らしく"扱って欲しい。

最近の自分に言い聞かせてる言葉

「障害者だから仕方ない」

「障害者だから無視されるのが当たり前」

【2次合同方程式の可解性】

ルジャンドルの記号 ❲ ❳

x^2≡a (mod p)において

解を持つ→❲a/p❳=1

解を持たない→❲a/p❳=-1

a=pt+b→❲a/p❳=❲b/p❳ : a＞pのとき利用

オイラーの規準

pを奇素数、aをpと互いに素な0でない整数

とする。

❲a/p❳≡a^{(p-1)/2}

pを奇素数とする。

第一補充法則 ❲-1/p❳=(-1)^{(p-1)/2}

第二補充法則 ❲2/p❳=(-1)^{(p^2-1)/8}

ルジャンドル記号の性質

a,bがpの倍数でないとき

❲(ab)/p❳=❲a/p❳×❲b/p❳

平方剰余の相互法則

相異なる奇素数p,qに対して

❲q/p❳×❲p/q❳=(-1)^{(p-1)/2×(q-1)/2}

本来はすべて証明すべきことだが、これらを利用して2次合同式の可解性について考える。

==============================

【ルジャンドル記号❲ ❳の計算ルール】

p,qを奇素数とする。

①❲1/p❳=1、❲k^2/p❳=1

②❲(pt+r)/p❳=❲r/p❳

③a,bがpの倍数でないとき、

❲(ab)/p❳=❲a/p❳×❲b/p❳

④p=4s+3, q=4t+3→❲q/p❳=-❲p/q❳

それ以外→❲q/p❳=❲p/q❳

⑤p=8k±1→❲2/p❳=1

p=8k±3→❲2/p❳=-1

==============================

【❲a/p❳を計算アルゴリズム】

①a＞pのとき、a=pt+r→❲a/p❳=❲r/p❳

②aが合成数のとき、素因数分解する。

a=Π(p[i]^t[i]), t[i]≡u[i] (mod 2)

❲a/p❳=Π❲p[i]/p❳^u[i]

③p[i]すべてが2のとき→⑤

以下p[i]≠2を、処理する。

④p=4k+3, p❲i❳=4k+3のとき、

❲p[i]/p❳=-❲p/p[i]❳

それ以外のとき、❲p[i]/p❳=❲p/p[i]❳

①に戻る

⑤❲a/p❳を(-1)^s×Π❲2/q[i]❳の形に変形する。

⑥q[i]=8k±3である個数をtとする。

⑦❲a/p❳=(-1)^(s+t)

【例】x^2≡24 (mod 83)

❲24/83❳

24=2^3×3より、3≡1 (mod 2)

❲24/83❳=❲2/83❳×❲3/83❳

3=4×0+3, 83=4×20+3→❲3/83❳=-❲83/3❳

❲24/83❳=❲2/83❳×(-❲83/3❳)=-❲2/83❳×❲83/3❳

83=3×27+2→❲83/3❳=❲2/3❳

❲24/83❳=-❲2/83❳×❲2/3❳

3,83ともに8k±3型

❲24/83❳=-(-1)^2=-1

よって、解なし

【例】x^2≡42 (mod 89)

❲42/89❳

42=2×3×7

❲42/89❳=❲2/89❳×❲3/89❳×❲7/89❳

=❲2/89❳×❲89/3❳×❲89/7❳

=❲2/89❳×❲1/3❳×❲5/7❳

=❲2/89❳×1×❲7/5❳

=❲2/89❳×❲2/5❳

=1×1=1

よって、解あり

x≡24,65 (mod 89)→次回解説

【注意】(mod 2)の2次合同方程式

①x^2+x+1≡0 (mod 2)

②x^2+x≡0 (mod 2)

③x^2+1≡0 (mod 2)

④x^2≡0 (mod 2)

①x^2+x+1≡0 (mod 2)

x^2+x≡1→x(x+1)≡1

x(x+1)は常に偶数だから、x(x+1)≡0

よって、解なし

②x^2+x≡0→x(x+1)≡0→x≡0,-1

→x≡0,1→すべての整数

③x^2+1≡0 (mod 2)→x^2≡1→x≡±1

→x≡1→xは奇数

④x^2≡0 (mod 2)→x≡0→xは偶数

(2022/10/31・11/14)