Title 素数判定の決定的多項式時間アルゴリズム ( 代数的整数論とその周辺 ) Author(s) 木田, 雅成 Citation 数理解析研究所講究録 (2003), 1324: Issue Date URL

Size: px

Start display at page:

Download "Title 素数判定の決定的多項式時間アルゴリズム ( 代数的整数論とその周辺 ) Author(s) 木田, 雅成 Citation 数理解析研究所講究録 (2003), 1324: Issue Date URL"

のぶあきおおはし
5 years ago
Views:

2003-05 URL http://hdlhandlenet/2433/43143 Right Type

1 Title 素数判定の決定的多項式時間アルゴリズム ( 代数的整数論とその周辺 ) Author(s) 木田雅成 Citation 数理解析研究所講究録 (2003) 1324: Issue Date URL Right Type Departmental Bulletin Paper Textversion publisher Kyoto University

2 (Masanari Kida) (University of ElecctrO-Communications) Agrawal Kayal Saxena [1] AKS AKS 1 ( ) ( ) $\log N$ $\log N$ [11] AKS [5] 11 Miller-Rabin test (1980) 1([13][14]) $N$ $N-1=2^{s}\cdot d$ $(d 2)=1$ $\mathrm{a}$ $N$ $(\mathrm{a}n)=1$ $\mathrm{a}^{d}\not\equiv 1$ $(\mathrm{m}\mathrm{o}\mathrm{d} N)$ $\mathrm{a}^{2^{r}d}\not\equiv-1$ $(\mathrm{m}\mathrm{o}\mathrm{d} N)\forall r=0\ldotss-1$ (11) pu $N>1$ 1: $N-1=2^{s}d$ $(d2)=1$ $s$ $d$ 2: $\mathrm{a}\in[2n-2]$ 3: $b:=d(\mathrm{m}\mathrm{o}\mathrm{d} N)j$ 4: If or $b\neq 1$ $b\neq-1$ then 5: return cmposi$\mathrm{t}\mathrm{e}j$ $6$:end if 7: for $r=1$ to $s-1$ do

