Annotation of OpenXM/doc/sci-semi2001/factor-resume.tex, Revision 1.4
1.4 ! noro 1: %$OpenXM: OpenXM/doc/sci-semi2001/factor-resume.tex,v 1.3 2001/07/28 03:31:09 noro Exp $
1.1 noro 2: \documentclass[12pt]{jarticle}
3: %\oddsidemargin -0.25in
4: %\evensidemargin -0.25in
5: \topmargin -0.5in
6: \oddsidemargin -0.1in
7: \evensidemargin -0.1in
8: \textwidth 6.5in
9: \textheight 9.5in
10: \IfFileExists{epsfig.sty}{\usepackage{epsfig}}{}
11: \usepackage{latexsym}
12:
13: \title{$BB?9`<0$N0x?tJ,2r(B \\ --- $B%3%s%T%e!<%?>e$G$NBe?t7W;;(B ---}
14: \author{$BLnO$(B $B@59T(B \\ $B?@8MBg3XM}3XIt?t3X2J(B}
15: \date{2001 $BG/(B 7 $B7n(B 29 $BF|(B}
16: \begin{document}
17: \addtolength{\baselineskip}{5pt}
18: \maketitle
19: %\begin{center}
20: %Copyright~\copyright 2000 by Masayuki Noro. All rights reserved.
21: %\end{center}
22:
23: \section{$B$O$8$a$K(B}
24:
25: computer $B$H$$$&8@MU$O(B, $BJ8;zDL$j$K2r<a$9$l$P!V7W;;!W$9$k$?$a$N$b$N$H$$(B
26: $B$&0UL#$@$m$&$,(B, $B:G6a$G$O(B email, $B%&%'%V$J$I%G%8%?%k>pJsDL?.$N$?$a$N%D!<(B
27: $B%k$H$J$C$F$7$^$C$?46$,$"$k(B. $B7k2L$H$7$F(B, $B%3%s%T%e!<%?$r7W;;$K;H$C$F$$(B
28: $B$k?M$O$4$/>/?t$G$"$m$&(B. $B$7$+$7(B, $B%3%s%T%e!<%?$NG=NO$O:G6a0[MM$J$^$G$K8~(B
29: $B>e$7$F$*$j(B, $B7W;;$K;H$o$J$$$N$O$b$C$?$$$J$$$H8D?ME*$K$O;W$&(B. $B<B:](B, $BI.<T(B
30: $B$,K\3JE*$K%W%m%0%i%_%s%0$r$O$8$a$?(B 15 $BG/DxA0$K$O(B, $B$$$o$f$k%o!<%/%9%F!<(B
31: $B%7%g%s%/%i%9$N%^%7%s$,0l@iK|1_$[$I$7$F(B, $B$7$+$b7W;;G=NO$O:#$N(B PC $B$N?tI4(B
32: $B$+$i@iJ,$N0lDxEY$7$+$J$+$C$?$N$G$"$k(B. $BEv;~$O$=$NHsNO$J%^%7%s$rBg@*$G6&(B
33: $BF1MxMQ$7$F$$$?$o$1$G(B, $B$^$5$K3V@$$N46$,$"$k(B.
34:
35: $BK\9F$G=R$Y$k$h$&$J7W;;$O(B, $B$$$o$f$kBe?t7W;;$H8F$P$l$k$b$N$G(B, $B$h$j0lHLE*(B
36: $B$J?tCM7W;;$HHf$Y$k$HA[A|0J>e$K7W;;%Q%o!<(B, $B5-21MFNL$rI,MW$H$9$k(B. $B$7$+$7(B,
37: $B$$$^$d2HDm$K$"$kIaDL$N(B PC $B>e$G$b$3$N$h$&$J7W;;$OMF0W$K<B9T$G$-$k(B. $B$3$3(B
38: $B$G=R$Y$k$3$H$,(B, $B%3%s%T%e!<%?$N?7$7$$;H$$F;$"$k$$$O?t3X$NM-MQ@-$r8+=P$9(B
39: $B%R%s%H$H$J$l$P9,$$$G$"$k(B.
40:
41: \section{$B%3%s%T%e!<%?$K$D$$$F$N%$%m%O(B}
42:
43: $B%3%s%T%e!<%?$N<gMWIt$H$7$F(B, $B%W%m%0%i%`$r=g$K<B9T$9$k(B CPU, $B%W%m%0%i%`(B,
44: $B%G!<%?$rCV$/>l=j$G$"$k%a%b%j(B, $B$*$h$S(B CPU $B$,;}$DFCJL$J%a%b%j$G$"$j(B, $B1i(B
45: $B;;$NBP>]$H$J$k%l%8%9%?$,$"$k(B. $BL?Na$H$$$&$N$O(B, $BNc$($P<!$N$h$&$J$b$N$G$"$k(B.
46:
47: \begin{itemize}
48: \item 10 $BHVCO$+$i(B 1 $B%P%$%HFI$s$G(B A $B%l%8%9%?$KF~$l$h(B
49: \item A, B $B%l%8%9%?$NCM$rB-$7$F(B C $B%l%8%9%?$KF~$l$h(B
50: \item A $B%l%8%9%?$NCM$,(B 0 $B$J$i(B 100 $BHVCO@h$KHt$Y(B
51: \end{itemize}
52:
53: $B$3$N$h$&$K(B CPU $B$X$NL?Na$N0l$D0l$D$OC1=c$J$b$N$P$+$j$G$"$k(B.
1.4 ! noro 54: $B07$($k?t$NBg$-$5$O(B, $B%l%8%9%?$NBg$-$5$G7h$^$k$H8@$C$F$h$$(B. $B$?$H$($P(B,
1.1 noro 55: 32 $B%S%C%H%l%8%9%?$H$$$&$N$O(B 0 $B$^$?$O(B 1 $B$rI=$95-21AuCV$,(B 32 $B8D$"$k(B
56: $B%l%8%9%?$G$"$k$,(B, $B$3$N%l%8%9%?$O(B 0 $B$+$i(B $2^{32}-1$ $B$^$G$N@0?t$7$+(B
57: $BJ];}$G$-$J$$$3$H$K$J$k(B.
58:
59: CPU $B$NDs6!$9$k5!G=$@$1$G$O(B, $B?t3X$K;H$&$K$OITB-$G$"$k$3$H$,L@$i$+$G$"$k(B.
60: $B$?$H$($P(B $11111111111 \times 11111111111$ $B$r7W;;$7$?7k2L$H$7$F(B
61: 1332508849 $B$H$$$&?t;z$,JV$5$l$k>l9g$,$"$k(B. $B$3$N7k2L$O(B, $B<B$O??$N@Q(B
62: $B$NCM$r(B $2^{32}$ $B$G3d$C$?M>$j$G$"$k(B. $B$"$k$$$O(B,
63: $BEEBn$N$h$&$K(B $1.234567 \times 10^{20}$ $B$H$$$&CM$rJV$5$l$k$N$b:$$k(B.
64: $B8m:9$,F~$C$F$7$^$&$H(B, $B?t3XE*$K$O0UL#$N$J$$7k2L$H$J$j$+$M$J$$(B.
1.4 ! noro 65: $B$9$J$o$A(B, $B?t3X$K;H$&$K$O(B, $B07$($k@0?t$NBg$-$5$K@)8B$,$"$C$F$O$J$i$J$$(B.
1.1 noro 66: $B$3$N$?$a$K$OG$0U$NBg$-$5$N@0?t$r07$&$?$a$N%W%m%0%i%`$r=q$1$P$h$$(B.
67: $B$9$J$o$A(B, $B%a%b%j>e$K(B, $BNc$($P(B 32$B%S%C%H@0?t$rJB$Y$F(B, $B%3%s%T%e!<%?$K(B
68: $B!VI.;;!W$r$5$;$l$P$h$$(B. $B$3$N>l9g(B, $B?M4V$H0[$J$k$N$O(B, $B?M4V$N>l9g(B,
69: $BDL>o$R$H$1$?$H$$$&$N$O(B 0 $B$+$i(B 9 $B$^$G$N?t$@$,(B, $B%3%s%T%e!<%?$N>l9g(B
70: $B$R$H$1$?$,(B 0 $B0J>e(B $2^{32}-1$ $B$H$J$kE@$G$"$k(B.
71: $BNc$H$7$F(B, $B@0?t$NB-$7;;$O<!$N$h$&$K$J$k(B.
72:
73: \begin{tabular}{ccccc}\\
1.4 ! noro 74: & $2^{64}$ & $2^{32}$ & $1$ \\
1.1 noro 75: & 5 & 4001257187 & 1914644777 & (= $3^{42}$) \\
76: + & & 2830677074 & 689956897 & (= $3^{40}$) \\ \hline
77: & 6 & 2536966965 & 2604601674 & (= $10\times 3^{40}$)\\
78: \end{tabular}\\
79:
80: $B$+$1;;$K$D$$$F$O(B, CPU $B$,G\D91i;;$rDs6!$7$F$$$J$$>l9g$K$O$d$dJ#;($K$J$k$,(B
81: $B$"$H$OB-$7;;$HF1MM$G$"$k(B. $B3d;;$O(B, $B>&$N8+@Q$j$N$?$a$K$h$jJ#;($K$J$k$,(B,
82: $B4pK\E*$K$O?M4V$N9T$&I.;;$HF1MM$H9M$($F$h$$(B. $B$3$N$h$&$K$7$F(B, $BG$0U$NBg$-$5(B
83: $B$N@0?t$N;MB'$r9T$&%W%m%0%i%`$rAuHw$9$l$P(B, $B@0?t$"$k$$$OM-M}?t$r?t3XE*$K(B
84: $B@53N$K07$&$3$H$,$G$-$k(B. $B$3$l$r4pAC$H$7$F(B, $BNc$($P0lJQ?tB?9`<0$O(B, $B9S$C$]$/(B
85: $B8@$($P3F<!?t$N78?t$rJB$Y$?$b$N$H$7$FI=8=$G$-$k(B. $B$h$C$F(B, $B0lJQ?tB?9`<0$r(B
86: $B%3%s%T%e!<%?>e$G@53N$K07$($k$3$H$K$J$k(B. $B0J2<$G$O(B, $B$3$N1~MQ$H$7$F(B,
87: $BCf3X9b9;$G$*$J$8$_$NB?9`<0$N0x?tJ,2r$r(B, $B$I$&%3%s%T%e!<%?$K:\$;$k$+(B
88: $B$K$D$$$F9M$($k(B.
89:
90: \section{$BB?9`<0$N0x?tJ,2r(B --- $BCf3X9b9;E*J}K!(B}
91:
92: $BB?9`<0$N@0?t$NHO0OFb$G$N0x?tJ,2r$K$D$$$F(B, $B$*$J$8$_$NJ}K!$r5s$2$k(B.
93:
94: \begin{enumerate}
95: \item {$B4cNOK!(B}
96:
97: $x^2+ax+b$ $B$r0x?tJ,2r$9$k:]$K(B, $BB-$7$F(B $a$, $B$+$1$F(B $b$ $B$K$J$k?t$NAH(B
98: $B$r5a$a$kJ}K!$r$3$3$G$O4cNOK!$H8F$V$3$H$K$9$k(B. $b$ $B$,>.$5$$>l9g$K$O(B
99: $B$3$NJ}K!$,==J,DLMQ$9$k$,(B, $B0J2<$G8+$k$h$&$K(B, $b$ $B$,Bg$-$/$J$k$H(B
100: $B$3$NJ}K!$O$[$H$s$IL5NO2=$9$k(B. $B$^$?(B, 3 $B<!0J>e$N>l9g$K$3$NJ}K!$r(B
101: $BE,MQ$9$k$N$OIaDL$OL5M}$G$"$m$&(B.
102:
103: \item {$B0x?tDjM}(B}
104:
105: $B$3$l$O(B, $BB?9`<0(B $f(x)$ $B$KBP$7(B, $f(a)=0$ $B$J$i(B $f(x)$ $B$,(B $x-a$ $B$G(B
106: $B3d$j@Z$l$k$3$H$rMxMQ$9$kJ}K!$G$"$k(B. $B$3$l$b4cNO$G(B $a$ $B$rC5$9$N$O(B
107: $BFq$7$$$,(B, $BC5$7J}$K$h$C$F$OM-K>$G$"$k(B.
108:
109: \item {$B2r$N8x<0(B}
110:
111: $x^2+ax+b=0$ $B$N:,$,(B ${-b \pm \sqrt{a^2-4b}} \over 2$ $B$H=q$1$k$+$i(B,
112: $a^2-4b = t^2$ ($t$ : $B@0?t(B) $B$H$+$1$k$+$I$&$+D4$Y$l$P(B, $B$b$H$NB?9`<0(B
113: $B$,0x?tJ,2r$G$-$k$+$I$&$+J,$+$k(B.
114: \end{enumerate}
115:
116: $B$5$F(B, $BNc$($P(B $f(x) = x^2+11508x+28386587$ $B$r0x?tJ,2r$9$k>l9g(B, $B$I$NJ}K!(B
1.3 noro 117: $B$,$h$$$@$m$&$+(B. $f(x)$ $B$O(B $f(x)=(x+3581)(x+7927)$ $B$HJ,2r$5$l$k$,(B,
1.1 noro 118: $28386587=3581\cdot 7927$ $B$H$$$&AG0x?tJ,2r$,!V4cNO!W$GJ,$+$k?M$OB?J,>/(B
119: $B$J$$$H;W$&(B. $B<B:](B, $BB?9`<0$N0x?tJ,2r$KHf$Y$F(B, $B@0?t$NAG0x?tJ,2r$N$[$&$,$O(B
120: $B$k$+$K:$Fq$JLdBj$G$"$k(B. $B$^$?(B, $BAG0x?tJ,2r$,4JC1$G$b(B, $BAG0x?t$,B?$9$.$k$H(B,
121: $BAH9g$;$N?t$,B?$/$J$j$9$.$F(B, $B$d$O$j:$Fq$K$J$k(B. $B$D$^$j(B, $B4cNOK!$OLdBj$r$+(B
122: $B$($C$FFq$7$/$7$F$$$k$3$H$K$J$k(B.
123: $B<B$O(B, $B$b$C$H$b0BD>$=$&$K8+$($k(B, $B2r$N8x<0$NMxMQ$,$3$N>l9g$b$C$H$bM-K>(B
124: $B$G$"$k(B. $B$H$$$&$N$b(B, $B@0?t$,(B, $B$"$k@0?t$N(B 2 $B>h$K$J$C$F$$$k$+$I$&$+D4$Y$k$N$O(B,
125: $BAG0x?tJ,2r$KHf$Y$F$:$C$H$d$5$7$$$+$i$G$"$k(B. $B$3$NLdBj$N>l9g(B,
126: $(a^2-4b)/4 = 4717584$ $B$,(B $2172^2$ $B$G$"$k$3$H$O(B, $B<j7W;;$G$bHf3SE*MF0W(B
127: $B$KJ,$+$k(B.
128:
129: $BB?9`<0$N<!?t$,(B 3 $B<!0J2<$N>l9g(B, $B@0?t$NHO0OFb$GJ,2r$G$-$k$J$i0l<!$N0x;R$r(B
130: $B;}$D$N$G(B, $B:,$rC5$9$&$^$$J}K!$,$"$l$P$h$$(B. $B$3$l$K$O(B, $B$?$H$($P(B
131: $BCf4VCM$NDjM}(B
132: $B!V(B$f(a) < 0$, $f(b) > 0$ $B$J$i(B $a$, $b$ $B$N4V$K(B $f(c)=0$ $B$J$k(B $c$ $B$,$"$k(B.$B!W(B
133: $B$r;H$C$F:,$rC5$9J}K!$G$"$k!VFsJ,K!!W$"$k$$$O@\@~$rMQ$$$k%K%e!<%H%sK!(B
1.4 ! noro 134: $B$,$"$k(B ($B$$$:$l$b9b9;?t3X(B C $B$K$"$k(B). $BLdBj$O@0?t:,$NM-L5$J$N$G(B,
! 135: $B$3$l$i$NJ}K!$K$h$jHf3SE*MF0W$K:,$,C5$;$k(B. $B$7$+$7(B, $BB?9`<0(B
1.1 noro 136: $B$N<!?t$,(B 4 $B<!0J>e$N>l9g(B, $B0x;R$N<!?t$,$5$^$6$^$G$"$k$?$a(B, $B:,$rC5$9J}K!(B
137: $B$rE,MQ$9$k$N$O:$Fq$G$"$m$&(B. $B$=$3$G(B, $B%3%s%T%e!<%?$K9g$C$?J}K!$rC5$9$3$H(B
138: $B$K$9$k(B. $B%R%s%H$H$7$F$O(B,
139:
140: \begin{itemize}
141: \item $B!V6a;w!W$r$&$^$/;H$&(B
1.4 ! noro 142: \item $B%3%s%T%e!<%?$O7+$jJV$7(B, $B;n9T:x8m$,F@0U(B ($B$J$K$r$d$i$;$F$bJ86g$r8@$o$J$$(B)
1.1 noro 143: \end{itemize}
144: $B$H$$$&(B 2 $BE@$G$"$k(B. $BA0<T$O(B, $BCf4VCM$NDjM}$,<B?t$K$*$1$k6a;w$H(B
145: $B7k$SIU$$$?$h$&$K(B, $BB>$N%?%$%W$N6a;w$,;H$($J$$$+(B, $B$H$$$&$3$H$G$"$k(B.
146: $B8e<T$O(B, $B$=$N$h$&$J6a;w$r7+$jJV$7$FL\E*$NJ,2r$K6aIU$$$F$$$3$&(B, $B$H$$$&(B
147: $B$3$H$G$"$k(B.
148:
149: \section{$p$-$B?J6a;w$K$h$kB?9`<0$N0x?tJ,2r(B}
150:
151: $B$3$l$+$i=R$Y$kJ}K!$O(B, $B0x;R$N7A(B ($B<!?t(B)$B$r2>Dj$7$F(B, $B$=$N78?t$r6a;w$K(B
152: $B$h$j5a$a$F$$$/J}K!$G$"$k(B. $B$3$N>l9g$K;X?K$H$J$k86M}$O(B
153: $B!V@0?t(B $m$ $B$,(B 0 $\Leftrightarrow$ $m$ $B$O$I$s$J@0?t$G$b3d$j@Z$l$k!W(B
154: $B$H$$$&$b$N$G$"$k(B. $B$3$l$rMQ$$$F(B, $B$?$H$($P(B
155:
156: \begin{enumerate}
157: \item $B:G=i(B, $f(x)-g_1(x)h_1(x)$ $B$N78?t$,@0?t(B $p$ $B$G3d$j@Z$l$k$h$&$J(B $g_1$,
158: $h_1$ $B$r8+$D$1$k(B.
159:
160: \item $f(x)-g_k(x)h_k(x)$ $B$N78?t$,(B $p^k$ $B$G3d$j@Z$l$k$h$&$K(B $g_k$, $h_k$ $B$r(B
1.4 ! noro 161: $B=g<!:n$C$F$$$/(B ($k=2,3,\ldots$) --- $B$@$s$@$s!V@:EY!W$,>e$,$k(B
1.1 noro 162:
163: \item $g_1$, $h_1$ $B$,@52r$KBP1~$7$F$$$l$P(B, $BE,Ev$J(B $k$ $B$N$H$3$m$G$[$s$H$K3d$j@Z$l$k$@$m$&(B.
164: \end{enumerate}
1.3 noro 165: $B$H$$$&%?%$%W$N%"%k%4%j%:%`$r9=@.$9$k(B. $B8@$$$+$($k$H<!$N$h$&$K$J$k(B.
1.1 noro 166: $B0J2<(B, $B4JC1$N$?$a(B $f(x)$ $B$*$h$S$=$N0x;R$N78?t$OA4$F@5$G$"$k$H$9$k(B.
167: $B$^$:(B, $f(x)$ $B$N3F78?t$r(B $p$-$B?J?t$GI=$7(B, $B3F(B $p^k$ $B$4$H$K$^$H$a$F(B
168: $$f(x) = a_0(x)+p \cdot a_1(x)+p^2\cdot a_2(x)+\cdots$$
169: $B$H!V(B$p$ $B$K4X$7$F$Y$-5i?tE83+!W$9$k(B. ( $a_i(x)$ $B$N78?t$O(B 0 $B0J>e(B $p-1$ $B0J2<(B)
170: $B$3$l$KBP$7$F(B,
171: $$g(x) = b_0(x)+p\cdot b_1(x)+p^2\cdot b_2(x)+\cdots$$
172: $$h(x) = c_0(x)+p\cdot c_1(x)+p^2\cdot c_2(x)+\cdots$$
173: ($b_i$, $c_i$ $B$N78?t$O(B 0 $B0J>e(B $p-1$ $B0J2<(B)
174: $B$H$*$$$F(B $f(x)-g(x)h(x)=0$ $B$+$i(B $b_i$, $c_i$ $B$r(B, $B2<$+$i=g$K7h$a$F$$$/(B
175: $B$N$G$"$k(B.
176:
177: $B$3$3$G5-K!$r0l$DMQ0U$7$F$*$/(B. $M$ $B$r@0?t$H$9$k$H$-(B, $a \equiv b \bmod M$
178: $B$H$O(B,
179: \begin{itemize}
180: \item $a$, $b$ $B$,@0?t$N$H$-(B, $a-b$ $B$,(B $M$ $B$G3d$j@Z$l$k$3$H(B
181:
182: \item $a$, $b$ $B$,@0?t78?tB?9`<0$N$H$-(B, $a-b$ $B$N3F78?t$,(B $M$ $B$G3d$j@Z$l$k$3$H(B
183: \end{itemize}
184: $B$H$9$k(B. $B$^$?(B, $a$ $B$r(B $b$ $B$G3d$C$?M>$j$b(B $a \bmod M$ $B$H=q$/$3$H$K$9$k(B.
185:
186: $B$5$F(B, $B>e$N$h$&$K(B $g(x)$, $h(x)$ $B$N7A$r2>Dj$9$k$H(B
187: $$f-gh \equiv a_0-b_0c_0 \bmod p$$
188: $B$@$+$i(B, $f=gh$ $B$J$i(B $a_0 \equiv b_0c_0 \bmod p$ $B$N$O$:$G$"$k(B. $B$h$C$F(B, $B$3$l$r(B
189: $BK~$?$9(B $b_0$, $c_0$ $B$r5a$a$k$N$,Bh0lJb$H$J$k(B. $B0J2<$G$O(B,
190: $$f(x) =x^4+17056x^3+72658809x^2+3504023212x+30603759869$$
191: $B$N0x?tJ,2r$rNc$H$7$F@bL@$9$k(B. $p=3$ $B$H$9$k(B ($B$3$&$H$k$H0J2<$N7W;;$,$&$^$/$$$/(B)$B$H(B
192:
193: \noindent
194: $f(x)=(x^4+x^3+x+2)+
195: 3^1(x)+
196: 3^2(2x^3+x+2)+
197: 3^3(x^3+x^2+2x+2)+
198: 3^4(x^2+x+1)+
199: 3^5(x^3)+
200: 3^6(2x^3+x+2)+
201: 3^7(x^3+x^2+x)+
202: 3^8(2x^3+x^2+2x)+
203: 3^9(x^2+2x+1)+
204: 3^{11}(2x^2+x+1)+
205: 3^{12}(x^2+2x+1)+
206: 3^{13}(x+1)+
207: 3^{14} \cdot 2+
208: 3^{15}(2x^2+x+2)+
209: 3^{16}(x^2+2)+
210: 3^{17} \cdot 2+
211: 3^{19} \cdot 2+
212: 3^{20}(x+2)+
213: 3^{21} \cdot 2$
214:
215: $$a_0(x)=x^4+x^3+x+2$$
216: $B$G$"$k(B. $B$^$:(B, 1 $B<!0x;R$,$"$k$+$I$&$+$rD4$Y$F$_$k(B.
217: $$b_0(x) = x+q, c_0(x) = x^3+rx^2+sx+t$$ $B$H$*$/(B. $a_0 \equiv b_0c_0 \bmod 3$
218: $B$h$j(B\\
219:
220: $\left\{
221: \parbox[c]{6in}{
222: $q+r \equiv 1 \bmod 3$ \\
223: $qr+s \equiv 0 \bmod 3$ \\
224: $qs+t \equiv 1 \bmod 3$ \\
225: $qt \equiv 2 \bmod 3$}\\
226: \right.$\\
227:
228: $B$3$l$O(B $q,r,s,t$ $B$K4X$9$kO"N)9gF1<0$@$,(B, $q,r,s,t$ $B$K(B 0,1,2 $B$r$I$&F~$l(B
229: $B$F$bK~$?$5$l$J$$$3$H$+$i(B 1 $B<!0x;R$,$J$$$3$H$,J,$+$k(B. ($f(0)$,
230: $f(1)$, $f(2)$ $B$,(B 3 $B$G3d$j@Z$l$J$$$3$H$+$i$b$9$0$KJ,$+$k(B.)
231:
232: $B$D$.$O(B, 2 $B<!0x;R$NB8:_$rD4$Y$k(B.
233: $$b_0(x) = x^2+qx+r, c_0(x) = x^2+sx+t$$ $B$H$*$/(B. $a_0 \equiv b_0c_0 \bmod 3$
234: $B$h$j(B\\
235:
236: $\left\{
237: \parbox[c]{6in}{
238: $q+s \equiv 1 \bmod 3$ \\
239: $qs+r+t \equiv 0 \bmod 3$ \\
240: $qt+rs \equiv 1 \bmod 3$ \\
241: $tr \equiv 2 \bmod 3$}\\
242: \right.$\\
243:
244: $B:#EY$O(B, $$(q,r,s,t) = (0,1,1,2), (1,2,0,1)$$ $B$H$$$&2r$,8+$D$+$k(B. $B$3$l$O(B
245:
246: \centerline{$(b_0,c_0) = (x^2+1,x^2+x+2)$ $B$^$?$O(B $(x^2+x+2,x^2+1)$}
247:
248: \noindent
249: $B$r0UL#$9$k$,(B, $B$3$l$i$O%Z%"$H$7$F$OF1$8$b$N$G$"$k(B.
250: $b_0=x^2+1$, $c_0=x^2+x+2$ $B$H$9$k$H3N$+$K(B
1.3 noro 251: $f \equiv b_0c_0 \bmod 3$ $B$,@.$jN)$D(B.
1.1 noro 252: $B$b$H$N<0$KLa$k$H(B,
1.2 noro 253: $$gh \equiv (b_0+3b_1)(c_0+3c_1) \bmod 3^2$$ $B$h$j(B
1.1 noro 254: $$f-gh \equiv a_0-b_0c_0+3(a_1-(c_0b_1+b_0c_1)) \bmod 3^2$$
255: $a_0\equiv b_0c_0 \bmod 3$ $B$h$jN>JU$r(B 3 $B$G3d$k$H(B
256: $$(f-gh)/3 \equiv (a_0-b_0c_0)/3+(a_1-(c_0b_1+b_0c_1)) \bmod 3$$$B$5$F(B,
257: $B85!9:8JU$,(B 0 $B$K$J$k$h$&$K(B $g$, $h$ $B$r7h$a$?$$$N$@$+$i(B, $B1&JU(B $\equiv 0
258: \bmod 3$ $B$N$O$:$G$"$k(B. $B$h$C$F(B
259: $b_1$, $c_1$ $B$O(B
260: $$(a_0-b_0c_0)/3+(a_1-(c_0b_1+b_0c_1)) \equiv 0 \bmod 3$$
261: $B$rK~$?$9(B. $B$3$3$G(B, $g$, $h$ $B$N:G9b<!9`$O(B $x^2$ $B$H$7$F$h$$(B($BMW>ZL@(B)$B$+$i(B,
262: $BJd@59`$G$"$k(B $b_1$, $c_1$ $B$O0l<!<0$H$7$F$h$$(B. $B$h$C$F(B
263: $$b_1 = qx+r, c_1 = sx+t$$ $B$H$*$1$k(B. $B$9$k$H(B $a_1 = x$ $B$h$j(B
264: $$(a_0-b_0c_0)/3+(a_1-(c_0b_1+b_0c_1)) = -
265: (q+s)x^3-(q+r+t+1)x^2-(2q+r+s-1)x-(2r+t)$$
266: $B$h$j(B\\
267:
268: $\left\{
269: \parbox[c]{6in}{
270: $q+s \equiv 0 \bmod 3$ \\
271: $q+r+t+1 \equiv 0 \bmod 3$ \\
272: $2q+r+s-1 \equiv 0 \bmod 3$ \\
273: $2r+t \equiv 0 \bmod 3$}\\
274: \right.$\\
275:
276: \noindent
277: $B:#EY$OO"N)0l<!9gF1<0$G(B, $BMF0W$K2r$1$F(B
278:
279: \centerline{$(q,r,s,t) = (0,1,0,1)$ $B$9$J$o$A(B $b_1 = 1, c_1 = 1$}
280:
281: \noindent
282: $B$3$l$G(B $$f \equiv (b_0+3b_1)(c_0+3c_1) \bmod 3^2$$ $B$H$J$k(B $b_1$, $c_1$
1.3 noro 283: $B$,5a$^$C$?$3$H$K$J$k(B. $B<!$O(B $a_2$, $b_2$, $c_2$ $B$^$G$H$C$F(B $\bmod 3^3$ $B$G8+$H(B,
284: $$f \equiv a_0+3a_1+3^2a_2 \equiv (b_0+3b_1+3^2b_2)(c_0+3c_1+3^2c_2) \bmod 3^3$$
285: $B$h$j(B
286: $$((a_0+3a_1)-(b_0+3b_1)(c_0+3c_1))+3^2(a_2-(c_0b_2+b_0c_2)) \equiv 0 \bmod 3^3$$
287: ($3^3$ $B$G3d$j@Z$l$k9`$O<N$F$?(B.) $B@hF,ItJ,$O(B $3^2$ $B$G3d$j@Z$l$k$N$G(B,
288: $BN>JU$r(B $3^2$ $B$G3d$k$H(B
289: $$((a_0+3a_1)-(b_0+3b_1)(c_0+3c_1))/3^2+(a_2-(c_0b_2+b_0c_2)) \equiv 0 \bmod 3$$
1.4 ! noro 290: $b_2 = qx+r, c_2 = sx+t$ $B$H$*$/$H(B, $BA0$HF1MM$K(B $(q,r,s,t)$ $B$NO"N)0l<!(B
1.3 noro 291: $B9gF1<0$,F@$i$l$k(B.
292: $B0J2<F1MM$K(B $b_i = qx+r, c_i = sx+t$
1.4 ! noro 293: ($i=3,4,\ldots$) $B$H$*$$$F(B $(q,r,s,t)$ $B$NO"N)0l<!9gF1<0$r=g<!(B
1.1 noro 294: $B2r$$$F$$$1$P(B
295: $$f \equiv (b_0+\ldots+3^{k-1}b_{k-1})(c_0+\ldots+3^{k-1}c_{k-1\
296: }) \bmod 3^k$$
1.3 noro 297: $B$9$J$o$A(B$f \equiv g_kh_k \bmod 3^k$ $B$H$J$k(B $g_k$, $h_k$ $B$,7h$^$k(B.
1.1 noro 298: \begin{table}[hbtp]
299: \label{gh}
300: \begin{center}
301: \begin{tabular} { c | c c }
302: $k$ & $g_k$ & $h_k$ \\ \hline
303: 1&$x^2+1$&$x^2+x+2$\\ \hline
304: 2&$x^2+4$&$x^2+x+5$\\ \hline
305: 3&$x^2+18x+4$&$x^2+x+5$\\ \hline
306: 4&$x^2+45x+4$&$x^2+x+59$\\ \hline
307: 5&$x^2+45x+166$&$x^2+x+140$\\ \hline
308: 6&$x^2+531x+409$&$x^2+487x+626$\\ \hline
309: 7&$x^2+1260x+1867$&$x^2+487x+1355$\\ \hline
310: 8&$x^2+1260x+4054$&$x^2+2674x+1355$\\ \hline
311: 9&$x^2+7821x+10615$&$x^2+9235x+7916$\\ \hline
312: 10&$x^2+7821x+30298$&$x^2+9235x+47282$\\ \hline
313: 11&$x^2+7821x+89347$&$x^2+9235x+165380$\\ \hline
314: 12&{$x^2+7821x+89347$}&{$x^2+9235x+342527$}\\ \hline
315: 13&{$x^2+7821x+89347$}&{$x^2+9235x+342527$}\\ \hline
316: \end{tabular}
317: \caption{($g_k$, $h_k$)}
318: \end{center}
319: \end{table}
1.4 ! noro 320: $BI=(B 1 $B$O(B, $B$3$NA`:n$rB3$1$?$H$-$N(B, $B3F%9%F%C%W$K$*$1$k(B $g_k$, $h_k$ $B$r<($9(B.
1.1 noro 321: $BI=$G8+$k$H(B, $k = 12$ $B$+$i(B $k = 13$ $B$GJQ2=$,$J$$$3$H$,J,$+$k(B. $B<B:]$K(B
322: $f-g_{13}h_{13}$ $B$r7W;;$7$F$_$k$H(B 0 $B$G$"$k$3$H$,J,$+$k(B.
323: $B$9$J$o$A(B
324: $$f(x) = (x^2+7821x+89347)(x^2+9235x+342527)$$
325: $B$3$l$G0x?tJ,2r$,40N;$7$?(B. $B$3$3$G$O(B $B!V(B $\bmod p^k$$B$X$N;}$A>e$2!W$,(B
326: $B$=$N$^$^0x;R$H$J$C$?$,(B, $B<B:]$K$O(B
327: \begin{itemize}
328: \item $BIi$N78?t$rI|85$9$k$?$a$N9)IW(B
329: \item $k$ $B$r$I$3$^$G>e$2$l$P$h$$$+$H$$$&>e8B$N7W;;(B
330: \end{itemize}
331: $B$,I,MW$H$J$k(B.
332:
333: $B$3$3$G>R2p$7$?%"%k%4%j%:%`$N3F%9%F%C%W$G(B, $b_k$, $c_k$ $B$N78?t$K4X$9$k(B
334: $BO"N)J}Dx<0(B ($B9gF1<0(B) $B$,8=$l$?$,(B, $k>1$ $B$G$O0l<!J}Dx<0$G$"$j2r$/$N$O$d$5(B
335: $B$7$$(B. $BLdBj$O(B $k=1$ $B$N>l9g$G$"$k(B. $B$3$NJ}Dx<0$r(B, $BJQ?t$K$"$i$f$kCM$rF~$l(B
336: $B$F2r$/$H$$$&$N$O(B, $B%3%s%T%e!<%?$NG=NO$r9MN8$7$F$b$"$^$j$K$b8zN($,Dc(B
337: $B$$(B. $B$=$3$G(B, $a_0 \equiv b_0c_0 \bmod p$ $B$rK~$?$9(B$b_0$, $c_0$ $B$r5a$a$k(B
338: $BLdBj$r;kE@$rJQ$($F8+$k$3$H$K$9$k(B.
339:
340: \section{$BM-8BBN(B $GF(p) = \{0,1,\cdots,p-1\}$}
341:
342: $p$ $B$,AG?t$N$H$-(B, $GF(p) = \{0,1,\cdots,p-1\}$$B$K(B, $+$, $-$, $\times$
343: $B$r!V7k2L$r(B $p$ $B$G(B $B3d$C$?M>$j!W$GDj5A$9$k$H<!$,@.$jN)$D(B.
344: \begin{enumerate}
345: \item $B2C8:>h;;$GJD$8$F$$$k(B.
346:
347: $B$3$l$O<+L@$G$"$m$&(B.
348:
349: \item 0 $B0J30$N85$G3d;;$,$G$-$k(B.
350:
351: $B$3$l$O8@$$BX$($k$H(B
352: $B!V(B$a {\not \equiv} 0 \bmod p$ $B$J$i(B $ab \equiv 1 \bmod p$ $B$J$k(B $b$ $B$,$"$k!W(B
353: $B$H$$$&$3$H$G$"$k(B.
1.4 ! noro 354: $B!V(B$a$, $p$ $B$,8_$$$KAG$N$H$-@0?t(B $b$, $q$ $B$,B8:_$7$F(B $ab+pq=1$$B!W(B
1.1 noro 355: $B$H=q$1$P(B, $B8+$?$3$H$,$"$k$+$b$7$l$J$$(B. $B$3$l$O(B, $B%f!<%/%j%C%I$N8_=|K!$N(B
356: $BI{;:J*$H$7$FF@$i$l$k7k2L$G$"$k(B.
357: \end{enumerate}
358: $B$9$J$o$A(B, $GF(p)$ $B$OBN(B($B%?%$(B)$B$r$J$9(B.
359: $B85$N8D?t$,M-8B8D(B ($p$ $B8D(B)$B$J$N$GM-8BBN$H$h$V(B. $B$5$F(B, $a_0 \equiv f \bmod p$
360: $B$r(B $BBN(B $GF(p)$ $B$K78?t$r$b$D0lJQ?tB?9`<0$H8+$k$H(B, $a_0 \equiv b_0c_0 \bmod p$
361: $B$J$k(B $b_0$, $c_0$ $B$r5a$a$k$3$H$O(B, $GF(p)$ $B78?tB?9`<0$N0x?tJ,2r$r9T$&$3$H(B
362: $B$KAjEv$9$k(B. $B<B$O(B, $BM-8BBN>e$NB?9`<0$N0x?tJ,2r$K4X$7$F$O(B Berlekamp $B%"%k%4%j%:%`(B,
363: Cantor-Zassenhaus $B%"%k%4%j%:%`$H$$$C$?BgJQ8zN($N$h$$%"%k%4%j%:%`$,(B
364: $B9M0F$5$l$F$$$k(B. $B$^$?(B, $k > 1$ $B$K$D$$$F$b(B, $k=1$ $B$GF@$i$l$?(B $b_0$, $c_0$
365: $B$K(B, $GF(p)$ $B>e$GB?9`<0$KBP$9$k8_=|K!$rE,MQ$7$FF@$?(B $v_0b_0+w_0c_0=1$ $B$r(B
366: $BK~$?$9B?9`<0(B $v_0$, $w_0$ $B$r;H$C$F(B, $b_k$, $c_k$ $B$,5!3#E*$K7W;;$G$-$k(B.
367: $B0J>e$K$h$j(B, $B0x?tJ,2r%"%k%4%j%:%`(B (Zassenhaus $B%"%k%4%j%:%`(B) $B$O<!$N$h$&$K(B
368: $B$^$H$a$k$3$H$,$G$-$k(B.
369:
370: \begin{enumerate}
371: \item $B$h$$AG?t(B $p$ $B$rA*$s$G(B $f \bmod p$ $B$r0x?tJ,2r(B
372:
373: $B$3$3$G!V$h$$!W$H$$$&$N$ONc$($P<!$N$h$&$J$3$H$r0UL#$9$k(B.
374:
375: \begin{itemize}
376: \item $f$ $B$N:G9b<!78?t$r3d$i$J$$(B
377:
378: $GF(p)$ $B>e$G9M$($?$H$-$K<!?t$,JQ$o$i$J$$$h$&$K$9$k(B.
379:
380: \item $GF(p)$ $B$G$N0x;R$,A4$F0[$J$k(B
381:
382: $k > 1$ $B$GI,MW$H$J$k(B $v_0$, $w_0$ $B$,B8:_$9$k$?$a$KI,MW$J>r7o$G$"$k(B.
383:
384: \end{itemize}
385:
386: \item $f$ $B$N0x;R$N78?t$N>e8B$r7W;;$7(B, $p^k$ $B$,$=$l$h$j==J,Bg$-$/$J$k(B
387: $B$h$&$K(B $k$ $B$r7h$a$k(B.
388:
389: \item $B<!$r7+$jJV$7(B
390:
391: \begin{enumerate}
392: \item $GF(p)$ $B>e$N0x;R$rFsAH$KJ,$1$k(B.
393:
394: \item $B3FAH$N@Q$r(B $g_1$, $h_1$ $B$H$9$k(B.
395:
396: \item $f \equiv g_kh_k \bmod p^k$ $B$J$k(B $g_k$, $h_k$ $B$r:n$k(B
397:
398: \item $B78?t$N@5Ii$rD4@a$7$F;n$73d$j(B
399: \end{enumerate}
400: \end{enumerate}
401:
402: $B$3$3$G$O(B, $B$*$*$6$C$Q$K<jB3$-$N$_$r=R$Y$?$,(B, $B?t3XE*$K@5Ev2=$9$k$?$a$K$O(B
403: $B$5$^$6$^$J?t3XE*N"IU$1$,I,MW$H$J$k(B. $B:G$b:,K\E*$JLdBj$H$7$F(B, $BB?9`<0$N0x(B
404: $B?tJ,2r(B ($BM-M}?tBN>e(B, $BM-8BBN>e(B) $B$,0l0UE*$K$G$-$k$+$I$&$+$H$$$&LdBj$,$"$k(B.
405: $B$3$l$O(B, $BBN$N>e$G$NB?9`<0$N0x?tJ,2r$N0l0U@-$H$$$&0lHLO@$K$h$jJ]>Z$5$l$k(B.
406: $B$^$?(B, $BM-8BBN>e$N0x?tJ,2r%"%k%4%j%:%`<+?H(B, $B$=$3$GMQ$$$i$l$F$$$k<jK!$,$H(B
407: $B$F$b6=L#?<$$$,(B, $B$=$NM}2r$N$?$a$K$OBe?t3X$K$"$kDxEY=,=O$7$F$$$kI,MW$,$"(B
408: $B$k(B. $B$5$i$K(B, $\bmod p$ $B$+$i(B $\bmod p^k$ $B$X$N;}$A>e$2(B (lifting $B$H8F$V(B)
409: $B$O(B, Hensel $B$NJdBj$H$$$&=EMW$+$D0lHLE*$JDjM}$NFCJL$J>l9g$G$"$k(B. $B0J>e(B
410: $B$N$h$&$K(B, $BB?9`<0$N0x?tJ,2r$H$$$&Hf3SE*C1=c$=$&$K8+$($kA`:n$b(B, $B%3%s%T%e!<(B
411: $B%?$G<B9T$5$;$h$&$H;W$&$H(B, $B7W;;%Q%o!<$@$1$G$O;H$$$b$N$K$J$i$:(B, $B?t3X(B
412: $B$r$&$^$/;H$C$?%"%k%4%j%:%`@_7W$,I,MW$K$J$k$3$H$,J,$+$k(B.
413:
414: \section{$BM-8BBN$N1~MQNc(B : $B0E9f(B}
415:
416: $BA0@a$G(B, $BM-8BBN$H$$$&35G0$r>R2p$7$?$,(B, $B$3$3$G$OM-8BBN$,<B<R2q$K1~MQ$5$l(B
417: $B$F$$$kNc$H$7$F(B, $B0E9f$K$D$$$F=R$Y$k(B. $B:G=i$K=R$Y$?$h$&$K(B, $B%3%s%T%e!<%?$O(B
418: $B8=:_(B, $BDL?.<jCJ$H$7$F:G$b2Z!9$7$/MQ$$$i$l$F$$$k(B. $BDL?.$O%M%C%H%o!<%/$rDL(B
419: $B$8$F9T$o$l$k$,(B, $B%M%C%H%o!<%/$rDL$k%G!<%?$rBh;0<T$,K5<u$9$k2DG=@-$,$"$k(B.
420: $B$b$C$H8@$($P(B, $B%M%C%H%o!<%/>e$G$NDL?.$O4pK\E*$KE{H4$1$H;W$C$F$h$$(B. $B$3$N(B
421: $B$h$&$J>u67$G(B, $B%&%'%V>e$G$NGcJ*$K%/%l%8%C%H%+!<%I$NHV9f$J$I$r5$7Z$KF~NO(B
422: $B$7$FBg>fIW$J$N$@$m$&$+(B. $B<B$O(B, $B$3$l$KEz$($k$N$,(B, $BDL?.$N0E9f2=$G$"$k(B. $B0E(B
423: $B9f$K$O$5$^$6$^$JJ}<0$,$"$k$,(B, $BNc$($P<!$N$h$&$JJ}K!$,<B:]$KMQ$$$i$l$F$$(B
424: $B$k(B.
425:
426: \begin{enumerate}
427: \item $B0E9f2=(B/$BI|9f2=80$r6&M-$9$k(B.
428:
429: $B$3$3$G(B, $B80$H$$$&$N$O$"$kBg$-$5$N@0?t$H;W$C$F$h$$(B.
430:
431: \item $BAw?.B&$O80$G0E9f2=$7(B, $B<u?.B&$O80$GI|9f2=$9$k(B.
432:
1.2 noro 433: $B80$O0l$D$G0E9f2=(B/$BI|9f2=$K;H$&(B. $B$b$A$m$s(B, $B0E9f2=$K;H$C$?80$r;}$C$F$$(B
434: $B$J$1$l$PI|9f$G$-$J$$$h$&$J0E9fJ}<0$rMQ$$$k(B. $B$3$N$h$&$J0E9f$O(B
1.1 noro 435: $B6&DL800E9f$H8F$P$l$k(B.
436: \end{enumerate}
437: $B$3$3$GLdBj$,0l$D$"$k(B. $B0E9f2=$5$l$F$$$J$$(B, $BE{H4$1$NDL?.O)$r;H$C$F(B
438: $B$I$N$h$&$K80$r6&M-$9$k$N$@$m$&$+(B. $B$=$NJ}K!$N0l$D$,<!$N(B Diffie-Hellman
439: $B808r49%W%m%H%3%k$G$"$k(B.
440:
441: \begin{itemize}
442: \item {$B8x3+>pJs(B}
443:
444: $BBg$-$$AG?t(B $p$, $0 < g < p$ $B$J$k@0?t(B $g$
445:
446: \item {A $B$5$s$N;E;v(B}
447:
448: \begin{enumerate}
449: \item $0 < s_A < p$ $B$J$k@0?t(B {$s_A$} ($BHkL)(B) $B$r:n$k(B.
450: \item $w_A =$ {$g^{s_A} \bmod p$} $B$r(B B $B$5$s$KAw$k(B.
451: \item $B<u$1<h$C$?(B $w_B$ $B$+$i(B $s =$ {$w_B^{s_A} \bmod p$} $B$r:n$k(B.
452: \end{enumerate}
453:
454: \item {B $B$5$s$N;E;v(B}
455:
456: \begin{enumerate}
457: \item $0 < s_B < p$ $B$J$k@0?t(B {$s_B$} ($BHkL)(B) $B$r:n$k(B.
458: \item $w_B =$ {$g^{s_B} \bmod p$} $B$r(B A $B$5$s$KAw$k(B.
459: \item $B<u$1<h$C$?(B $w_A$ $B$+$i(B $s =$ {$w_A^{s_B} \bmod p$} $B$r:n$k(B.
460: \end{enumerate}
461: \end{itemize}
462: $B$3$N<j=g$,(B A $B$5$s(B, B $B$5$sAPJ}$G9T$o$l$k$H(B, A $B$5$s(B, B $B$5$s$O6&DL$N(B $s$ $B$H$$$&(B
463: $B%G!<%?$r<j$KF~$l$k(B. $B$3$l$O(B $w_B^{s_A} \equiv w_A^{s_B} \bmod p (\equiv g^{s_As_B} \bmod p)$ $B$+$iJ,$+$k(B.
464: $B$"$H$O(B $s$ $B$+$i6&DL$N<j=g$G80$r:n$l$P$h$$(B. $B$3$3$G(B, $w_A$, $w_B$ $B$O(B
465: $B0E9f2=$5$l$F$$$J$$$?$a(B, $BB>?M$,F~<j$9$k$3$H$b$"$jF@$k(B. $B$7$+$7(B, $s_A$, $s_B$
466: $B$5$(%P%l$J$1$l$P(B, $BBh;0<T$,(B $s$ $B$r:n$k$3$H$O$G$-$J$$(B. $B<B:](B,
467: $g^{s_A} \bmod p$ $B$+$i(B $s_A$ $B$r5U;;$9$kLdBj$O(B, $BM-8BBN$N>hK!72$K$*$1$k(B
468: $BN%;6BP?tLdBj$H$h$P$l(B, $p$ $B$,Bg$-$$$H7W;;$,:$Fq$G$"$k$H9M$($i$l$F$$$k(B.
469: $B$3$l$,(B, $w_A$, $w_B$ $B$r0E9f2=$9$kI,MW$,$J$$:,5r$H$J$C$F$$$k(B.
470:
471: $B$J$*(B, $B<j=gCf$K8=$l$k(B, $\overline{a^b} = a^b \bmod p$ $B$N7W;;(B($B$Y$->h>jM>(B
472: $B1i;;(B) $B$O(B, $BNc$($P<!$N$h$&$J<j=g$G7W;;$9$k$3$H$G(B, $p$ $BDxEY$NBg$-$5$N?t$N(B
473: $B$+$1;;(B, $B3d;;$N7+$jJV$7$K5"Ce$G$-$k(B.
474:
475: $\overline{a^{100}} = \overline{(\overline{a^{50}})^2}$,
476: $\overline{a^{50}} = \overline{(\overline{a^{25}})^2}$,
477: $\overline{a^{25}} = \overline{\overline{(\overline{a^{12}})^2}
478: \times \overline{a}}$,
479: $\overline{a^{12}} = \overline{(\overline{a^{6}})^2}$,
480: $\overline{a^{6}} = \overline{(\overline{a^{3}})^2}$,
481: $\overline{a^{3}} = \overline{\overline{(\overline{a})^2} \times \overline{a}}$
482:
483: $B$3$3$G=R$Y$?$b$N0J30$K$b(B, $BM-8BBN$r1~MQ$7$?0E9f$O$$$m$$$m$"$k(B. $BBeI=E*(B
484: $B$J$b$N$r(B 2 $B$D5s$2$k(B.
485: \begin{itemize}
486: \item RSA $B0E9f(B
487:
488: $BBg$-$J@0?t$NAG0x?tJ,2r$NFq$7$5$rMxMQ(B
489:
490: \item $BBJ1_6J@~0E9f(B
491:
492: $BM-8BBN>e$G(B $y^2=x^3+ax+b$ $B$N2r(B $P=(x,y)$ $B$r9M$($k$H(B,
493: $k$ $BG\;;(B $kP$ $B$,Dj5A$G$-$k(B.
494:
495: $kP$ $B$+$i(B $k$ $B$r5a$a$k7W;;$NFq$7$5$rMxMQ(B
496: \end{itemize}
497: $B$3$l$i$O<B:]$KDL?.$N0BA4@-$rJ]>Z$9$k$?$a$KMQ$$$i$l$F$$$k$,(B,
498: $B%3%s%T%e!<%?>e$G$O7k6I(B, $B@0?t$N2C8:>h=|$*$h$S$Y$->h>jM>1i;;$K(B
499: $B$h$j<B8=$5$l$F$$$k$N$G$"$k(B.
500:
501: \section{$B$^$H$a(B}
502:
503: $BK\9F$G$O(B, $B@0?t78?t$NB?9`<0$N0x?tJ,2r$r(B, $BM-8BBN78?t$NB?9`<0$N0x?tJ,2r(B(
504: $\bmod p$ $B$G$N0x?tJ,2r(B) $B$+$i(B Hensel lifting $B$H$h$P$l$kJ}K!$K$h$j(B$\bmod
505: p^k$ $B$G$N0x?tJ,2r$K;}$A>e$2$F(B, $B:G=*E*$K@0?t>e$N0x;R$rF@$k$H$$$&J}K!$r(B
506: $B>R2p$7$?(B. $B$=$N%"%k%4%j%:%`$O(B, $B=iEyE*$G$O$"$k$,?t3X$r$&$^$/;H$C$F8zN($h(B
507: $B$$B?9`<00x?tJ,2r$r2DG=$K$9$k(B. $B$^$?(B, $B$=$3$G8=$l$?M-8BBN$H$$$&BP>]$,(B, $BC1(B
508: $B$K?t3XE*$K6=L#$"$kBP>]$H$$$&$@$1$G$J$/(B, $B$5$^$6$^0E9f$r<B8=$9$k$?$a$KMQ(B
509: $B$$$i$l$F$$$k$3$H$b>R2p$7$?(B. $B%3%s%Q%/%H%G%#%9%/$N?.Mj@-$b(B, $BM-8BBN$rMQ$$(B
510: $B$?Id9f$G$"$k(B Reed-Solomon $BId9f$G;Y$($i$l$F$$$k$3$H$r9M$($l$P(B, $BM-8BBN$,(B
511: IT $B<R2q$rN"$G;Y$($F$$$k$H$$$C$F$b2a8@$G$O$J$$$@$m$&(B. $B?t3X$r@$$NCf$NLr(B
1.4 ! noro 512: $B$KN)$F$h$&(B, $B$J$I$H9M$($F$$$k?t3X<T$O$"$^$j$$$=$&$K$J$$$7(B, $B$^$?(B, $B$=$&(B
1.1 noro 513: $B$$$&$7$,$i$_$+$i<+M3$G$"$k$H$3$m$,?t3X$NH/E8$N8;@t$H$$$($k$N$+$b$7$l$J(B
514: $B$$(B. $B$7$+$7(B, $B$=$N$h$&$K$7$FF@$i$l$?7k2L$,(B, $B8e$GA[A|$b$D$+$J$$$H$3$m$G1~(B
515: $BMQ$5$l$k>l9g$b$"$k(B. $B$^$?(B, $B0lHL$K4w$_7y$o$l$k860x$H$J$k!VFq$7$5!W$,(B, $B0E(B
516: $B9f$N0BA4@-$N:,5r$H$J$k$H$$$&$N$b$*$b$7$m$$OC$G$"$j(B, $B7y$o$l$b$N$K4E$s$8(B
517: $B$J$,$i(B, $B<B$O$3$C$=$j@$$NCf$NLr$KN)$C$F$$$k$H$$$&(B, $B?t3X$N2{$N?<$5$rI=$7(B
1.4 ! noro 518:
1.1 noro 519: $B$F$$$k$H$$$&5$$,$9$k(B.
520:
521: \begin{thebibliography}{99}
522: \bibitem{KNUTH}
523: Knuth, D.E., The Art of Computer Programming, Vol. 2.
524: Seminumerical Algorithms, Third ed. Addison-Wesley (1998).
525:
526: \bibitem{NORO}
1.2 noro 527: $BLnO$(B, $B7W;;5!Be?t(B. Rokko Lectures in Mathematics 9, $B?@8MBg3XM}3XIt(B
1.1 noro 528: $B?t3X65<<(B (2001).
529:
530: \bibitem{ASIR}
1.4 ! noro 531: $BLnO$(B $BB>(B, $B7W;;5!Be?t%7%9%F%`(B Risa/Asir (1994-2001).
! 532:
! 533: {\tt ftp://archives.cs.ehime-u.ac.jp/pub/asir2000/}
1.1 noro 534: \end{thebibliography}
535:
536: $BK\9F$G=R$Y$?$3$H$O(B, $B<g$K%3%s%T%e!<%?$,CB@8$7$?8e$K9M0F$5$l$?J}K!$G(B, $BJ8(B
537: $B8%$O$=$&B?$/$J$$(B. \cite{KNUTH} $B$OBg$-$J@0?t$N1i;;(B, $B0x?tJ,2r$r4^$`0lJQ(B
538: $B?tB?9`<0$K4X$9$k%"%k%4%j%:%`$N%O%s%I%V%C%/E*$JK\$G$"$k(B. $BFbMF$OKDBg$@$,(B
539: $B5-=R$O6K$a$F@53N$G$"$k(B. \cite{NORO} $B$O$=$N$h$&$JK\$HHf$Y$i$l$k$b$N$G$O(B
540: $B$J$$$,(B, $BB?JQ?tB?9`<0$N0x?tJ,2r$*$h$SHs@~7AO"N)Be?tJ}Dx<0$N5a2r$K$D$$$F(B
541: $B$b>\$7$/=R$Y$F$$$k(B. $BB>$NJ88%$K$D$$$F$O(B, $B$3$l$i$NK\$NJ88%I=$r;2>H$7$F$[(B
542: $B$7$$(B. \cite{ASIR} $B$O%U%j!<$J7W;;5!Be?t%7%9%F%`(B($B?t<0=hM}%7%9%F%`(B)$B$G(B,
543: \cite{NORO} $B$K=q$+$l$?%"%k%4%j%:%`$O$[$\<BAu$5$l$F$$$k(B. $B<B:]$K$I$NDxEY(B
1.2 noro 544: $B;H$$$b$N$K$J$k$+;n$7$F$_$F$[$7$$(B.\\
1.1 noro 545:
1.2 noro 546: \noindent
547: {\large\bf $BG[I[(B CD $B$K$D$$$F(B}
548: \begin{enumerate}
549: \item
550: Windows $BHG(B Asir $B$K$O%$%s%9%H!<%i$,$"$j$^$;$s(B. $B$$$-$J$j5/F0$G$-$^$9(B.
551: Asir $B$r5/F0$9$k$K$O(B, CDROM $B>e$N(B $B%U%)%k%@(B {\tt asir} $B$r3+$-(B,$B$5$i$K(B {\tt
552: bin} $B%U%)%k%@$r3+$-(B {\tt asirgui} $B%"%$%3%s$r%@%V%k%/%j%C%/$7$^$9(B. $B%^(B
553: $B%K%e%"%k(B({\tt index.html}), $BF~Lg=q(B({\tt index-asir-book.html})$B$J$I$b(B
554: CDROM $B$K$$$l$F$"$j$^$9(B. Asir $B$N%[!<%`%Z!<%8$O(B, \\
555: {\tt http://www.math.kobe-u.ac.jp/Asir/asir.html} $B$G$9(B. {\tt asirgui} $B$O(B
556: $B%G%9%/%H%C%W$X%3%T!<$9$k$HF0$-$^$;$s(B. $B%^%$%I%-%e%a%s%H$X$N%3%T!<$O(B($BB?(B
557: $BJ,(B)$BBg>fIW$G$9(B. $B$?$@$7(B {\tt asir} $B%U%)%k%@A4BN$r%3%T!<$9$kI,MW$,$"$j$^(B
558: $B$9(B. ({\tt asirgui} $B$OF|K\8l$N%Q%9L>$,$"$k$H%H%i%V%k$r5/$3$90Y(B. $B%G%9(B
559: $B%/%H%C%W$OF|K\8l$N%Q%9L>$rMxMQ$7$F$$$k(B.)
560:
561: \item
562: Asir $B$O%^%7%sL>$,F|K\8l$N>l9g(B, $BF0:n$,$*$+$7$/$J$j$^$9(B.
563: $B<+J,$N%3%s%T%e!<%?$N%^%7%sL>$rD4$Y$k$K$O(B, $B%G%9%/%H%C%W$N(B
564: $B%M%C%H%o!<%/%3%s%T%e!<%?%"%$%3%s$r%/%j%C%/$7$F2<$5$$(B.
565: LAN $B$K@\B3$5$l$F$$$J$$>l9g$O(B, 1 $BBf$@$1%3%s%T%e!<%?$,I=<($5$l$^$9$,(B,
566: $B$=$NL>A0$,<+J,$N%3%s%T%e!<%?$NL>A0$G$9(B.
567:
568: \item
569: CDROM $B>e$N(B {\tt povwin3} $B$r%@%V%k%/%j%C%/$9$k$H(B, ray tracer povray $B$N(B
570: $B%$%s%9%H!<%k$,;O$^$j$^$9(B. povray $B$NF|K\8l$N@bL@=q$H$7$F$O(B, $B%"%9%-!<=P(B
571: $BHG6I$N!V(BPOV-Ray $B$G$O$8$a$k%l%$%H%l!<%7%s%0!W(B $B>.<<F|=P<yCx(B
572: (ISBN4-7561-1831-3) $B$,$"$j$^$9(B. \\
573: {\tt http://hp.vector.co.jp/authors/VA000449/pov/} $B$r$_$k$H(B povray $B$K$D$$$F(B
574: $B$N$$$m$s$J>pJs$rF@$k$3$H$,2DG=$G$9(B.
575:
576: \item
577: $B?@8MBg3X?t3X65<<$N(B web page $B$KCV$$$F$"$k(B, $B6JLL$N2hA|=8$r<}O?$7$F$"$j$^(B
578: $B$9(B.\\
579: {\tt web-math-kobe-u} $B%U%)%k%@$r3+$$$?$N$A(B, {\tt index.html} $B$r%@(B
580: $B%V%k%/%j%C%/$7$F(B,$BI=<($5$l$?%Z!<%8$N(B Mathematical Diversion $B$r3+$-$^$9!#(B
581: \end{enumerate}
1.1 noro 582: \end{document}
583:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to factor-resume.tex CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM / doc / sci-semi2001