Return to factorb.tex CVS log

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

Annotation of OpenXM/doc/sci-semi2001/factorb.tex, Revision 1.6

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