Return to factorb.tex CVS log

Up to [local] / OpenXM / doc / sci-semi2001

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}