3 $\partial$ $\mathrm{t}\mathrm{l}\mathrm{c}$ $b:=b^{2}(\mathrm{m}\mathrm{o}\mathrm{d} n)j$ 8: 9: if $b\neq-1$ then 10: return composite; 11: end lf 12: end for 13: return probably prime; 7/ $N$ } probably prime 1/4 1/2 Miller-Rabin [11 PRIMES is $\mathrm{p}^{\cdot}$ in Dirichlet Riemann $L$ $N$ ( ) a $2(\log N)^{2}$ 2 for $\mathrm{a}=2$ to 2 $(\log N)^{2}$ do 12 Miller-Rabin test KASH PARI MAGMA $\mathrm{a}=23$ $17$ $\ldots$ 7 Miller-Rab test $n< $ [ [9] MAGMA A eman-pomerance-rumely (1983) $O((\log N)^{C\mathrm{l}\mathrm{o}\mathrm{g}\log\log N})$ Coldwasser-Kilian(1986) heuris- Adleman-Huang (1992) 2

4 24 2AKS AKS $q$ $r$ $s$ $N$ 2(Agrawal and Kayal and Saxena [11) $N$ 1 (1) $q (r-1)$ $()$ $N^{H_{q}}\not\in 0$ nor 1 $(\mathrm{m}\mathrm{o}\mathrm{d} (S) $N$ $s$ r)$ (4) $(\begin{array}{l}q+s-\mathrm{l}s\end{array})[succeq] N^{2[\sqrt{\eta}}$ $(x-\mathrm{a})^{n}\equiv x^{n}-\mathrm{a}(\mathrm{m}\mathrm{o}\mathrm{d} (N x^{\mathrm{r}}-1))$ (5) $\mathrm{a}=12$ $\ldotss$ 1 Bernstein [3] (1) $\frac{r-1}{q}$ $N$ $p$ $p^{\lrcorner r_{l}}\not\in 0$ nor 1 $(\mathrm{m}\mathrm{o}\mathrm{d} (2) r)$ (21) $jn^{j}$ $(0\leq lj\leq[\sqrt{\mathit{1}}\mathrm{j})$ $r$ $\exists(ij)$ $(\mathrm{j}j)\neq(kl)$ $(kl)\{$ \mathrm{r})$ $p^{l}n^{j}$ $(\mathrm{m}\mathrm{o}\mathrm{d} $u=p^{\iota}n^{j}$ $v= \oint N^{t}$ $u=v$ $(ij)\neq(kt)$ $N$ $p$ (i) (ii) $G=\langle g\rangle$ (1)#G>7S/[ (h) $g^{u}=g^{\gamma}$ $u=v$ (ii) $g^{\mathrm{u}-\gamma}=1$ $p^{l}m\leq\dot{n}^{+j}\leq N^{l[\sqrt{\eta}}$ u-\eta \leq N2[ (i) $u=v$ 2 $G$ $h(x)\in \mathrm{f}_{p}1x]$ $r$ $\frac{i-1}{\mathrm{x}-1}$ $\mathrm{m}\mathrm{o}\mathrm{d} p$ $G=\langle x-\mathrm{a} \mathrm{a}=12\ldotss\rangle\subset(\mathrm{f}_{p}[x]/(h(x)))^{\mathrm{x}}$

5 $\mathrm{a}$ $d\in[12$ $\mathrm{o}\mathrm{r}\mathrm{d}(p\mathrm{m}\mathrm{o}\mathrm{d} r)$ $G$ (i) (ii) $\mathrm{k}$ $\deg h=\mathrm{o}\mathrm{r}\mathrm{d}(p\mathrm{m}\mathrm{o}\mathrm{d} (1) (21) r)$ $q$ deg# $\geq q\geq 2$ $x-\mathrm{a}\neq \mathrm{o}$ in K $\ldotss$} $\mathrm{a}\neq d$ $x-\mathrm{a}=x-\#$ $\mathrm{f}_{p}[x]$ $\mu(\mathrm{a}-d)$ $s$ (3) $x-\mathrm{a}\neq x-d$ $\prod_{\mathrm{a}=1}^{s}(x-\mathrm{a})^{e}\cdot$ $( \sum_{\epsilon=1}^{s}e_{\delta}\leq q-1)$ (22) $\mathrm{k}$ $\mathrm{f}_{p}1x1$ $\mathrm{m}\mathrm{o}\mathrm{d} 7\mathrm{J}()$ degb $\geq q$ $\mathrm{f}_{p}[x1$ $x-\mathrm{a}$ (22) $G$ $(\begin{array}{l}q+s-\mathrm{l}s\end{array})$ (I) (ii) (4) $A=(\mathrm{Z}/N\mathrm{Z})[x]/(x^{r}-1)arrow B=\mathrm{F}_{p}[x]/(x^{\mathrm{r}}-1)arrow \mathrm{k}=\mathrm{f}_{p}[x]/(h(\triangleleft)$ $AB$ (5) $X$ $x^{n}$ $\mathrm{k}$ $(\mathrm{x}^{m}-\mathrm{a})^{n}\equiv \mathrm{x}^{w^{1}}-a$ $(\mathrm{m}\mathrm{o}\mathrm{d} P^{\mathrm{r}}-1)$ $\mathrm{t}p-\mathrm{a})^{n}=\mathrm{x}^{w^{1}}-\mathrm{a}$ $A$ $(\mathrm{x}-a)^{\mathcal{n}}=\theta-\partial$ in $A$ $p^{l}$ rnodp (X-a)\tilde =X -a $B$ $u$ $v$ $u\equiv v(\mathrm{m}\mathrm{o}\mathrm{d} r)$ $A$ $\mathrm{x}^{u}=\mathrm{x}^{\nu}$ in A $B$ $x^{r}=1$ ] $(x-\mathrm{a})^{u}=x^{u}-\mathrm{a}=x^{\nu}-\mathrm{a}=(\mathrm{x}-\mathrm{a})$ $\mathrm{k}$ $G$ $x-\mathrm{a}$ $g\in G$ $t=g^{\nu}$

6 26 3AKS algoriffim 2 Input: $N>1$ $1\mathrm{f}N=m^{k}$ 1: wiffi $k>1$ then compos$\mathrm{i}\mathrm{t}\mathrm{e}j$ 2: return $3$:end lf 4: for $r=2$ to $N-1$ do $1\mathrm{f}r1\mathrm{s}$ $\mathrm{u}^{-}r1\mathrm{s}$ 5: aptime aprlme then tnen $1\mathrm{f}r N$ 6: lf $r N$ ffien then 7: retum compositej 8: end if 9: $q:=$ ($r-1$ ) 10: $\ovalbox{\tt\small REJECT} N\text{ }\not\in 1(\mathrm{m}\mathrm{o}\mathrm{d}$ ffien 11: for $s=1$ to $q-1$ do 12: $1\mathrm{f}(\begin{array}{l}q+s-\mathrm{l}s\end{array})[succeq] N^{2[\mathrm{f}\sqrt{\mathrm{i}}}$ then 13: bre ; 14: end if 15: end for 16: end if 17: end if 18: end for 19: for to do $\mathrm{a}=1$ $s$ 20: lf in then $(x-\mathrm{a})^{n}\neq x^{n}-\partial$ $(\mathrm{z}/n\mathrm{z})[x]/(l-1)$ 21: return compositej 22: end if 23: end for 24: return prime; 1 3 $N$ 4 18 (5) $r$ $s$ $rs$ 8 $N$ $r$ $s\leq q\leq r$ (3) (5) $N$ Fermat

7 $\exists$ $\log N$ $r$ $\log N$ $\mathrm{k}\mathrm{s}$ $s\leq q-1\leq r-1$ $\log N$ $7^{\beta}$ T 3(Goldfeld [7] [2] ) $A$ $\delta>1/2$ $X$ $\#${$p p$ $x$ $p-1$ \nearrow } $\geq A\frac{X}{1\mathrm{o}\mathrm{g}\mathrm{x}}$ $\pi(x)$ 4 $X$ $B$ $\text{ }$ $X$ $s=[2[\sqrt{r}]\log_{2}n]+1$ $\pi(x)\leq B\frac{X}{1\mathrm{o}\mathrm{g}\mathrm{x}}$ 4 $B$ $A$ 4 $B$ 3 $\delta$ $q\geq 2s$ 3 $(\begin{array}{ll}q+s -\mathrm{l}s \end{array})>(\frac{q}{s})^{s}\geq 2^{s}\geq N^{2[\sqrt \mathrm{h}}$ (4) $q\geq 4\sqrt{r}\log_{2}N$ $s$ (4) 4 $\delta$ 5 A $k \geq\frac{2}{2\delta-1}$ (41) $c_{1}$ $c_{2}$ $r\in[c_{1}(\log N^{\mathrm{A}}$ $c_{2}(\log \mathrm{n}^{k}1$ : $\{$ $\varphi l)r-1\dagger \mathrm{j}q[succeq] 4\sqrt{r}\log_{2}N$ $\wp \mathit{2})" r\not\equiv 1r-1$ $(\mathrm{m}\mathrm{o}\mathrm{d} r)$ 1 $q$ $ \supset$ $\mathrm{p}(x)$ $X$ $\mathrm{p} (x)$ $X$ 3

8 $\exists$ $\gamma$ $(\mathrm{m}\mathrm{o}\mathrm{d} \mathrm{r})$ 28 $\#(\mathrm{p} (c_{2}(\log N)^{k})\cap[c_{1}(\log N)^{k} c_{2}(\log N)^{k}])\geq\#\mathrm{P} (c_{2}(\log N)\mathfrak{h}-\#\mathbb{P}(c_{1}(\log N)^{\mathrm{A}})$ $\geq\#\mathrm{p} (c_{2}(\log N)^{k})-\#\mathrm{P}(c_{1}(\log N)^{\mathrm{A}})$ ( J!i 3 $\text{ }4\text{ }$ ) $\geq\frac{ac_{2}(1\mathrm{o}\mathrm{g}n^{\mathrm{a}}}{1\mathrm{o}\mathrm{g}(c_{2}(\log N^{k})}-\frac{Bc_{1}(1\mathrm{o}\mathrm{g}N)^{k}}{1\mathrm{o}\mathrm{g}(c_{1}(\log N)^{k})}$ ( $c_{1}\geq 1$ $A\mathrm{c}_{2}(\log N^{k}$ $Bc_{1}(\log N^{k}$ ) $\geq\overline{\log(c_{2}(\log N^{k})}\overline{k\log(\log N)}-$ $N[^{\vee}$ ( $[succeq]$ ) $Ac_{2}(\log N)^{k}$ $Bc_{1}(\log N)^{\mathrm{A}}$ $\overline{(k+1)1o\mathrm{g}\log N}^{-}\overline{k\log 1o\mathrm{g}N}$ $=( \frac{ac_{2}}{k+1}-\frac{bc_{1}}{k})\frac{(1\mathrm{o}\mathrm{g}n)^{k}}{1\mathrm{o}\mathrm{g}1\mathrm{o}\mathrm{g}n}$ $c_{2}^{\delta-1/2} \geq\frac{4}{1o\mathrm{g}2}$ $ Cc_{2}$ $ \dot{\mathrm{a}}\text{ }\} $ 7xib(l) 0 0 $[] $ $c_{3}$ $\frac{k-1}{2k}>t[succeq] 1-\delta$ $t$ $\gamma=(n-1)(n^{2}-1)\ldots(n^{\triangleleft}-1)$ $M^{l1}$ $[x^{t}]$ $\gamma$ $\leq\gamma$ $\sim l\log M$ $=x^{2\mathrm{t}}\log N=\xi^{\mathrm{t}}(\log N)^{2\mathrm{f}\mathrm{f}+1}$ $<\xi^{t}(\log N)^{k}$ $\cdot$ $\frac{k-1}{2k}>\mathrm{t}$ $N$ T $c_{3} \frac{(1\mathrm{o}\mathrm{g}n)^{l}}{1\mathrm{o}\mathrm{g}1\mathrm{o}\mathrm{g}n}$ $\vee\supset$ 1 $\text{ }$ $\in[c_{1}(\log N)^{\mathrm{A}}$ $c_{2}(\log \mathrm{n}\eta)\{$ $\gamma\not\equiv 0$ $\mathrm{f}\mathrm{l}\lambda \mathfrak{f}$ $r-1$ E } ffl 3 \mbox{\boldmath $\tau$}

9 $=\mathrm{x}^{\mathrm{t}}$ $r-1$ $q$ $q\geq(c_{2}(\log N)^{\mathrm{A}})^{\delta}$ $4c^{1/2}$ $\geq\frac{2}{\log 2}(\log N)^{\mathrm{A}\delta}$ $\cdot$ $\cdot$ 3 $d_{2}^{-1/2}\geq 4/\log 2$ $4d^{/\mathrm{z}}$ $\geq\frac{2}{\log 2}(\log N)^{k/2+1}$ (41) $=4c_{2}^{1/2}(\log N)^{l/2}\log_{2}N$ $\geq 4\sqrt{r}\log_{2}N$ $\cdot$ $c_{2}(\log N)^{k}\geq r$ (P1) $\frac{\mathrm{r}-1}{q}\leq\frac{c_{2}(1\mathrm{o}\mathrm{g}n^{k}}{(c_{2}(1\mathrm{o}\mathrm{g}n^{k})^{\delta}}$ $=(c_{2}(\log N)\mathfrak{h}^{1-\delta}$ $\leq(c_{2}(\log N)^{\mathrm{A}})^{t}$ $1-\delta\leq t$ $\gamma\not\equiv (P2) $\mathrm{o}\mathrm{k}$ 0(\mathrm{m}\mathrm{o}\mathrm{d} r)$ $r$ $(\log N)^{k}$ $s$ $q$ 6 (41) 3 $k$ $\delta$ $\delta$ Fouvry [61 $\delta=06683$ $(\log N)^{k/2+1}$ $\delta=\frac{2}{3}\prime t=\frac{1}{3}$ $k=6$ (42) (4) $rs$ $r$ $s$ T

10 and $O((1o\mathrm{g}N)^{\xi \mathrm{r}+4})$ 7 $AKS$ 19 $(\mathrm{x}-\epsilon)^{n}\mathrm{m}\mathrm{o}\mathrm{d} (\mathrm{x}^{r}-1n)$ $\mathrm{z}/n\mathrm{z}[\mathrm{x}]$ $r$ $O(\log N)$ $\mathrm{z}/n\mathrm{z}[\mathrm{x}]$ $r$ FFT FFT $O(d)$ $O(r(\log N^{\epsilon})$ $\mathrm{z}/n\mathrm{z}$ FFT $\mathrm{z}/n\mathrm{z}$ FFT $O((\log N^{2})$ $O((\log N^{1+\epsilon})$ $O((1o\mathrm{g}N)^{u2+1}\cdot$ $\log N\cdot(\log N^{2})$ $r$ $\mathrm{o}((\log N)\mathrm{I}^{l+4})$ (FFT N^{\S k+3+\epsilon_{\square }}))$ $O$(($\log$ A) (42) $O((\log N)^{12+\epsilon}))$ [1] $O((\log N^{\epsilon+\epsilon})$ FFT(Fast Fourier Transform) [5] 0 $((\log $O((\log N^{19})$ ($\mathrm{f}\mathrm{f}\gamma$ Sophie Germain 52 [4] Allan K Steel MAGMA Bernstein $r$ NextPrime $\mathrm{i}\mathrm{i}\mathrm{i}866\mathrm{m}\mathrm{h}\mathrm{z}$ Mobile Pentium $\succ \mathrm{a}\mathrm{k}\mathrm{s}(1\theta\phi 003)j$ $\mathrm{r}=1187$ $\mathrm{s}=545$ $\mathrm{r}$ Selection of Final loop:9365 true $>\mathrm{a}\mathrm{k}\mathrm{s}(10000\theta 3)\cdot$ $\mathrm{r}=1619\mathrm{s}=793$ and $\mathrm{s}:657$ $\mathrm{r}$ $\mathrm{s}$ Selection of :1221 Final loop:214429

11 philasdf 31 true $>\mathrm{a}\mathrm{k}\mathrm{s}(1\emptyset \mathrm{q}\mathrm{q}\mathrm{q}\mathrm{q}19)j$ $\mathrm{r}=2207$ $\mathrm{s}=$ lq45 and $\mathrm{s}:2337$ $\mathrm{r}$ Selection of Final loop: true AKS [1] M Agrawal N Kayal and N Saxena PRIMES is $lnp$ Preprint (2002) http: $//\mathrm{w}\mathrm{w}\mathrm{w}\mathrm{c}\mathrm{s}\mathrm{e}$ iitk $\mathrm{a}\mathrm{c}\mathrm{i}\mathrm{n}/\mathrm{n}\mathrm{e}\mathrm{w}\mathrm{s}/\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{m}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{t}\mathrm{y}$html [2] R C Baker and G Harman The Brun-Titchmarsh theorem on average Analytic number theory Vol 1(Allerton Park IL 1995) Progr Math vol 138 Birkh\"auser Boston Boston MA 1996 pp [31 D J Bemsteln An exposition of the Agrawal-Kayal-Saxena $phmali\psi$-proving theorem Poeprint (2002) hrrp: $//\mathrm{c}\mathrm{r}\mathrm{y}\mathrm{p}\mathrm{t}\mathrm{o}/\mathrm{p}\mathrm{a}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{s}/\mathrm{a}\mathrm{k}\mathrm{s}$ps [41 P Cramody Links to things relevant to the $AKS$ algorithms $//\mathrm{f}\mathrm{a}\mathrm{t}$ $\mathrm{o}\mathrm{r}\mathrm{g}/\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{h}\mathrm{s}/\mathrm{a}\mathrm{k}\mathrm{s}$ hrrp: [51 R Crandall and C Pomerance Prime numbers $-A$ computational perspective Springer-Verlag New York 2001 [61 ] $:$ Fouvry Thior\ eme de Bmn-Tifchmarsh: application au th($r&me de Fermat Invent Math 79 (1985) no [71 M Goldfeld On the number of primes $p$ for whfcll $p+\partial$ has alarge prime fictor Mathematika 16 (1969) [81 S Goldwasser and J Kilian Primality testing using ellipfic curves J ACM 46 (1999) no [91 C Jaeschke On strongpseudoprimes to several bases Math Comp 61 (1993) no [101 A Klappenecker The test results from analytic number theory $AKSprlm\epsilon lliy$ tamu edu/klappi/629/ana1ytic pdf http: $//\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{u}\mathrm{l}\mathrm{t}\mathrm{y}\mathrm{c}\mathrm{s}$ [11] N Koblitz Algebraicaspects ofcryptography Algorithms and Computatlon in MathemaUcs vol 3 Springer-Verlag Berlin 1998 With an appendix by Alfred J Menezes Yi-Hong Wu and Robert J Zuccherato [121 P Luschny $AKS$ $\mathrm{v}$ a deterministic primary test Maple program http: $//\mathfrak{m}[] \mathrm{w}$ luschny $\mathrm{d}\mathrm{e}/\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{h}/\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{m}\mathrm{e}\mathrm{s}/\mathrm{a}\mathrm{k}\mathrm{s}$txt

12 mcgill 32 $\dot{s}$ [131 G L Miller Riemann hypothesis and tests for primality J Comput System Sci 13 (1976) no Working papers presented at the ACM-SIGACT Symposium on the Theory of Computing (Albuquerque NM 1975) [141 M O Rabin Probabilistic algorithm for testlngprimality J Number Theory 12 (1980) no [151 ( ) [161 A Stiglic The PRIIIES is in $P$ little $FAQ$ http: $//\mathrm{c}\mathrm{r}\mathrm{y}\mathrm{p}\mathrm{t}\mathrm{o}\mathrm{c}\mathrm{s}$ $\mathrm{c}\mathrm{a}/\sim \mathrm{s}\mathrm{t}\mathrm{i}\mathrm{g}\mathrm{l}\mathrm{i}\mathrm{c}/\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{n}\mathrm{e}\mathrm{s}p\mathrm{j}\mathrm{a}\mathrm{q}$ html [17] PRIN ES in $P-$-the $ls$ $aks$ primality testing JANT8 $\mathrm{u}\mathrm{e}\mathrm{c}\mathrm{a}\mathrm{c}\mathrm{j}\mathrm{p}/\mathrm{j}\mathrm{a}\mathrm{n}\mathrm{t}/\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{m}08$ html http: $//\mathrm{n}\mathrm{t}\mathrm{w}\mathrm{e}$-one ( $\mathrm{e}$-mall:ldda@sugal(u $\mathrm{e}$-one ) $\mathrm{u}\mathrm{e}\mathrm{c}$acjp

$\mathrm{v}$ ( )* $1$ $\ovalbox{\tt\small REJECT}2$ \searrow $\mathrm{b}$ $3$ $4$ ( ) [1] $*5$ $\mathrm{a}\mathrm{c}

$$\mathrm{v}$ ( )* $*1$ $\ovalbox{\tt\small REJECT}*2$ \searrow $\mathrm{b}$ $*3$ $*4$ ( ) [1] $*5$ $\mathrm{a}\mathrm{c}$ Title 狩野本綴術算経について ( 数学史の研究 ) Author(s) 小川束 Citation 数理解析研究所講究録 (2004) 1392: 60-68 Issue Date 2004-09 URL http://hdlhandlenet/2433/25859 Right Type Departmental Bulletin Paper Textversion publisher Kyoto