Annotation of OpenXM/doc/sci-semi2001/factorb.tex, Revision 1.1
1.1 ! noro 1: % $OpenXM$
! 2:
! 3: \Large
! 4: \parskip 0pt
! 5:
! 6: \begin{slide}{}
! 7: \fbox{\bf 1. $B$O$8$a$K(B}
! 8:
! 9: computer = compute $B$9$k$?$a$N$b$N(B
! 10:
! 11: compute = $B7W;;$9$k(B
! 12:
! 13: $B:G6a$G$O(B communication $B$N<jCJ$H$J$C$F$7$^$C$?(B
! 14:
! 15: $B$5$^$6$^$J>pJs$r%G%8%?%k2=(B ($BId9f2=(B) $B$7$F%M%C%H%o!<%/$rDL$7$FAw<u?.(B
! 16:
! 17: $\Rightarrow$ $B!V7W;;!W$K;H$C$F$$$k?M$O$4$/>/?t(B
! 18:
! 19: $BNc(B : email, $B%&%'%V(B $\cdots$ $B!V%$%s%?!<%M%C%H$9$k!W(B
! 20:
! 21: $B$7$+$7(B, $B7W;;5!$NG=NO$O0[MM$K8~>e(B
! 22:
! 23: $B7W;;$K;H$o$J$$$N$O$b$C$?$$$J$$(B($B$H;W$&(B)
! 24: \end{slide}
! 25:
! 26: \begin{slide}{}
! 27: \fbox{\bf 2. $B%3%s%T%e!<%?$K$D$$$F$N%$%m%O(B}
! 28:
! 29: \begin{itemize}
! 30: \item CPU
! 31:
! 32: $B%W%m%0%i%`$K=>$C$FL?Na$r<B9T(B
! 33:
! 34: \item $B%a%b%j(B
! 35:
! 36: $B%W%m%0%i%`(B, $B%G!<%?$rCV$/>l=j(B. $B>l=j(B ($BHVCO(B) $B$r;XDj$7$F9bB.$K=P$7F~$l$,$G$-$k(B.
! 37:
! 38: \item $B%l%8%9%?(B
! 39:
! 40: CPU $B$,;}$C$F$$$kFCJL$J%a%b%j$G(B, $B1i;;$NBP>]$K$J$k(B. $B?t$OB?$/$J$/(B, $BBg$-$5(B
! 41: ($BD9$5(B) $B$b>.$5$$(B.
! 42: \end{itemize}
! 43:
! 44: \end{slide}
! 45:
! 46: \begin{slide}{}
! 47: \underline{\bf $BL?Na$NNc(B}
! 48: \begin{itemize}
! 49: \item 10 $BHVCO$+$i(B 1 $B%P%$%HFI$s$G(B A $B%l%8%9%?$KF~$l$h(B
! 50: \item A, B $B%l%8%9%?$NCM$rB-$7$F(B C $B%l%8%9%?$KF~$l$h(B
! 51: \item A $B%l%8%9%?$NCM$,(B 0 $B$J$i(B 100 $BHVCO@h$KHt$Y(B
! 52: \end{itemize}
! 53:
! 54: \underline{\bf $B07$($k?t(B}
! 55:
! 56: $B%l%8%9%?$NBg$-$5$G07$($k?t$NHO0O$,7h$^$k(B.
! 57:
! 58: 32$B%S%C%H%l%8%9%?(B $\Rightarrow$ 0 $B$+$i(B $2^{32}-1$ $B$^$G$N@0?t$7$+07$($J$$(B
! 59:
! 60: \end{slide}
! 61:
! 62: \begin{slide}{}
! 63: \underline{\bf $B?t3X$K;H$&>l9g$r9M$($k$H(B...}
! 64:
! 65: $11111111111 \times 11111111111$
! 66:
! 67: $\Rightarrow 1332508849$ ??? (=$B7k2L$r(B $2^{32}$ $B$G3d$C$?M>$j(B)
! 68:
! 69: $B$+$H$$$C$F(B
! 70:
! 71: $11111111111 \times 11111111111$
! 72:
! 73: $\Rightarrow 1.234567 \times 10^{20}$
! 74:
! 75: $B$b:$$k(B
! 76:
! 77: $B8m:9$,F~$k$H?t3X$H$7$F$OL50UL#$J7W;;(B
! 78: \end{slide}
! 79:
! 80: \begin{slide}{}
! 81: \underline{\bf $B$H$j$"$($:Bg$-$J@0?t$O07$($J$$$H$$$1$J$$(B}
! 82:
! 83: $\Rightarrow$ $B%W%m%0%i%`$r=q$1$P$h$$(B
! 84:
! 85: $B%a%b%j>e$K@0?t$rJB$Y$F(B, $B%3%s%T%e!<%?$K!VI.;;!W$r$5$;$l$P$h$$(B
! 86:
! 87: \begin{itemize}
! 88: \item $B?M4V(B
! 89:
! 90: $B$R$H$1$?(B : 0 $B0J>e(B 9 $B0J2<(B
! 91:
! 92: \item $B%3%s%T%e!<%?(B
! 93:
! 94: $B$R$H$1$?(B : 0 $B0J>e(B $2^{32}-1$ $B0J2<(B
! 95: \end{itemize}
! 96: \end{slide}
! 97:
! 98: \begin{slide}{}
! 99: \underline{\bf $BNc(B : $B@0?t$NB-$7;;(B}
! 100:
! 101: \begin{tabular}{ccccc}
! 102: & 5 & 4001257187 & 1914644777 & (= $3^{42}$) \\
! 103: + & & 2830677074 & 689956897 & (= $3^{40}$) \\ \hline
! 104: & 6 & 2536966965 & 2604601674 &
! 105: \end{tabular}
! 106:
! 107: \underline{\bf $B0lJQ?tB?9`<0(B}
! 108:
! 109: $B3F<!?t$N78?t$rJB$l$P$h$$(B
! 110:
! 111: $\Rightarrow$ $B$3$l$G(B, $B@0?t78?t$NB?9`<0$r?t3XE*$K07$($k(B
! 112:
! 113: \end{slide}
! 114:
! 115: \begin{slide}{}
! 116: \fbox{\bf 3. $BB?9`<0$N0x?tJ,2r(B --- $BCf3X9b9;E*J}K!(B}
! 117:
! 118: \begin{enumerate}
! 119: \item $B4cNOK!(B ($B2r$H78?t$N4X78(B)
! 120:
! 121: $x^2+ax+b \Rightarrow$ $BB-$7$F(B $a$, $B$+$1$F(B $b$ $B$K$J$k?t$NAH(B
! 122:
! 123: $x^3+ax^2+bx+c$ $B$O$I$&$9$k(B?
! 124:
! 125: \item $B0x?tDjM}(B
! 126:
! 127: $BBeF~$7$F(B 0 $B$K$J$k?t$rC5$9(B ($B$I$&$d$C$FC5$9(B?)
! 128:
! 129: \item $B2r$N8x<0(B
! 130:
! 131: $x^2+ax+b$ $B$N:,(B ${-b \pm \sqrt{a^2-4b}} \over 2$
! 132:
! 133: $\Rightarrow$ $a^2-4b = t^2$ ($t$ : $B@0?t(B) $B$H$+$1$k$+$I$&$+D4$Y$k(B
! 134: \end{enumerate}
! 135: \end{slide}
! 136:
! 137: \begin{slide}{}
! 138: \underline{\bf $B4cNOK!$OLdBj$rFq$7$/$7$F$$$k(B}
! 139:
! 140: $BNc(B : $x^2+11508x+28386587$
! 141:
! 142: $28386587=3581\times 7927$ $B$,$a$N$3$GJ,$+$k?M$O>/$J$$(B($B$H;W$&(B)
! 143:
! 144: \underline{\bf $B2r$N8x<0K!$OM-K>(B}
! 145:
! 146: $(a^2-4b)/4 = 4717584 = 2172^2$ $B$J$i2?$H$+$J$k(B?
! 147:
! 148: $\Rightarrow$ $x^2-t$ $B$N@0?t:,$rC5$9J}K!$,$"$l$P$h$$(B
! 149: \end{slide}
! 150:
! 151: \begin{slide}{}
! 152: \underline{\bf 3 $B<!0J2<$N>l9g(B}
! 153:
! 154: \underline{\bf $B@0?t>e$GJ,2r$G$-$k$J$i(B, $B0l<!0x;R$r;}$D(B}
! 155:
! 156: $B:,$rC5$9J}K!$,E,MQ$G$-$k(B.
! 157:
! 158: $B:,5r(B : $BCf4VCM$NDjM}(B
! 159: $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
! 160:
! 161: \begin{itemize}
! 162: \item $BFsJ,K!(B
! 163:
! 164: $B6h4V$rH>J,$:$D69$a$FDI$$9~$`(B
! 165:
! 166: \item Newton $BK!(B
! 167:
! 168: $BFsJ,K!$h$j$:$C$H9bB.(B
! 169: \end{itemize}
! 170:
! 171: \end{slide}
! 172:
! 173: \begin{slide}{}
! 174: \underline{\bf 4 $B<!0J>e$N>l9g(B}
! 175:
! 176: $B$$$m$$$m$JJ,2r%Q%?!<%s$,$"$jF@$k(B
! 177:
! 178: 4 $B<!(B = 2 $B<!(B $\times$ 2 $B<!(B
! 179:
! 180: $\Rightarrow$ $B:,$rC5$9J}K!$OE,MQ:$Fq(B
! 181:
! 182: \underline{\bf $B%3%s%T%e!<%?MQ$K$O(B, $B$b$&>/$7E}0lE*$JJ}K!$,I,MW(B}
! 183:
! 184: $BCf4VCM$NDjM}$O(B, $B<B?t$K$*$1$k(B {\bf $B6a;w(B} $B$NMxMQ(B
! 185:
! 186: $BJL$N6a;w(B $\Rightarrow$ {\bf $B3d$C$?M>$j(B}$B$KCmL\(B
! 187: \end{slide}
! 188:
! 189: \begin{slide}{}
! 190: \fbox{\bf 4. $p$-$B?J6a;w$K$h$kB?9`<0$N0x?tJ,2r(B}
! 191:
! 192: \underline{\bf $B86M}(B} : {\bf $B@0?t(B $m$ $B$,(B 0} $\Leftrightarrow$
! 193:
! 194: {\bf $m$ $B$O$I$s$J@0?t$G$b3d$j@Z$l$k(B}
! 195:
! 196: ({\bf $m$ $B$O==J,Bg$-$$@0?t$G3d$j@Z$l$k(B})
! 197:
! 198: $B$?$H$($P(B,
! 199:
! 200: \begin{enumerate}
! 201: \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$,
! 202: $h_1$ $B$r8+$D$1$k(B.
! 203:
! 204: \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
! 205: $B:n$C$F$$$/(B ($k=1,2,\ldots$)
! 206:
! 207: \item $g_1$, $h_1$ $B$,Ev$?$j$J$i(B, $BE,Ev$J(B $k$ $B$N$H$3$m$G$[$s$H$K3d$j@Z$l$k$@$m$&(B.
! 208: \end{enumerate}
! 209: \end{slide}
! 210:
! 211: \begin{slide}{}
! 212: \underline{\bf $B8@$$$+$($l$P(B...}
! 213:
! 214: $B0J2<(B, $B4JC1$N$?$a(B, $f(x)$ $B$*$h$S0x;R$N78?t$OA4$F@5$G$"$k$H$9$k(B.
! 215:
! 216: $f(x) = a_0(x)+p\cdot a_1(x)+p^2\cdot a_2(x)+\cdots$
! 217:
! 218: $B$H!V$Y$-5i?tE83+!W$9$k(B. ( $a_i$ $B$N78?t$O(B $p-1$ $B0J2<(B)
! 219:
! 220: $g(x) = b_0(x)+p\cdot b_1(x)+p^2\cdot b_2(x)+\cdots$
! 221:
! 222: $h(x) = c_0(x)+p\cdot c_1(x)+p^2\cdot c_2(x)+\cdots$
! 223:
! 224: $B$H$*$$$F(B $f(x)-g(x)h(x)=0$ $B$+$i(B $b_i$, $c_i$ $B$r7h$a$k(B.
! 225: \end{slide}
! 226:
! 227: \begin{slide}{}
! 228: \underline{\bf $B5-9f(B $a \equiv b \bmod M$}
! 229:
! 230: $M$ $B$r@0?t$H$9$k(B. $a \equiv b \bmod M$ $B$H$O(B
! 231:
! 232: \begin{itemize}
! 233: \item $a,b$ $B$,@0?t$N$H$-(B,
! 234:
! 235: $a-b$ $B$,(B $M$ $B$G3d$j@Z$l$k$3$H(B
! 236:
! 237: \item $a,b$ $B$,@0?t78?tB?9`<0$N$H$-(B
! 238:
! 239: $a-b$ $B$N3F78?t$,(B $M$ $B$G3d$j@Z$l$k$3$H(B
! 240: \end{itemize}
! 241:
! 242: $a$ $B$r(B $M$ $B$G3d$C$?M>$j$b(B $a \bmod M$ $B$H=q$/(B
! 243: \end{slide}
! 244:
! 245: \begin{slide}{}
! 246: \underline{\bf$b_0(x)$, $c_0(x)$ $B$+$i%9%?!<%H(B}
! 247:
! 248: $f-gh = a_0-b_0c_0$ + ($p$$B$G3d$j@Z$l$kB?9`<0(B)
! 249:
! 250: $B$@$+$i(B, $f=gh$ $B$J$i(B $a_0 \equiv b_0c_0 \bmod p$ $B$N$O$:(B
! 251:
! 252: \underline{$BNc(B}
! 253:
! 254: \begin{tabbing}
! 255: $f(x)=$ \= $x^4+17056x^3+72658809x^2$ \\
! 256: \> $+3504023212x+30603759869$
! 257: \end{tabbing}
! 258:
! 259: $p = 3$ $B$H$9$k$H(B $a_0(x)=x^4+x^3+x+2$
! 260: \end{slide}
! 261:
! 262: \begin{slide}{}
! 263: \underline{\bf $B0l<!0x;R$,$"$k$+(B?}
! 264:
! 265: $b_0(x) = x+p$, $h_0(x) = x^3+qx^2+rx+s$ $B$H$*$/(B.
! 266:
! 267: $a_0 \equiv b_0c_0 \bmod 3$ $B$h$j(B\\
! 268:
! 269: $\left\{
! 270: \parbox[c]{6in}{
! 271: $p+q \equiv 1 \bmod 3$ \\
! 272: $pq+r \equiv 0 \bmod 3$ \\
! 273: $pr+s \equiv 1 \bmod 3$ \\
! 274: $ps \equiv 2 \bmod 3$}
! 275: \right.$\\
! 276:
! 277: $p$, $q$, $r$, $s$ $B$K(B 0, 1, 2 $B$r$I$&F~$l$F$b%@%a(B.
! 278:
! 279: $B$h$C$F(B, $B0l<!0x;R$O$J$$(B.
! 280:
! 281: \end{slide}
! 282:
! 283: \begin{slide}{}
! 284: \underline{\bf $BFs<!0x;R$O$"$k$+(B? --- $B$^$:(B $b_0$, $c_0$ $B$rC5$9(B}
! 285:
! 286: $b_0(x) = x^2+px+q$, $h_0(x) = x^2+rx+s$ $B$H$*$/(B
! 287:
! 288: $a_0 \equiv b_0c_0 \bmod 3$ $B$h$j(B\\
! 289:
! 290: $\left\{
! 291: \parbox[c]{6in}{
! 292: $p+r \equiv 1 \bmod 3$ \\
! 293: $pr+q+s \equiv 0 \bmod 3$ \\
! 294: $ps+qr \equiv 1 \bmod 3$ \\
! 295: $sq \equiv 2 \bmod 3$}
! 296: \right.$\\
! 297:
! 298: $p$, $q$, $r$, $s$ $B$K(B 0, 1, 2 $B$NCM$rF~$l$F$_$l$P(B
! 299:
! 300: $(p,q,r,s) = (0,1,1,2), (1,2,0,1)$ $B$,8+$D$+$k(B.
! 301:
! 302: $B0lJ}$,(B $b_0$, $BB>J}$,(B $c_0$ $B$H$_$J$;$P$3$l$i$OF1$8$b$N(B
! 303: \end{slide}
! 304:
! 305: \begin{slide}{}
! 306: \underline{\bf $BFs<!0x;R$D$E$-(B --- $b_1$, $c_1$ $B$,K~$?$9@-<A(B}
! 307:
! 308: $b_0 = x^2+1$, $c_0 = x^2+x+2$ $B$H$9$k$H(B
! 309:
! 310: \centerline{$f-b_0c_0 \equiv 0 \bmod 3$}
! 311:
! 312: $f-gh \equiv a_0-b_0c_0+p(a_1-(b_0c_1+b_1c_0)) \bmod 3^2$
! 313:
! 314: $B$h$j(B, $BN>JU$r(B 3 $B$G3d$C$F(B
! 315:
! 316: ${{f-gh} \over 3} \equiv {{a_0-b_0c_0}\over 3} + (a_1-(b_0c_1+b_1c_0)) \bmod 3$
! 317:
! 318: $B:8JU$O(B $3$ $B$G2?2s$G$b3d$l$k(B $\Rightarrow$ $B1&JU$O(B $3$ $B$G3d$l$k(B
! 319:
! 320: $BJd@59`(B $b_1$, $c_1$ : $x^2$ $B$N78?t$O(B 0 $B$H$7$F$h$$(B
! 321:
! 322: \end{slide}
! 323:
! 324: \begin{slide}{}
! 325: \underline{\bf $BFs<!0x;R$D$E$-(B --- $b_1$, $c_1$ $B$,K~$?$9J}Dx<0(B}
! 326:
! 327: $b_1 = px+q$, $c_1 = rx+s$ $B$H$*$/(B.
! 328:
! 329: \begin{tabbing}
! 330: $B1&JU(B = \= $-(p+r)x^3-(p+q+s+1)x^2$\\
! 331: \> $-(2p+q+r-1)x-(2q+s)$
! 332: \end{tabbing}
! 333:
! 334: $$B1&JU(B \equiv 0 \bmod 3$ $B$h$j(B\\
! 335:
! 336: $\left\{
! 337: \parbox[c]{6in}{
! 338: $p+r \equiv 0 \bmod 3$ \\
! 339: $p+q+s+1 \equiv 0 \bmod 3$ \\
! 340: $2p+q+r-1 \equiv 0 \bmod 3$ \\
! 341: $2q+s \equiv 0 \bmod 3$}
! 342: \right.$\\
! 343:
! 344: $B$3$s$I$OO"N)0l<!J}Dx<0(B($B9gF1<0(B). $B$3$l$r2r$/$H(B
! 345:
! 346: $(p,q,r,s) = (0,1,0,1)$ $B$9$J$o$A(B $b_1 = 1$, $c_1 = 1$
! 347:
! 348: \end{slide}
! 349:
! 350: \begin{slide}{}
! 351: \underline{\bf $BFs<!0x;R$D$E$-(B --- $b_k$, $c_k$ $B$bF1MM(B}
! 352:
! 353: $B$3$l$G(B,
! 354:
! 355: \centerline{$f \equiv (b_0+3b_1)(c_0+3c_1) \bmod 3^2$}
! 356:
! 357: $B0J2<F1MM$K(B,
! 358:
! 359: \centerline{$b_k = px+q, c_k = rx+s$}
! 360:
! 361: $B$H$*$$$F(B, $(p,q,r,s)$ $B$NO"N)0l<!J}Dx<0$r2r$1$P(B
! 362:
! 363: \centerline{$f \equiv (b_0+\ldots+3^{k-1}b_{k-1})(c_0+\ldots+3^{k-1}c_{k-1}) \bmod 3^k$}
! 364:
! 365: $B$9$J$o$A(B
! 366:
! 367: \centerline{$f \equiv g_kh_k \bmod 3^k$}
! 368:
! 369: $B$H$J$k(B $g_k, h_k$ $B$,7h$^$k(B.
! 370:
! 371: \end{slide}
! 372:
! 373: \begin{slide}{}
! 374: \underline{\bf $(g_k, h_k)$ $B$NI=(B}
! 375:
! 376: {\large
! 377: \begin{tabular} { c | c c }
! 378: $k$ & $g_k$ & $h_k$ \\ \hline
! 379: 1&$x^2+1$&$x^2+x+2$\\ \hline
! 380: 2&$x^2+4$&$x^2+x+5$\\ \hline
! 381: 3&$x^2+18x+4$&$x^2+x+5$\\ \hline
! 382: 4&$x^2+45x+4$&$x^2+x+59$\\ \hline
! 383: 5&$x^2+45x+166$&$x^2+x+140$\\ \hline
! 384: 6&$x^2+531x+409$&$x^2+487x+626$\\ \hline
! 385: 7&$x^2+1260x+1867$&$x^2+487x+1355$\\ \hline
! 386: 8&$x^2+1260x+4054$&$x^2+2674x+1355$\\ \hline
! 387: 9&$x^2+7821x+10615$&$x^2+9235x+7916$\\ \hline
! 388: 10&$x^2+7821x+30298$&$x^2+9235x+47282$\\ \hline
! 389: 11&$x^2+7821x+89347$&$x^2+9235x+165380$\\ \hline
! 390: 12&$x^2+7821x+89347$&$x^2+9235x+342527$\\ \hline
! 391: 13&$x^2+7821x+89347$&$x^2+9235x+342527$\\ \hline
! 392: \end{tabular}}
! 393: \end{slide}
! 394:
! 395: \begin{slide}{}
! 396: \underline{\bf $\bmod 3^k$ $B$G$N0x;R$+$i??$N0x;R$X(B}
! 397:
! 398: $BI=$G8+$k$H(B, $k=12$ $B$+$i(B $k=13$ $B$GJQ2=$,$J$$(B
! 399:
! 400: $\Rightarrow$ $f-g_{13}h_{13}$ $B$r7W;;$7$F$_$k$H(B 0 $B$K$J$C$F$$$k(B!
! 401:
! 402: $B$9$J$o$A(B
! 403:
! 404: $f(x) = $
! 405:
! 406: $(x^2+7821x+89347)(x^2+9235x+342527)$
! 407:
! 408: \underline{\bf $B<B:]$K$O(B...}
! 409:
! 410: \begin{itemize}
! 411: \item $BIi$N78?t$N>l9g$r07$&$?$a$N9)IW$,I,MW(B
! 412:
! 413: \item $B<:GT$N2DG=@-$b$"$k$N$G(B, $k$ $B$r$I$3$^$G>e$2$l$P$$$$$+$N>e8B$,I,MW(B
! 414: \end{itemize}
! 415: \end{slide}
! 416:
! 417: \begin{slide}{}
! 418: \underline{\bf $\bmod p$ $B$G$NJ,2r$,0lHVBg@Z(B}
! 419:
! 420: $B=P$FMh$?(B, $B78?t$NJ}Dx<0(B
! 421:
! 422: \begin{itemize}
! 423: \item $k > 1$
! 424:
! 425: $BC1$J$kO"N)0l<!J}Dx<0(B
! 426:
! 427: \item $k = 1$
! 428:
! 429: $B0l<!J}Dx<0$G$J$$(B $\Rightarrow$ $B$7$i$_$D$V$7$G2r$/$N$O$"$^$j$K8zN((B
! 430: $B$,$o$k$$(B ($B$$$/$i%3%s%T%e!<%?$G$b(B)
! 431: \end{itemize}
! 432: \end{slide}
! 433:
! 434: \begin{slide}{}
! 435: \fbox{\bf 5. $BM-8BBN(B $GF(p) = \{0,1,\cdots,p-1\}$ }
! 436:
! 437: $p$ $B$,AG?t$N$H$-(B,
! 438: $GF(p) = \{0,1,\cdots,p-1\}$ $B$K(B, $+$, $-$, $\times$ $B$r(B
! 439: $B!V7k2L$r(B $p$ $B$G(B $B3d$C$?M>$j!W$GDj5A$9$k$H(B
! 440:
! 441: \begin{enumerate}
! 442: \item $B2C8:>h;;$GJD$8$F$$$k(B.
! 443: \item 0 $B0J30$N85$G3d;;$,$G$-$k(B.
! 444:
! 445: $B!V(B$a {\not \equiv} 0 \bmod p$ $B$J$i(B $ab \equiv 1 \bmod p$ $B$H$J$k(B $b$ $B$,$H$l$k!W(B
! 446: \end{enumerate}
! 447:
! 448: $B$9$J$o$A(B, {\bf $GF(p)$ $B$OBN(B($B%?%$(B)}
! 449:
! 450: $B85$N8D?t$,M-8B8D(B ($p$ $B8D(B)$B$J$N$G(B {\bf $BM-8BBN(B} $B$H$h$V(B.
! 451:
! 452: \end{slide}
! 453:
! 454: \begin{slide}{}
! 455: \underline{\bf $k=1$ $B$G$N7W;;$O(B, $BM-8BBN>e$G$N0x?tJ,2r(B}
! 456:
! 457: $a_0 \equiv f \bmod p$ $B$r(B $GF(p)$ $B78?tB?9`<0$H$_$k(B.
! 458:
! 459: $\Rightarrow$ $a_0 \equiv b_0c_0 \bmod p$ $B$H$J$k(B $b_0$, $c_0$ $B$r(B
! 460: $B5a$a$k$3$H$O(B, $GF(p)$ $B>e$G$N0x?tJ,2r$KAjEv(B
! 461:
! 462: $\Rightarrow$ {\bf $B$h$$%"%k%4%j%:%`$,$?$/$5$s$"$k(B}
! 463:
! 464: \underline{\bf $k > 1$ $B$G$N7W;;$O(B, $BM-8BBN>e$G$NO"N)0l<!J}Dx<05a2r(B}
! 465:
! 466: $B<B:]$K$O(B, $k=1$ $B$N7k2L$+$i5!3#E*$K7W;;$G$-$k(B.
! 467: \end{slide}
! 468:
! 469: \begin{slide}{}
! 470: \underline{\bf $B0x?tJ,2r$N$^$H$a(B (Zassenhaus $B%"%k%4%j%:%`(B)}
! 471:
! 472: \begin{enumerate}
! 473: \item $B$h$$AG?t(B $p$ $B$rA*$s$G(B $f \bmod p$ $B$r0x?tJ,2r(B
! 474:
! 475: $f$ $B$N:G9b<!78?t$r3d$i$J$$(B
! 476:
! 477: $GF(p)$ $B$G$N0x;R$,A4$F0[$J$k(B etc.
! 478:
! 479: \item $B<!$r7+$jJV$7(B
! 480:
! 481: \begin{enumerate}
! 482: \item $GF(p)$ $B>e$N0x;R$rFsAH$KJ,$1$k(B
! 483:
! 484: \item $B3FAH$N@Q$r(B $g_1$, $h_1$ $B$H$9$k(B.
! 485:
! 486: \item $f \equiv g_kh_k \bmod p^k$ $B$J$k(B $g_k$, $h_k$ $B$r:n$k(B
! 487:
! 488: \item $B78?t$N@5Ii$rD4@a$7$F;n$73d$j(B
! 489: \end{enumerate}
! 490:
! 491: \end{enumerate}
! 492: \end{slide}
! 493:
! 494: \begin{slide}{}
! 495: \underline{\bf $BN"$K$O$$$m$$$m?t3X$,1#$l$F$$$k(B}
! 496:
! 497: \begin{itemize}
! 498: \item $BBN$N>e$G$N0x?tJ,2r$N0l0U@-(B
! 499:
! 500: $BBN>e$NB?9`<04D$N@-<A(B
! 501:
! 502: \item $BM-8BBN>e$G$N0x?tJ,2r%"%k%4%j%:%`(B
! 503:
! 504: Berlekamp $B%"%k%4%j%:%`(B
! 505:
! 506: \item $\bmod p$ $B$+$i(B $\bmod p^k$ $B$X$N;}$A>e$2(B
! 507:
! 508: Euclid $B$N8_=|K!(B, Hensel $B$NJdBj(B
! 509: \end{itemize}
! 510:
! 511: $\Rightarrow$ $B7W;;5!$N%Q%o!<$@$1$G$O%@%a(B. $B?t3X$r$&$^$/MxMQ$7$?(B
! 512: $B%"%k%4%j%:%`@_7W$,I,MW$H$$$&$3$H(B.
! 513:
! 514: \end{slide}
! 515:
! 516: \begin{slide}{}
! 517: \fbox{\bf 6. $BM-8BBN$N1~MQNc(B : $B0E9f(B}
! 518:
! 519: \underline{\bf $B%M%C%H%o!<%/>e$G$NDL?.$O4pK\E*$KE{H4$1(B}
! 520:
! 521: $B<+J,$N?H$O<+J,$G<i$k(B $\Rightarrow$ $BDL?.FbMF$r(B{\bf $B0E9f(B}$B2=(B
! 522:
! 523: \underline{\bf $B0E9f2=DL?.$N0lNc(B}
! 524:
! 525: \begin{enumerate}
! 526: \item $B6&DL$N0E9f2=(B/$BI|9f2=80$r6&M-$9$k(B.
! 527:
! 528: \item $BAw?.B&(B : $B80$G0E9f2=(B $\Rightarrow$ $B<u?.B&(B : $B80$GI|9f2=(B
! 529: \end{enumerate}
! 530:
! 531: \underline{\bf $BLdBj(B : $BDL?.O)$,E{H4$1$N$H$-$K(B, $B$I$&$d$C$F80$r6&M-(B?}
! 532: \end{slide}
! 533:
! 534: \begin{slide}{}
! 535: \underline{\bf A $B$5$s$H(B B $B$5$s$,80$r6&M-(B --- Diffie-Hellman}
! 536:
! 537: \begin{itemize}
! 538: \item $B8x3+>pJs(B
! 539:
! 540: $BBg$-$$AG?t(B $p$, $0 < g < p$ $B$J$k@0?t(B $g$
! 541:
! 542: \item A $B$5$s$N;E;v(B
! 543:
! 544: \begin{enumerate}
! 545: \item $0 < s_A < p$ $B$J$k@0?t(B $s_A$ ($BHkL)(B) $B$r:n$k(B.
! 546: \item $w_A = g^{s_A} \bmod p$ $B$r(B B $B$5$s$KAw$k(B.
! 547: \item $s = w_B^{s_A} \bmod p$ $B$r:n$k(B.
! 548: \end{enumerate}
! 549:
! 550: \item B $B$5$s$N;E;v(B
! 551:
! 552: \begin{enumerate}
! 553: \item $0 < s_B < p$ $B$J$k@0?t(B $s_B$ ($BHkL)(B) $B$r:n$k(B.
! 554: \item $w_B = g^{s_B} \bmod p$ $B$r(B A $B$5$s$KAw$k(B.
! 555: \item $s = w_A^{s_B} \bmod p$ $B$r:n$k(B.
! 556: \end{enumerate}
! 557:
! 558: \end{itemize}
! 559: \end{slide}
! 560:
! 561: \begin{slide}{}
! 562: \underline{\bf $BBg;v$JE@(B}
! 563:
! 564: \begin{itemize}
! 565: \item $w_B^{s_A} = w_A^{s_B} \bmod p$
! 566:
! 567: $B$3$l$G80$,6&M-$G$-$?(B
! 568:
! 569: \item $w_A$, $w_B$ $B$O0E9f2=$5$l$J$$(B
! 570:
! 571: $g^{s_A} \bmod p$ $B$+$i(B $s_A$ $B$r5a$a$k$N$OFq$7$$(B
! 572:
! 573: ($BM-8BBN$N>hK!72$K$*$1$kN%;6BP?tLdBj(B)
! 574:
! 575: \item $\overline{a^b} = a^b \bmod p$ $B$O(B $p$ $BDxEY$N?t$N$+$1;;3d;;$K5"Ce(B
! 576:
! 577: $\overline{a^{100}} = \overline{(\overline{a^{50}})^2}$,
! 578: $\overline{a^{50}} = \overline{(\overline{a^{25}})^2}$,
! 579: $\overline{a^{25}} = \overline{\overline{(\overline{a^{12}})^2} \times \overline{a}}$,
! 580: $\overline{a^{12}} = \overline{(\overline{a^{6}})^2}$,
! 581: $\overline{a^{6}} = \overline{(\overline{a^{3}})^2}$,
! 582: $\overline{a^{3}} = \overline{\overline{(\overline{a})^2} \times \overline{a}}$
! 583:
! 584: \end{itemize}
! 585: \end{slide}
! 586:
! 587: \begin{slide}{}
! 588: \underline{\bf $BB>$K$b$$$m$$$m$"$k(B}
! 589:
! 590: \begin{itemize}
! 591: \item RSA $B0E9f(B
! 592:
! 593: $BBg$-$J@0?t$NAG0x?tJ,2r$NFq$7$5$rMxMQ(B
! 594:
! 595: \item $BBJ1_6J@~0E9f(B
! 596:
! 597: $BM-8BBN>e$G(B $y^2=x^3+ax+b$ $B$N2r(B $P=(x,y)$ $B$r9M$($k$H(B,
! 598: $k$ $BG\;;(B $kP$ $B$,Dj5A$G$-$k(B.
! 599:
! 600: $kP$ $B$+$i(B $k$ $B$r5a$a$k7W;;$NFq$7$5$rMxMQ(B
! 601: \end{itemize}
! 602:
! 603: $\Rightarrow$ {\bf $B$$$:$l$b(B, $BD>@\(B, $B4V@\$K@0?t$N>jM>1i;;$,4XM?(B}
! 604: \end{slide}
! 605:
! 606: \begin{slide}{}
! 607: \fbox{\bf 7. $B$^$H$a(B}
! 608:
! 609: \begin{enumerate}
! 610: \item {\bf $BB?9`<00x?tJ,2rDxEY$G$b(B, $B8zN($h$$<B8=$OBgJQ(B}
! 611:
! 612: $B?t3X$,0U30$KLr$KN)$D(B $\cdots$ $BFC$KM-8BBN(B
! 613:
! 614: \item {\bf $B$G$bM-8BBN$J$s$FB>$K2?$NLr$KN)$D$N(B?}
! 615:
! 616: $B<B$O(B IT $B<R2q$rN"$G;Y$($F$$$k(B.
! 617:
! 618: \item {\bf $B?t3X$N1|?<$5(B}
! 619:
! 620: $B8e$K$J$C$F$H$s$G$b$J$$$H$3$m$K1~MQ$5$l$k2DG=@-$,$"$k(B
! 621: $B$H$$$&3Z$7$5(B, $B1|?<$5(B
! 622: \end{enumerate}
! 623:
! 624: \end{slide}
! 625:
! 626: %\begin{slide}{}
! 627: %\fbox{\bf}
! 628: %\end{slide}
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>