🚀 go-pugleaf

$B5WLg!w(BICOT$B$G$9!#(B
$B4V$K5Y(B$BF|$J$I$,$O$5$^$C$?$j$7$F$:$$$V$sCY$l$F$7$^$$$^$7$?$,(B
$BJ?J}:,!J(Bn$B>h:,!K$r5a$a$kJ}K!$K4X$9$k$^$H$a$G$9!#(B

 | $BAG?t$rK!$H$9$k>jM>7O$N7W;;$G!"$"$k?t$,B>$N?t$N(B
 | $BJ?J}$K$J$C$F$$$k!"$D$^$jJ?J}>jM>$G$"$k$+$I$&$+$O(B
 | $B$9$0$KH=Dj=PMh$k$3$H$OJ,$+$k$N$G$9$,!"(B
 | $B<B:]$K2?$NJ?J}$K$J$C$F$$$k$+$r5a$a$k%"%k%4%j%:%`(B
 | $B$O$I(B$B$&$9$l$PNI$$$+$H8@$&$3$H$G$9!#(B

$B$H8@$&KM$N<ALd$KBP$7$F!"(B
	$B%K%e!<%9$G(B	$B$^$m!wAa0pEDBg3X$5$s(B
	$B%a!<%k$K$F(B	$BKqK\!w#N#E#C$5$s(B
$B$+$i%U%)%m!<$$$?$@$-$^$7$?!#(B

$B$^$:!"$*OM$S$+$i!"(B
$B$3$NA0$N%]%9%H$N(BFrom$B9T$N%"%I%l%9$,(B$B4V0c$C$F$$$^$7$?!#(B
$B@5$7$/$O(Bkumon@icot.or.jp$B$G$9!#(B

$B$^$m!wAa0pEDBg3X$5$s$+$i$O!"(B
 |$BM7@1<R(B $BOBED=(IWCx(B $B!V(B$B%3%s%T%e!<%?$HAG0x;RJ,2r!W(B

$B$H8@$&K\$r>R2p$7$F$$$?$@$-$^$7$?!#(B
$B$3$NK\$K$O!"AG?tH=DjJ}K!$J$I$N%"%k%4%j(B$B%:%`$,:\$C$F$*$j!"(B
$BJ?J}:,$r5a$a$kJ}K!$b=P$F$$$^$7$?!#(B
$BJ?J}:,$r5a$a$k%"%k%4%j%:%`$O4pK\E*$KKqK\!w#N#E#C(B$B$5$s$+$i(B
$B%a!<%k$G$$$?$@$$$?J}K!$HF1$8$J$N$G!"(B
$B0J2<$OKqK\$5$s$N%a!<%k$r4pK\$K@bL@$7$^$9!#(B

$BKqK\!w#N#E#C(B$B$5$s$H$O2?EY$+%a!<%k$r$d$j$H$j$7!"(B
$B%"%k%4%j%:%`$rCzG+$K65$($F$$$?$@$-$^$7$?!#(B

$B$J$*!"$3$N%a!<%k$OBgJQ(B$B$K$-$A$s$H$^$H$^$C$F$$$k$N$G!"(B
$BKM$,=q$-D>$9$h$j$b86J8$r$=$N$^$^0zMQ$7$?J}$,(B
$BJ,$+$j$d$9$$$H;W$$$^$9!#(B
$B$=$3$G!"0J2<$KE>:\$5$;$F$$$?$@$-$^$9!#(B
$B$J$*!"8fK\?M$,$3$N%a!<%k$OE>:\$O<+M3$G$"$k$H8@$C$F$*$i$l$^$9!#(B

$B<XB-$@$H$O;W$&$N$G$9$,!"KM$,M}2r$7$?$3$H$b$D$1$F$*$-$^$7$?!#(B


$BKqK\!w#N#E#C$5$s(B:
 | $BG$0U$N4qAG?t$r(B$BK!$H$9$kJ?J}:,7W;;%"%k%4%j%:%`$O!"J88%(B[1]$B$K5-:\$N(B
 | $B<!$NJ}K!$,<BMQE*$GH~$7$$$G$9(B($B5-=R$O>/$7JQ$($F$"$j(B$B$^$9(B)$B!#(B
 | $B$J$*!"9gF15-9f(B'$B"a(B'$B$OI8=`4A;z$G$O$J$$$h$&$J$N$G!"(B'='$B$GBeMQ$7$^$9!#(B
 | 
 | $B!Z#1![J?J}:,7W;;J}(B$BK!(B (r^2 = y (mod p) $B$rK~$?$9(B r $B$r5a$a$k(B)
 |   (1) p = 2^k q + 1  $B$rK~$?$9@0?t(B k $B$H4q?t(B q $B$r5a$a$k!#(B
 |   (2) p $B$rK!$H$9$kJ?J}Hs>jM>(B g $B$rMQ0U$9$k!#(B
 |   (3) v = 1 $B$H$*$/!#(B
 |   (4) (y v^2)^{2^i q} = 1 (mod p) $B$rK~$?$9:G>.$N@0?t(B i (0$B!e(Bi$B!e(Bk)
 |       $B$r8+$D$1$k!#(B
 |   (5) 1$B!e(Bi$B!e(Bk-1 $B$J$i!"(Bv = v g^{2^{k-i-1}} $B$H$7$F(B (4) $B$KLa$k!#(B
 |   (6) i=0 $B$J$i(B r = $B!^(B (y v^2)^{(q+1)/2} v^{-1} mod p $B$,#2$D$NJ?J}:,!#(B
 |   (7) i=k $B$J$i2r$J$7!#(B
 | 
 | $B2r@b!'(B
 | $B!](B(1),(2)$B$O(B p $B$N$_$+$iA07W;;2DG=$G$"$k!#J?J}Hs>jM>(B g $B$OB?9`<0;~(B$B4V(B
 |   $B$G5a$^$k$H$5$l$F$$$k$,(B[1]$B!"4JC1$K$OMp?t$NJ?J}>jM>8!Dj$r9T$($P!"(B
 |   $B#12s$K$D$-3NN((B 1/2 ($B$9$J(B$B$o$AJ?6Q#22s$N%F%9%H(B) $B$G5a$a$i$l$k!#(B
 | $B!](B(4),(5)$B$N7+$jJV$7$G$O(B (y v^2)^q = 1 (mod p) $B$rK~$?$9(B v $B$r5a(B$B$a$k!#(B
 |   (4) $B$N;~E@$G$O(B (y v^2)^{2^{i-1} q} $B!b(B 1 (mod p) $B$G$"$k$,!"(B(5)$B$G(B
 |   $B$3$l$,(B =1 (mod p) $B$H(B$B$J$k!#$h$C$F#12s$N7+$jJV$7$G(B i $B$O>/$J$/$H$b(B
 |   $B#18:>/$9$k$+$i!"7+$jJV$72s?t$O:G0-$G(B k $B2s$G$"$k!#(B
 |   $B$7$?$,$C$F7W;;NL$O(B O((log p)^4) $B$@$H;W$$$^$9!#(B
 | $B!](B(y v^2)^q = 1 (mod p) $B$rK~$?$9(B v $B$,8+$D$+$l$P!"(B
 |   r = $B!^(B(y v^2)^{(q+1)/2} v^{-1} (mod p) $B$O!"(B
 |   r^2 = (y v^2)^{q+1} v^{-2} = (y v^2)^q y = y (mod p)
 |   $B$rK~$?$9#2$D$NJ?J}:,$G$"$k!#(B
 | $B!]:n6HJQ?tEy$r;H$($P>e5-%"%k%4%j%:%`$O9bB.2=$,2DG=$G$"$k!#(B
 |   $BJ88%(B[2]$B$O>e5-%"%k%4%j%:%`$N9bB.2=HG$G$9!#(B($B<jA0$_$=$G$9$,(B :-)
---------------------------
$BKM$NM}(B$B2r!J<XB-$G$9!K(B
$B!V%3%s%T%e!<%?$HAG0x;RJ,2r!W$K$O!"J?J}Hs>jM>$r5a$a$k;~$K(B
2,3,5,7$B$J$I$NAG?t$rD4$Y$F$$$^(B$B$9$,!"J?J}>jM>$HJ?J}Hs>jM>$O(B
$BF1?t$"$j$^$9$N$G!"FC$KAG?t$@$1$rD4$Y$J$/$F$b$9$0$K(B
$BJ?J}Hs>jM>$O8+$D$+$k$H(B$B;W$$$^$9!#(B

r^2 = y (mod p)$B$KBP$7!"$b$7(By$B$N4q?t(B(2n-1)$B>h$,(B1$B$H$J$k$J$i$P!"(B
y = y^{2 n} (mod p)$B$@$+$i!"(By ^ n $B$,(By$B$NJ?J}:,$K$J$k!#(B

$B$3$l$O!":G=i$KKM$,%]%9%H$7$?(Bp = -1 (mod 4)$B$N>l9g$K$O>o$K$J$jN)$D!#(B
$B$=$l$G!"(Bp = -1 (mod 4)$B$N;~$K$O4JC1$K5a$a$i$l$?!#(B

$B$=$l0J30$N;~$K$O!"(By$B$KE,@Z$JJ?J}:,$NJ,$+$C$F$$$k(B
$BJ?J}>jM>$r3](B$B$1$k$3$H$K$h$j>e$K<($7$?$h$&$K4q?t>h$G(B
1$B$K$J$l$P$"$H$O2?$H$+$J$k!#(B

$B>e$N(B(4)$B$G:G>.$N@0?t(Bi$B$H=q$$$F$"$k$N(B$B$O(Bi-1$B$N;~$K$O(B
(4)$B$N<0$,(B=-1$B$H$J$k$?$a$KI,MW$J>r7o$G$"$k!#(B
p$B$,AG?t$N;~$K$O(B1$B$NJ?J}:,$,!^(B1$B$7$+$J$$$H8@$&$3(B$B$H$,;H$o$l$F$$$k!#(B
$B$3$l$K!"G$0U$NJ?J}Hs>jM>(B g $B$N(B{(p-1)/2}$B>h$D$^$j!"(Bg ^ {(p-1)/2} = -1$B$r(B
$B3]$1$k$3$H$G!"(B$B$h$j>.$5$$(Bi$B$G(B(4)$B$N<0$,(B=1$B$H$J$kCM$r@8@.$7(B
$B:G=*E*$K(B(p-1)$B$r#2$G3d$j@Z$l$k$@$13d$C$?;~$K=P$k4q?t>h$G(B=1$B$H(B
$B$J$k$b$N$r5a$a$k!#(B

$B!t$d$C$Q$j$3$N2r@b$O<XB-$@$H;W$&(B
-------------------------------

$B<!$O(Bn$B>h:,$N5a$a(B$BJ}$G$9!#(B

 |    >$B$^$?!"$b$C$H0lHL$K(Bn$B>h:,$r5a$a$kJ}K!$O$"$k$N$G$7$g$&$+!)(B
 | 
 | $BJ88%(B[1]$B$O!">e5-$N%"%k(B$B%4%j%:%`$rJQ7A$7$?!"0lHL$N#n>h:,7W;;%"%k%4(B
 | $B%j%:%`$bM?$($F$$$^$9!#0J2<$N%"%k%4%j%:%`$N86M}$OJ88%(B[1]$B$N$b$N$G(B
 | $B$9$,!"5-=R$O>/$7JQ$($F$"$j$^$9!#(B
 | $B#n>h:,$O!"(Bn $B$rAG0x?tJ,2r$7$F!"$=$N3F!9$NAG0x?t>h:,7W;;(B$B$r=g<!9T$($P(B
 | $B7W;;$G$-$^$9(B($BNc$($P(B60$B>h:,$OJ?J}:,$NJ?J}:,$N#3>h:,$N#5>h:,$G5a$^$k(B)$B!#(B
 | $B$7$?$,$C$F!"(Bn $B>h:,7W;;LdBj$O!"AG?t>h:,7W;;LdBj$K4T85$5$l$^$9!#(B
 | 
 | $B!Z#2![AG?t>h:,7W;;J}K!(B (r^n = y (mod p) $B$rK~(B$B$?$9(B r $B$r5a$a$k!#(Bn$B$OAG?t(B)
 |   (1) p = n^k q + 1 $B$rK~$?$9@0?t(B k,q (gcd(n,q)=1) $B$r5a$a$k!#(B
 |       $B$^(B$B$?!"(Bq $B$rK!$H$9$k(B n $B$N5U?t(B h $B$r5a$a$k(B(h = n^{-1} mod q)$B!#(B
 |   (2) g^{(p-1)/n} mod p $B!b(B 1 $B$rK~$?$9(B g $B$r(B$BMQ0U$9$k!#(B
 |   (3) v = 1 $B$H$*$/!#(B
 |   (4) (y v^n)^{n^i q} = 1 (mod p) $B$rK~$?$9:G>.$N@0?t(B i (0$B!e(Bi$B!e(Bk)
 |       $B$r8+$D$1$k!#(B
 |   (5) 1$B!e(Bi$B!e(Bk-1 $B$J$i!"(Bv = v g^{n^{k-i-1}} $B$H$7$F(B (4) $B$KLa$k!#(B
 |   (6) i=0 $B$J$i(B r = (y v^n)^h v^{-1} mod p $B$,#n>h:,$N0l$D!#(B
 |   (7) i=k $B$J$i2r$J$7!#(B
 | 
 | $B$"$^$j>\$7$/$O2r@b(B$B$7$^$;$s$,$A$g$C$H$@$1!#(B
 | $B!](B(2)$B$G$O(B n$B>hHs>jM>(B(n$B>h:,$r;}$?$J$$85(B) g $B$r5a$a$F$$$^$9$,!"(B
 |   $B86;O:,$r(B$BMQ$$$l$PG$0U$N(B n $B$KBP1~$G$-$^$9!#(B
 | $B!]$3$N%"%k%4%j%:%`$O(B gcd(n,p-1)=1 $B$N>l9g$rJq4^$7$^$9!#(B
 | $B!]$b$A(B$B$m$s(B n=2 $B$H$9$l$P$=$N$^$^%"%k%4%j%:%`!Z#1![$H$J$j$^$9!#(B
 | $B!]>e5-$G$O#1$D$7$+5a$a$F$$$^$;$s$,!"(Bn $B$,(B p-1 $B$NLs?t$G$"$k;~!"(B
 |   $B#n>h:,$O#n8DB8:_$7!"$3$l$i$O(B r_j = r (g^{(p-1)/n})^j (mod p)
 |   (j=0...n-1) $B$GA4$F5a$^$j$^$9!#(B
 | $B!](B(4),(5)$B$N7+$jJV$7$K$*$$$F(B i $B$r#18:$i$9$N$K!":G0-$G(B n-1 $B2s$+$+(B
 |   $B$j$^$9!#(B$B$7$?$,$C$F7+$jJV$72s?t$O:GBg(B (n-1)k $B2s$K5Z$S!"(Bn $B$,Bg(B
 |   $B$-$$;~(B log p $B$NB?9`<0;~4V$G$O7W;;$G$-$J$/$J(B$B$j$^$9(B (k$B!b(B0$B$N;~(B)$B!#(B
 | 
 | $B$H8@$&$o$1$G!"G$0U$N(B n $B>h:,$H$O$$$C$F$b!"(Bgcd(n,p-1) $B$,Bg$-$$;~(B
 | $B$O8=<BE*(B$B$K7W;;=PMh$J$$$h$&$G$9$M!#$3$l$,2DG=$J%"%k%4%j%:%`$r;d(B
 | $B$OCN$j$^$;$s!#$b$7$o$+$C$?$i65$($F2<$5$$$M!#(B
---------------------------
$B<XB-(B
p-1$B$,(Bn$B$NG\?t$G$J$$;~!J(Bn$B$,AG?t$H$7$F!K$K$O!"(B
$BG$0U$NCM$,(Bn$B>h:,$r;}$A4J(B$BC1$K7W;;$G$-$k!#(B
k n = 1 (mod p-1)$B$H$J$k(Bk$B$r5a$a$l$P(By ^ k$B$,$=$N:,$K$J$k!#(B
	(y ^ k) ^ n = y ^ {k n} = y ^ 1 = y $B$@$+$i!#(B
$B$h$C$FG\?t$N;~$@$1$r9M$($k!#(B
$B!J<B$O!"G\?t$N;~$K(Bn$B>h:,$r5a$a$k%"%k%4%j%:%`$O(B
  $B$=$N$^(B$B$^G\?t$G$J$$;~$K$b7k2LE*$K;HMQ$G$-$k!K(B

$B0lHL$N(Bn$B>h:,$G$O(B1$B$N(Bn$B>h:,$O(B1$B0J30$K(Bn-1$B8D$"$k!#(B
(2)$B$G5a$a$?(Bn$B>hHs>j(B$BM>(Bg$B$N(B{p-1}/n$B>h$O(B1$B$N??$N(Bn$B>h:,$K$J$C$F$$$k!#(B
$B$^$?!"(B(4)$B$G5a$a$?(Bi$B$K$h$k(B(y v^n)^{n^{i-1} q}$B$O(B1$B$N(Bn$B>h:,$K$J$C(B$B$F$$$k!#(B
$B$h$C$F!"(B(y v^n)^{n^{i-1} q}$B$K2?2s$+(Bg^{{p-1}/n}$B$r3]$1$k$H(B
$B#1$K$J$k!#$3$N2s?t$OB?$/$F$b(Bn-1$B2s$G(B$B$"$k!#(B

$B7k6I!"(B(4)$B$N%9%F%C%W$G(Bi$B$h$j>.$5$$CM$G(B
=1$B$K$J$k$b$N$r5a$a$k$N$K:G0-(Bn-1$B%9%F%C%W3]$+$k!#(B
$B=>$C$F!"(B$B2r$rF@$k$?$a$N%9%F%C%W?t$,J?J}:,$N;~$h$j$b(B
$BB?$/$J$k!#(B
$B$b$7!"$"$i$+$8$a(B(y v^n)^{n^{i-1} q}$B$G=P$F$/$k$9(B$B$Y$F$N(B
$B#1$G$J$$CM!J9b!9(Bn-1$B8D!K$KBP$7$F%F!<%V%k$rMQ0U$9$k$3$H$G(B
$B?7$7$$(Bv$B$r7W;;$9$k$J$i$P(B(4)(5)$B$N%k!<%W$O(B$B#12sKh$K(B
i$B$r8:$i$9$3$H$,=PMh$k!#(B


 |    >$B$3$N$h$&$J%"%k%4%j%:%`$K4X$7$F=q$$$F$"$k;29M=q$J$I(B
 |    >$B$"$j$^$7$?$i!"65$($F2<$5$$!#(B
 | 
 | $BJ?J}:,!"#n>h:,7W;;J}K!$H$7$F$O!"B>$K$b#n<!J}Dx<0$N0x?tJ,2r(B
 | $B$K$h(B$B$kJ}K!$,$"$j$^$9$,!"$"$^$jM}2r$7$F$J$$$N$G!"J88%$r>R2p(B
 | $B$9$k$@$1$K$H$I$a$^$7$g$&(B[3][4][5][6][7]$B!#(B
 | $B0J2<$K;29MJ88%$r$"$2$F$*$-$^$9!#(B[2],[6],[7]$B0J30$O1Q8l$G$9!#(B
 |
 | [$B;29MJ88%(B]
 | [1] L.Adleman, K.Manders, G.Miller, "On Taking Roots in Finite Fields",
 |     18th IEEE Annual Symposium on Foundations of Computer Science,
 |     Providence RI, 1977.
 | [2] $BKqK\M59,(B, "GF(p)$B>e$NJ?J}:,$r5a$a$k0lJ}<0(B", $BBh(B14$B2s>pJsM}O@$H(B
 |    $B$=$N1~MQ%7%s%]%8%&%`(B(SITA'91)$BM=9F=8(B, vol.1, pp.37-40, Dec.1991.
 | [3] M.O.Rabin, "Probabilistic Algorithm in Finite Fields'',
 |     SIAM.J.Comput. vol.9 No.2 pp.273-280, May 1980.
 | [4] R.C.Peralta, "A Simple and Fast Probabilistic Algorithm for
 |     Computing Square Roots Modulo a Prime Number", IEEE Transactions
 |     on Information Theory Vol.IT-32 No.6 pp.846, Nov.1986.
 | [5] T.Itoh, "Efficient Probabilistic Algorithm for Solving Quadratic
 |     Equations over Finite Fields", Electronics Letters 13th Vol.23
 |     No.17 pp.869-870, Aug.1987.
 | [6] $B0KElMx:H(B, "$BM-8BBN>e(B$B$N(B2$B<!J}Dx<0$r2r$/8zN(E*$J3NN(E*%"%k%4%j%:%`(B",
 |     $BEE;R>pJsDL?.3X2qO@J8;o(B A Vol.J71-A No.1 pp.95-101, Jan.1988.
 | [7] D.E.Knuth, "The Art of Computer Programming, vol.2 Seminumerical
 |     Algorithms - Arithmetic", Addison-Wesley Corp.
 |     ($BK.Lu!'Cf@n7=2pLu(B,$B!V=`?tCM;;K!!?;;=Q1i;;!W(B,$B%5%$%(%s%9<R(B)


$BKqK\!w#N#E#C$5$s$+$i<!$N<ALd$,$"$j$^$7$?$N$G(B
$B%a!<%k$G$O$*Ez$($7$?$N$G$9$,!"$3$3$G$bEz$($F$*$-$^$9(B$B!#(B

 | $B$"$H!"$b$7:9$7;Y$($J$1$l$P!"$J$<$3$s$JLdBj$K6=L#$r;}$C$?$N$+$r(B
 | $BJ9$+$;$F2<$5$k$H:#8e$N;29M$K(B$B$J$k$N$G$9$,!#(B

$B85!9$O8x3+0E9f$r6=L#K\0L$GD4$Y$F$$$?$3$H$,H/C<$G$9!#(B
$B8x3+0E9f$K4X$9$k!V$"$kLuK\!W$rGc(B$B$C$?$H$3$m!"(B
$B$=$l$,$H$F$b$R$I$$FbMF$G!"FI$s$G$$$F$b?t3XE*$J%Y!<%9$,(B
$BNI$/J,$+$i$J$+$C$?$N$G!"@0?tO@$rJY(B$B6/$7;O$a$^$7$?!#(B
$B$7$+$7!"KM$,8+$F$$$k?t3X$N652J=q$K$O%"%k%4%j%:%`$d(B
$B7W;;NL$J$I$,$[$H$s$I9MN8$5$l$F$$$J(B$B$+$C$?$N$G!"(B
$BK\$NCf$K=P$F$/$kJ?J}:,$J$I$r$I$&$d$C$F5a$a$k$N$+$,(B
$BCN$j$?$+$C$?$o$1$J$N$G$9!#(B

$B!t$3$N!V$"(B$B$kLuK\!W$O62$i$/Lu<T$,NI$/M}2r$7$F$$$J$$$N$+(B
$B!tA4$/Lu$r8+D>$7$F$$$J$$$N$+$N$I$A$i$+$H8@$C$FNI$$$[$I(B
$B!t(B$B8mLu!"8m?"$,B?$+$C$?!#0l>>@h@8!"?dA&$N8@MU$J$s$+=q$+$J$$$G$h!A(B

$B0J>e<ALd$KEz$($F$$$?$@$$$?!"$^$m!wAa0p(B$BEDBg3X$5$s!"KqK\!w#N#E#C$5$s(B
$BBgJQ$"$j$,$H$&$4$6$$$^$7$?!#(B

$BM>CL!#(B
1993$BG/F|K\?t3X%*%j%s%T%C%/M=A*$NBh#1(B$BLd$NEz$($O(B

4*2*2=16$B$G$9$h$M!)(B
--
$B5WLg9L0l!w#I#C#O#T#18&(B				TEL 03-3456-3193
						kumon@icot.or.jp