\(\newcommand{\footnotename}{footnote}\)
\(\def \LWRfootnote {1}\)
\(\newcommand {\footnote }[2][\LWRfootnote ]{{}^{\mathrm {#1}}}\)
\(\newcommand {\footnotemark }[1][\LWRfootnote ]{{}^{\mathrm {#1}}}\)
\(\newcommand \ensuremath [1]{#1}\)
\(\newcommand {\LWRframebox }[2][]{\fbox {#2}} \newcommand {\framebox }[1][]{\LWRframebox } \)
\(\newcommand {\setlength }[2]{}\)
\(\newcommand {\addtolength }[2]{}\)
\(\newcommand {\setcounter }[2]{}\)
\(\newcommand {\addtocounter }[2]{}\)
\(\newcommand {\cline }[1]{}\)
\(\newcommand {\directlua }[1]{\text {(directlua)}}\)
\(\newcommand {\luatexdirectlua }[1]{\text {(directlua)}}\)
\(\newcommand {\protect }{}\)
\(\def \LWRabsorbnumber #1 {}\)
\(\def \LWRabsorbquotenumber "#1 {}\)
\(\def \mathchar {\ifnextchar "\LWRabsorbquotenumber \LWRabsorbnumber }\)
\(\def \mathcode #1={\mathchar }\)
\(\let \delcode \mathcode \)
\(\let \delimiter \mathchar \)
\(\let \LWRref \ref \)
\(\renewcommand {\ref }{\ifstar \LWRref \LWRref }\)
\(\newcommand {\intertext }[1]{\text {#1}\notag \\}\)
\(\newcommand {\mathllap }[2][]{{#1#2}}\)
\(\newcommand {\mathrlap }[2][]{{#1#2}}\)
\(\newcommand {\mathclap }[2][]{{#1#2}}\)
\(\newcommand {\mathmbox }[1]{#1}\)
\(\newcommand {\clap }[1]{#1}\)
\(\newcommand {\LWRmathmakebox }[2][]{#2}\)
\(\newcommand {\mathmakebox }[1][]{\LWRmathmakebox }\)
\(\newcommand {\cramped }[2][]{{#1#2}}\)
\(\newcommand {\crampedllap }[2][]{{#1#2}}\)
\(\newcommand {\crampedrlap }[2][]{{#1#2}}\)
\(\newcommand {\crampedclap }[2][]{{#1#2}}\)
\(\newenvironment {crampedsubarray}[1]{}{}\)
\(\newcommand {\crampedsubstack }{}\)
\(\newcommand {\smashoperator }[2][]{#2\limits }\)
\(\newcommand {\adjustlimits }{}\)
\(\newcommand {\SwapAboveDisplaySkip }{}\)
\(\require {extpfeil}\)
\(\Newextarrow \xleftrightarrow {10,10}{0x2194}\)
\(\Newextarrow \xLeftarrow {10,10}{0x21d0}\)
\(\Newextarrow \xhookleftarrow {10,10}{0x21a9}\)
\(\Newextarrow \xmapsto {10,10}{0x21a6}\)
\(\Newextarrow \xRightarrow {10,10}{0x21d2}\)
\(\Newextarrow \xLeftrightarrow {10,10}{0x21d4}\)
\(\Newextarrow \xhookrightarrow {10,10}{0x21aa}\)
\(\Newextarrow \xrightharpoondown {10,10}{0x21c1}\)
\(\Newextarrow \xleftharpoondown {10,10}{0x21bd}\)
\(\Newextarrow \xrightleftharpoons {10,10}{0x21cc}\)
\(\Newextarrow \xrightharpoonup {10,10}{0x21c0}\)
\(\Newextarrow \xleftharpoonup {10,10}{0x21bc}\)
\(\Newextarrow \xleftrightharpoons {10,10}{0x21cb}\)
\(\newcommand {\LWRdounderbracket }[3]{\underset {#3}{\underline {#1}}}\)
\(\newcommand {\LWRunderbracket }[2][]{\LWRdounderbracket {#2}}\)
\(\newcommand {\underbracket }[1][]{\LWRunderbracket }\)
\(\newcommand {\LWRdooverbracket }[3]{\overset {#3}{\overline {#1}}}\)
\(\newcommand {\LWRoverbracket }[2][]{\LWRdooverbracket {#2}}\)
\(\newcommand {\overbracket }[1][]{\LWRoverbracket }\)
\(\newcommand {\LATEXunderbrace }[1]{\underbrace {#1}}\)
\(\newcommand {\LATEXoverbrace }[1]{\overbrace {#1}}\)
\(\newenvironment {matrix*}[1][]{\begin {matrix}}{\end {matrix}}\)
\(\newenvironment {pmatrix*}[1][]{\begin {pmatrix}}{\end {pmatrix}}\)
\(\newenvironment {bmatrix*}[1][]{\begin {bmatrix}}{\end {bmatrix}}\)
\(\newenvironment {Bmatrix*}[1][]{\begin {Bmatrix}}{\end {Bmatrix}}\)
\(\newenvironment {vmatrix*}[1][]{\begin {vmatrix}}{\end {vmatrix}}\)
\(\newenvironment {Vmatrix*}[1][]{\begin {Vmatrix}}{\end {Vmatrix}}\)
\(\newenvironment {smallmatrix*}[1][]{\begin {matrix}}{\end {matrix}}\)
\(\newenvironment {psmallmatrix*}[1][]{\begin {pmatrix}}{\end {pmatrix}}\)
\(\newenvironment {bsmallmatrix*}[1][]{\begin {bmatrix}}{\end {bmatrix}}\)
\(\newenvironment {Bsmallmatrix*}[1][]{\begin {Bmatrix}}{\end {Bmatrix}}\)
\(\newenvironment {vsmallmatrix*}[1][]{\begin {vmatrix}}{\end {vmatrix}}\)
\(\newenvironment {Vsmallmatrix*}[1][]{\begin {Vmatrix}}{\end {Vmatrix}}\)
\(\newenvironment {psmallmatrix}[1][]{\begin {pmatrix}}{\end {pmatrix}}\)
\(\newenvironment {bsmallmatrix}[1][]{\begin {bmatrix}}{\end {bmatrix}}\)
\(\newenvironment {Bsmallmatrix}[1][]{\begin {Bmatrix}}{\end {Bmatrix}}\)
\(\newenvironment {vsmallmatrix}[1][]{\begin {vmatrix}}{\end {vmatrix}}\)
\(\newenvironment {Vsmallmatrix}[1][]{\begin {Vmatrix}}{\end {Vmatrix}}\)
\(\newcommand {\LWRmultlined }[1][]{\begin {multline*}}\)
\(\newenvironment {multlined}[1][]{\LWRmultlined }{\end {multline*}}\)
\(\let \LWRorigshoveleft \shoveleft \)
\(\renewcommand {\shoveleft }[1][]{\LWRorigshoveleft }\)
\(\let \LWRorigshoveright \shoveright \)
\(\renewcommand {\shoveright }[1][]{\LWRorigshoveright }\)
\(\newenvironment {dcases}{\begin {cases}}{\end {cases}}\)
\(\newenvironment {dcases*}{\begin {cases}}{\end {cases}}\)
\(\newenvironment {rcases}{\begin {cases}}{\end {cases}}\)
\(\newenvironment {rcases*}{\begin {cases}}{\end {cases}}\)
\(\newenvironment {drcases}{\begin {cases}}{\end {cases}}\)
\(\newenvironment {drcases*}{\begin {cases}}{\end {cases}}\)
\(\newenvironment {cases*}{\begin {cases}}{\end {cases}}\)
\(\newcommand {\MoveEqLeft }[1][]{}\)
\(\def \LWRAboxed #1!|!{\fbox {\(#1\)}&\fbox {\(#2\)}} \newcommand {\Aboxed }[1]{\LWRAboxed #1&&!|!} \)
\( \newcommand {\LWRABLines }[1][\Updownarrow ]{#1 \notag \\}\newcommand {\ArrowBetweenLines }{\ifstar \LWRABLines \LWRABLines } \)
\(\newcommand {\shortintertext }[1]{\text {#1}\notag \\}\)
\(\newcommand {\vdotswithin }[1]{\hspace {.5em}\vdots }\)
\(\newcommand {\LWRshortvdotswithinstar }[1]{\vdots \hspace {.5em} & \\}\)
\(\newcommand {\LWRshortvdotswithinnostar }[1]{& \hspace {.5em}\vdots \\}\)
\(\newcommand {\shortvdotswithin }{\ifstar \LWRshortvdotswithinstar \LWRshortvdotswithinnostar }\)
\(\newcommand {\MTFlushSpaceAbove }{}\)
\(\newcommand {\MTFlushSpaceBelow }{\\}\)
\(\newcommand \lparen {(}\)
\(\newcommand \rparen {)}\)
\(\newcommand {\ordinarycolon }{:}\)
\(\newcommand {\vcentcolon }{\mathrel {\mathop \ordinarycolon }}\)
\(\newcommand \dblcolon {\vcentcolon \vcentcolon }\)
\(\newcommand \coloneqq {\vcentcolon =}\)
\(\newcommand \Coloneqq {\dblcolon =}\)
\(\newcommand \coloneq {\vcentcolon {-}}\)
\(\newcommand \Coloneq {\dblcolon {-}}\)
\(\newcommand \eqqcolon {=\vcentcolon }\)
\(\newcommand \Eqqcolon {=\dblcolon }\)
\(\newcommand \eqcolon {\mathrel {-}\vcentcolon }\)
\(\newcommand \Eqcolon {\mathrel {-}\dblcolon }\)
\(\newcommand \colonapprox {\vcentcolon \approx }\)
\(\newcommand \Colonapprox {\dblcolon \approx }\)
\(\newcommand \colonsim {\vcentcolon \sim }\)
\(\newcommand \Colonsim {\dblcolon \sim }\)
\(\newcommand {\nuparrow }{\mathrel {\cancel {\uparrow }}}\)
\(\newcommand {\ndownarrow }{\mathrel {\cancel {\downarrow }}}\)
\(\newcommand {\bigtimes }{\mathop {\Large \times }\limits }\)
\(\newcommand {\prescript }[3]{{}^{#1}_{#2}#3}\)
\(\newenvironment {lgathered}{\begin {gathered}}{\end {gathered}}\)
\(\newenvironment {rgathered}{\begin {gathered}}{\end {gathered}}\)
\(\newcommand {\splitfrac }[2]{{}^{#1}_{#2}}\)
\(\let \splitdfrac \splitfrac \)
\(\newcommand {\LWRoverlaysymbols }[2]{\mathord {\smash {\mathop {#2\strut }\limits ^{\smash {\lower 3ex{#1}}}}\strut }}\)
\(\newcommand{\alphaup}{\unicode{x03B1}}\)
\(\newcommand{\betaup}{\unicode{x03B2}}\)
\(\newcommand{\gammaup}{\unicode{x03B3}}\)
\(\newcommand{\digammaup}{\unicode{x03DD}}\)
\(\newcommand{\deltaup}{\unicode{x03B4}}\)
\(\newcommand{\epsilonup}{\unicode{x03F5}}\)
\(\newcommand{\varepsilonup}{\unicode{x03B5}}\)
\(\newcommand{\zetaup}{\unicode{x03B6}}\)
\(\newcommand{\etaup}{\unicode{x03B7}}\)
\(\newcommand{\thetaup}{\unicode{x03B8}}\)
\(\newcommand{\varthetaup}{\unicode{x03D1}}\)
\(\newcommand{\iotaup}{\unicode{x03B9}}\)
\(\newcommand{\kappaup}{\unicode{x03BA}}\)
\(\newcommand{\varkappaup}{\unicode{x03F0}}\)
\(\newcommand{\lambdaup}{\unicode{x03BB}}\)
\(\newcommand{\muup}{\unicode{x03BC}}\)
\(\newcommand{\nuup}{\unicode{x03BD}}\)
\(\newcommand{\xiup}{\unicode{x03BE}}\)
\(\newcommand{\omicronup}{\unicode{x03BF}}\)
\(\newcommand{\piup}{\unicode{x03C0}}\)
\(\newcommand{\varpiup}{\unicode{x03D6}}\)
\(\newcommand{\rhoup}{\unicode{x03C1}}\)
\(\newcommand{\varrhoup}{\unicode{x03F1}}\)
\(\newcommand{\sigmaup}{\unicode{x03C3}}\)
\(\newcommand{\varsigmaup}{\unicode{x03C2}}\)
\(\newcommand{\tauup}{\unicode{x03C4}}\)
\(\newcommand{\upsilonup}{\unicode{x03C5}}\)
\(\newcommand{\phiup}{\unicode{x03D5}}\)
\(\newcommand{\varphiup}{\unicode{x03C6}}\)
\(\newcommand{\chiup}{\unicode{x03C7}}\)
\(\newcommand{\psiup}{\unicode{x03C8}}\)
\(\newcommand{\omegaup}{\unicode{x03C9}}\)
\(\newcommand{\Alphaup}{\unicode{x0391}}\)
\(\newcommand{\Betaup}{\unicode{x0392}}\)
\(\newcommand{\Gammaup}{\unicode{x0393}}\)
\(\newcommand{\Digammaup}{\unicode{x03DC}}\)
\(\newcommand{\Deltaup}{\unicode{x0394}}\)
\(\newcommand{\Epsilonup}{\unicode{x0395}}\)
\(\newcommand{\Zetaup}{\unicode{x0396}}\)
\(\newcommand{\Etaup}{\unicode{x0397}}\)
\(\newcommand{\Thetaup}{\unicode{x0398}}\)
\(\newcommand{\Varthetaup}{\unicode{x03F4}}\)
\(\newcommand{\Iotaup}{\unicode{x0399}}\)
\(\newcommand{\Kappaup}{\unicode{x039A}}\)
\(\newcommand{\Lambdaup}{\unicode{x039B}}\)
\(\newcommand{\Muup}{\unicode{x039C}}\)
\(\newcommand{\Nuup}{\unicode{x039D}}\)
\(\newcommand{\Xiup}{\unicode{x039E}}\)
\(\newcommand{\Omicronup}{\unicode{x039F}}\)
\(\newcommand{\Piup}{\unicode{x03A0}}\)
\(\newcommand{\Varpiup}{\unicode{x03D6}}\)
\(\newcommand{\Rhoup}{\unicode{x03A1}}\)
\(\newcommand{\Sigmaup}{\unicode{x03A3}}\)
\(\newcommand{\Tauup}{\unicode{x03A4}}\)
\(\newcommand{\Upsilonup}{\unicode{x03A5}}\)
\(\newcommand{\Phiup}{\unicode{x03A6}}\)
\(\newcommand{\Chiup}{\unicode{x03A7}}\)
\(\newcommand{\Psiup}{\unicode{x03A8}}\)
\(\newcommand{\Omegaup}{\unicode{x03A9}}\)
\(\newcommand{\alphait}{\unicode{x1D6FC}}\)
\(\newcommand{\betait}{\unicode{x1D6FD}}\)
\(\newcommand{\gammait}{\unicode{x1D6FE}}\)
\(\newcommand{\digammait}{\mathit{\unicode{x03DD}}}\)
\(\newcommand{\deltait}{\unicode{x1D6FF}}\)
\(\newcommand{\epsilonit}{\unicode{x1D716}}\)
\(\newcommand{\varepsilonit}{\unicode{x1D700}}\)
\(\newcommand{\zetait}{\unicode{x1D701}}\)
\(\newcommand{\etait}{\unicode{x1D702}}\)
\(\newcommand{\thetait}{\unicode{x1D703}}\)
\(\newcommand{\varthetait}{\unicode{x1D717}}\)
\(\newcommand{\iotait}{\unicode{x1D704}}\)
\(\newcommand{\kappait}{\unicode{x1D705}}\)
\(\newcommand{\varkappait}{\unicode{x1D718}}\)
\(\newcommand{\lambdait}{\unicode{x1D706}}\)
\(\newcommand{\muit}{\unicode{x1D707}}\)
\(\newcommand{\nuit}{\unicode{x1D708}}\)
\(\newcommand{\xiit}{\unicode{x1D709}}\)
\(\newcommand{\omicronit}{\unicode{x1D70A}}\)
\(\newcommand{\piit}{\unicode{x1D70B}}\)
\(\newcommand{\varpiit}{\unicode{x1D71B}}\)
\(\newcommand{\rhoit}{\unicode{x1D70C}}\)
\(\newcommand{\varrhoit}{\unicode{x1D71A}}\)
\(\newcommand{\sigmait}{\unicode{x1D70E}}\)
\(\newcommand{\varsigmait}{\unicode{x1D70D}}\)
\(\newcommand{\tauit}{\unicode{x1D70F}}\)
\(\newcommand{\upsilonit}{\unicode{x1D710}}\)
\(\newcommand{\phiit}{\unicode{x1D719}}\)
\(\newcommand{\varphiit}{\unicode{x1D711}}\)
\(\newcommand{\chiit}{\unicode{x1D712}}\)
\(\newcommand{\psiit}{\unicode{x1D713}}\)
\(\newcommand{\omegait}{\unicode{x1D714}}\)
\(\newcommand{\Alphait}{\unicode{x1D6E2}}\)
\(\newcommand{\Betait}{\unicode{x1D6E3}}\)
\(\newcommand{\Gammait}{\unicode{x1D6E4}}\)
\(\newcommand{\Digammait}{\mathit{\unicode{x03DC}}}\)
\(\newcommand{\Deltait}{\unicode{x1D6E5}}\)
\(\newcommand{\Epsilonit}{\unicode{x1D6E6}}\)
\(\newcommand{\Zetait}{\unicode{x1D6E7}}\)
\(\newcommand{\Etait}{\unicode{x1D6E8}}\)
\(\newcommand{\Thetait}{\unicode{x1D6E9}}\)
\(\newcommand{\Varthetait}{\unicode{x1D6F3}}\)
\(\newcommand{\Iotait}{\unicode{x1D6EA}}\)
\(\newcommand{\Kappait}{\unicode{x1D6EB}}\)
\(\newcommand{\Lambdait}{\unicode{x1D6EC}}\)
\(\newcommand{\Muit}{\unicode{x1D6ED}}\)
\(\newcommand{\Nuit}{\unicode{x1D6EE}}\)
\(\newcommand{\Xiit}{\unicode{x1D6EF}}\)
\(\newcommand{\Omicronit}{\unicode{x1D6F0}}\)
\(\newcommand{\Piit}{\unicode{x1D6F1}}\)
\(\newcommand{\Rhoit}{\unicode{x1D6F2}}\)
\(\newcommand{\Sigmait}{\unicode{x1D6F4}}\)
\(\newcommand{\Tauit}{\unicode{x1D6F5}}\)
\(\newcommand{\Upsilonit}{\unicode{x1D6F6}}\)
\(\newcommand{\Phiit}{\unicode{x1D6F7}}\)
\(\newcommand{\Chiit}{\unicode{x1D6F8}}\)
\(\newcommand{\Psiit}{\unicode{x1D6F9}}\)
\(\newcommand{\Omegait}{\unicode{x1D6FA}}\)
\(\let \digammaup \Digammaup \)
\(\renewcommand {\digammait }{\mathit {\digammaup }}\)
\(\newcommand {\smallin }{\unicode {x220A}}\)
\(\newcommand {\smallowns }{\unicode {x220D}}\)
\(\newcommand {\notsmallin }{\LWRoverlaysymbols {/}{\unicode {x220A}}}\)
\(\newcommand {\notsmallowns }{\LWRoverlaysymbols {/}{\unicode {x220D}}}\)
\(\newcommand {\rightangle }{\unicode {x221F}}\)
\(\newcommand {\intclockwise }{\unicode {x2231}}\)
\(\newcommand {\ointclockwise }{\unicode {x2232}}\)
\(\newcommand {\ointctrclockwise }{\unicode {x2233}}\)
\(\newcommand {\oiint }{\unicode {x222F}}\)
\(\newcommand {\oiiint }{\unicode {x2230}}\)
\(\newcommand {\ddag }{\unicode {x2021}}\)
\(\newcommand {\P }{\unicode {x00B6}}\)
\(\newcommand {\copyright }{\unicode {x00A9}}\)
\(\newcommand {\dag }{\unicode {x2020}}\)
\(\newcommand {\pounds }{\unicode {x00A3}}\)
\(\newcommand {\iddots }{\unicode {x22F0}}\)
\(\newcommand {\utimes }{\overline {\times }}\)
\(\newcommand {\dtimes }{\underline {\times }}\)
\(\newcommand {\udtimes }{\overline {\underline {\times }}}\)
\(\newcommand {\leftwave }{\left \{}\)
\(\newcommand {\rightwave }{\right \}}\)
\(\newcommand {\toprule }[1][]{\hline }\)
\(\let \midrule \toprule \)
\(\let \bottomrule \toprule \)
\(\newcommand {\cmidrule }[2][]{}\)
\(\newcommand {\morecmidrules }{}\)
\(\newcommand {\specialrule }[3]{\hline }\)
\(\newcommand {\addlinespace }[1][]{}\)
\(\newcommand {\LWRsubmultirow }[2][]{#2}\)
\(\newcommand {\LWRmultirow }[2][]{\LWRsubmultirow }\)
\(\newcommand {\multirow }[2][]{\LWRmultirow }\)
\(\newcommand {\mrowcell }{}\)
\(\newcommand {\mcolrowcell }{}\)
\(\newcommand {\STneed }[1]{}\)
\( \newcommand {\multicolumn }[3]{#3}\)
\(\newcommand {\tothe }[1]{^{#1}}\)
\(\newcommand {\raiseto }[2]{{#2}^{#1}}\)
\(\newcommand {\ang }[2][]{(\mathrm {#2})\degree }\)
\(\newcommand {\num }[2][]{\mathrm {#2}}\)
\(\newcommand {\si }[2][]{\mathrm {#2}}\)
\(\newcommand {\LWRSI }[2][]{\mathrm {#1\LWRSInumber \,#2}}\)
\(\newcommand {\SI }[2][]{\def \LWRSInumber {#2}\LWRSI }\)
\(\newcommand {\numlist }[2][]{\mathrm {#2}}\)
\(\newcommand {\numrange }[3][]{\mathrm {#2\,\unicode {x2013}\,#3}}\)
\(\newcommand {\SIlist }[3][]{\mathrm {#2\,#3}}\)
\(\newcommand {\SIrange }[4][]{\mathrm {#2\,#4\,\unicode {x2013}\,#3\,#4}}\)
\(\newcommand {\tablenum }[2][]{\mathrm {#2}}\)
\(\newcommand {\ampere }{\mathrm {A}}\)
\(\newcommand {\candela }{\mathrm {cd}}\)
\(\newcommand {\kelvin }{\mathrm {K}}\)
\(\newcommand {\kilogram }{\mathrm {kg}}\)
\(\newcommand {\metre }{\mathrm {m}}\)
\(\newcommand {\mole }{\mathrm {mol}}\)
\(\newcommand {\second }{\mathrm {s}}\)
\(\newcommand {\becquerel }{\mathrm {Bq}}\)
\(\newcommand {\degreeCelsius }{\unicode {x2103}}\)
\(\newcommand {\coulomb }{\mathrm {C}}\)
\(\newcommand {\farad }{\mathrm {F}}\)
\(\newcommand {\gray }{\mathrm {Gy}}\)
\(\newcommand {\hertz }{\mathrm {Hz}}\)
\(\newcommand {\henry }{\mathrm {H}}\)
\(\newcommand {\joule }{\mathrm {J}}\)
\(\newcommand {\katal }{\mathrm {kat}}\)
\(\newcommand {\lumen }{\mathrm {lm}}\)
\(\newcommand {\lux }{\mathrm {lx}}\)
\(\newcommand {\newton }{\mathrm {N}}\)
\(\newcommand {\ohm }{\mathrm {\Omega }}\)
\(\newcommand {\pascal }{\mathrm {Pa}}\)
\(\newcommand {\radian }{\mathrm {rad}}\)
\(\newcommand {\siemens }{\mathrm {S}}\)
\(\newcommand {\sievert }{\mathrm {Sv}}\)
\(\newcommand {\steradian }{\mathrm {sr}}\)
\(\newcommand {\tesla }{\mathrm {T}}\)
\(\newcommand {\volt }{\mathrm {V}}\)
\(\newcommand {\watt }{\mathrm {W}}\)
\(\newcommand {\weber }{\mathrm {Wb}}\)
\(\newcommand {\day }{\mathrm {d}}\)
\(\newcommand {\degree }{\mathrm {^\circ }}\)
\(\newcommand {\hectare }{\mathrm {ha}}\)
\(\newcommand {\hour }{\mathrm {h}}\)
\(\newcommand {\litre }{\mathrm {l}}\)
\(\newcommand {\liter }{\mathrm {L}}\)
\(\newcommand {\arcminute }{^\prime }\)
\(\newcommand {\minute }{\mathrm {min}}\)
\(\newcommand {\arcsecond }{^{\prime \prime }}\)
\(\newcommand {\tonne }{\mathrm {t}}\)
\(\newcommand {\astronomicalunit }{au}\)
\(\newcommand {\atomicmassunit }{u}\)
\(\newcommand {\bohr }{\mathit {a}_0}\)
\(\newcommand {\clight }{\mathit {c}_0}\)
\(\newcommand {\dalton }{\mathrm {D}_\mathrm {a}}\)
\(\newcommand {\electronmass }{\mathit {m}_{\mathrm {e}}}\)
\(\newcommand {\electronvolt }{\mathrm {eV}}\)
\(\newcommand {\elementarycharge }{\mathit {e}}\)
\(\newcommand {\hartree }{\mathit {E}_{\mathrm {h}}}\)
\(\newcommand {\planckbar }{\mathit {\unicode {x210F}}}\)
\(\newcommand {\angstrom }{\mathrm {\unicode {x212B}}}\)
\(\let \LWRorigbar \bar \)
\(\newcommand {\bar }{\mathrm {bar}}\)
\(\newcommand {\barn }{\mathrm {b}}\)
\(\newcommand {\bel }{\mathrm {B}}\)
\(\newcommand {\decibel }{\mathrm {dB}}\)
\(\newcommand {\knot }{\mathrm {kn}}\)
\(\newcommand {\mmHg }{\mathrm {mmHg}}\)
\(\newcommand {\nauticalmile }{\mathrm {M}}\)
\(\newcommand {\neper }{\mathrm {Np}}\)
\(\newcommand {\yocto }{\mathrm {y}}\)
\(\newcommand {\zepto }{\mathrm {z}}\)
\(\newcommand {\atto }{\mathrm {a}}\)
\(\newcommand {\femto }{\mathrm {f}}\)
\(\newcommand {\pico }{\mathrm {p}}\)
\(\newcommand {\nano }{\mathrm {n}}\)
\(\newcommand {\micro }{\mathrm {\unicode {x00B5}}}\)
\(\newcommand {\milli }{\mathrm {m}}\)
\(\newcommand {\centi }{\mathrm {c}}\)
\(\newcommand {\deci }{\mathrm {d}}\)
\(\newcommand {\deca }{\mathrm {da}}\)
\(\newcommand {\hecto }{\mathrm {h}}\)
\(\newcommand {\kilo }{\mathrm {k}}\)
\(\newcommand {\mega }{\mathrm {M}}\)
\(\newcommand {\giga }{\mathrm {G}}\)
\(\newcommand {\tera }{\mathrm {T}}\)
\(\newcommand {\peta }{\mathrm {P}}\)
\(\newcommand {\exa }{\mathrm {E}}\)
\(\newcommand {\zetta }{\mathrm {Z}}\)
\(\newcommand {\yotta }{\mathrm {Y}}\)
\(\newcommand {\percent }{\mathrm {\%}}\)
\(\newcommand {\meter }{\mathrm {m}}\)
\(\newcommand {\metre }{\mathrm {m}}\)
\(\newcommand {\gram }{\mathrm {g}}\)
\(\newcommand {\kg }{\kilo \gram }\)
\(\newcommand {\of }[1]{_{\mathrm {#1}}}\)
\(\newcommand {\squared }{^2}\)
\(\newcommand {\square }[1]{\mathrm {#1}^2}\)
\(\newcommand {\cubed }{^3}\)
\(\newcommand {\cubic }[1]{\mathrm {#1}^3}\)
\(\newcommand {\per }{/}\)
\(\newcommand {\celsius }{\unicode {x2103}}\)
\(\newcommand {\fg }{\femto \gram }\)
\(\newcommand {\pg }{\pico \gram }\)
\(\newcommand {\ng }{\nano \gram }\)
\(\newcommand {\ug }{\micro \gram }\)
\(\newcommand {\mg }{\milli \gram }\)
\(\newcommand {\g }{\gram }\)
\(\newcommand {\kg }{\kilo \gram }\)
\(\newcommand {\amu }{\mathrm {u}}\)
\(\newcommand {\nm }{\nano \metre }\)
\(\newcommand {\um }{\micro \metre }\)
\(\newcommand {\mm }{\milli \metre }\)
\(\newcommand {\cm }{\centi \metre }\)
\(\newcommand {\dm }{\deci \metre }\)
\(\newcommand {\m }{\metre }\)
\(\newcommand {\km }{\kilo \metre }\)
\(\newcommand {\as }{\atto \second }\)
\(\newcommand {\fs }{\femto \second }\)
\(\newcommand {\ps }{\pico \second }\)
\(\newcommand {\ns }{\nano \second }\)
\(\newcommand {\us }{\micro \second }\)
\(\newcommand {\ms }{\milli \second }\)
\(\newcommand {\s }{\second }\)
\(\newcommand {\fmol }{\femto \mol }\)
\(\newcommand {\pmol }{\pico \mol }\)
\(\newcommand {\nmol }{\nano \mol }\)
\(\newcommand {\umol }{\micro \mol }\)
\(\newcommand {\mmol }{\milli \mol }\)
\(\newcommand {\mol }{\mol }\)
\(\newcommand {\kmol }{\kilo \mol }\)
\(\newcommand {\pA }{\pico \ampere }\)
\(\newcommand {\nA }{\nano \ampere }\)
\(\newcommand {\uA }{\micro \ampere }\)
\(\newcommand {\mA }{\milli \ampere }\)
\(\newcommand {\A }{\ampere }\)
\(\newcommand {\kA }{\kilo \ampere }\)
\(\newcommand {\ul }{\micro \litre }\)
\(\newcommand {\ml }{\milli \litre }\)
\(\newcommand {\l }{\litre }\)
\(\newcommand {\hl }{\hecto \litre }\)
\(\newcommand {\uL }{\micro \liter }\)
\(\newcommand {\mL }{\milli \liter }\)
\(\newcommand {\L }{\liter }\)
\(\newcommand {\hL }{\hecto \liter }\)
\(\newcommand {\mHz }{\milli \hertz }\)
\(\newcommand {\Hz }{\hertz }\)
\(\newcommand {\kHz }{\kilo \hertz }\)
\(\newcommand {\MHz }{\mega \hertz }\)
\(\newcommand {\GHz }{\giga \hertz }\)
\(\newcommand {\THz }{\tera \hertz }\)
\(\newcommand {\mN }{\milli \newton }\)
\(\newcommand {\N }{\newton }\)
\(\newcommand {\kN }{\kilo \newton }\)
\(\newcommand {\MN }{\mega \newton }\)
\(\newcommand {\Pa }{\pascal }\)
\(\newcommand {\kPa }{\kilo \pascal }\)
\(\newcommand {\MPa }{\mega \pascal }\)
\(\newcommand {\GPa }{\giga \pascal }\)
\(\newcommand {\mohm }{\milli \ohm }\)
\(\newcommand {\kohm }{\kilo \ohm }\)
\(\newcommand {\Mohm }{\mega \ohm }\)
\(\newcommand {\pV }{\pico \volt }\)
\(\newcommand {\nV }{\nano \volt }\)
\(\newcommand {\uV }{\micro \volt }\)
\(\newcommand {\mV }{\milli \volt }\)
\(\newcommand {\V }{\volt }\)
\(\newcommand {\kV }{\kilo \volt }\)
\(\newcommand {\W }{\watt }\)
\(\newcommand {\uW }{\micro \watt }\)
\(\newcommand {\mW }{\milli \watt }\)
\(\newcommand {\kW }{\kilo \watt }\)
\(\newcommand {\MW }{\mega \watt }\)
\(\newcommand {\GW }{\giga \watt }\)
\(\newcommand {\J }{\joule }\)
\(\newcommand {\uJ }{\micro \joule }\)
\(\newcommand {\mJ }{\milli \joule }\)
\(\newcommand {\kJ }{\kilo \joule }\)
\(\newcommand {\eV }{\electronvolt }\)
\(\newcommand {\meV }{\milli \electronvolt }\)
\(\newcommand {\keV }{\kilo \electronvolt }\)
\(\newcommand {\MeV }{\mega \electronvolt }\)
\(\newcommand {\GeV }{\giga \electronvolt }\)
\(\newcommand {\TeV }{\tera \electronvolt }\)
\(\newcommand {\kWh }{\kilo \watt \hour }\)
\(\newcommand {\F }{\farad }\)
\(\newcommand {\fF }{\femto \farad }\)
\(\newcommand {\pF }{\pico \farad }\)
\(\newcommand {\K }{\mathrm {K}}\)
\(\newcommand {\dB }{\mathrm {dB}}\)
\(\newcommand {\kibi }{\mathrm {Ki}}\)
\(\newcommand {\mebi }{\mathrm {Mi}}\)
\(\newcommand {\gibi }{\mathrm {Gi}}\)
\(\newcommand {\tebi }{\mathrm {Ti}}\)
\(\newcommand {\pebi }{\mathrm {Pi}}\)
\(\newcommand {\exbi }{\mathrm {Ei}}\)
\(\newcommand {\zebi }{\mathrm {Zi}}\)
\(\newcommand {\yobi }{\mathrm {Yi}}\)
\(\require {mhchem}\)
\(\require {cancel}\)
\(\newcommand {\fint }{âĺŊ}\)
\(\newcommand {\hdots }{\cdots }\)
\(\newcommand {\mathnormal }[1]{#1}\)
\(\newcommand {\vecs }[2]{\vec {#1}_{#2}}\)
\(\newcommand {\BB }{\mathbb {B}}\)
\(\newcommand {\EE }{\mathbb {E}}\)
\(\newcommand {\FF }{\mathbb {F}}\)
\(\newcommand {\KK }{\mathbb {K}}\)
\(\newcommand {\PP }{\mathbb {P}}\)
\(\renewcommand {\O }{\mathcal {O}}\)
\(\newcommand {\weakO }{\widetilde {\mathcal {O}}}\)
\(\newcommand {\teilt }{\mid }\)
\(\newcommand {\notteilt }{\nmid }\)
\(\newcommand {\ggT }{\operatorname {ggT}}\)
\(\newcommand {\Char }{\operatorname {char}}\)
\(\newcommand {\Rang }{\operatorname {Rang}}\)
\(\newcommand {\ZkZ }{\integer /k\integer }\)
\(\newcommand {\ZmZ }{\integer /m\integer }\)
\(\newcommand {\ZnZ }{\integer /n\integer }\)
\(\newcommand {\ZpZ }{\integer /p\integer }\)
\(\newcommand {\ZqZ }{\integer /q\integer }\)
\(\newcommand {\iu }{\mathrm {i}}\)
\(\newcommand {\xor }{\oplus }\)
\(\newcommand {\bigxor }{\bigoplus }\)
\(\newcommand {\IP }{\operatorname {IP}}\)
\(\newcommand {\PC }{\operatorname {PC}}\)
\(\newcommand {\DES }{\operatorname {DES}}\)
\(\newcommand {\smallbullet }{{\scriptstyle \bullet }}\)
\(\newcommand {\ord }{\operatorname {ord}}\)
\(\newcommand {\erzeugnis }[1]{\langle #1\rangle }\)
\(\newcommand {\true }{\texttt {true}}\)
\(\newcommand {\false }{\texttt {false}}\)
\(\renewcommand {\div }{\operatorname {div}}\)
\(\newcommand {\Pic }{\operatorname {Pic}}\)
\(\newcommand {\code }[1]{\texttt {#1}}\)
\(\newcommand {\name }[1]{\textsc {#1}}\)
\(\newcommand {\smallpmatrix }[1]{\left (\begin {smallmatrix}#1\end {smallmatrix}\right )}\)
\(\newcommand {\matlab }{{\fontfamily {bch}\scshape \selectfont {}Matlab}}\)
\(\newcommand {\innerproduct }[1]{\left \langle {#1}\right \rangle }\)
\(\newcommand {\norm }[1]{\left \Vert {#1}\right \Vert }\)
\(\renewcommand {\natural }{\mathbb {N}}\)
\(\newcommand {\integer }{\mathbb {Z}}\)
\(\newcommand {\rational }{\mathbb {Q}}\)
\(\newcommand {\real }{\mathbb {R}}\)
\(\newcommand {\complex }{\mathbb {C}}\)
\(\renewcommand {\d }{\mathop {}\!\mathrm {d}}\)
\(\newcommand {\dr }{\d {}r}\)
\(\newcommand {\ds }{\d {}s}\)
\(\newcommand {\dt }{\d {}t}\)
\(\newcommand {\du }{\d {}u}\)
\(\newcommand {\dv }{\d {}v}\)
\(\newcommand {\dw }{\d {}w}\)
\(\newcommand {\dx }{\d {}x}\)
\(\newcommand {\dy }{\d {}y}\)
\(\newcommand {\dz }{\d {}z}\)
\(\newcommand {\dsigma }{\d {}\sigma }\)
\(\newcommand {\dphi }{\d {}\phi }\)
\(\newcommand {\dvarphi }{\d {}\varphi }\)
\(\newcommand {\dtau }{\d {}\tau }\)
\(\newcommand {\dxi }{\d {}\xi }\)
\(\newcommand {\dtheta }{\d {}\theta }\)
\(\newcommand {\tp }{\mathrm {T}}\)
Verfahren
Der Miller-Rabin-Test ist ein probabilistischer Primzahltest. Wenn der Algorithmus ausgibt, dass die Zahl zusammengesetzt ist, dann stimmt das auch, allerdings stimmt die Ausgabe „wahrscheinlich prim“ nur zu \(\ge \)
50 %. Der Miller-Rabin-Test baut auf dem Fermat-Test auf.
Fermat-Test: Der Fermat-Test ist ein probabilistischer Primzahltest und läuft wie folgt ab.
Gegeben sei \(n \in \natural \).
Wähle \(a \in \{1, \dotsc , n - 1\}\) zufällig. Falls \(\ggT (a, n) > 1\) gilt, dann gib „\(n\) nicht prim“ aus.
Wenn \(a^{n-1} \equiv _n 1\), dann gib „\(n\) wahrscheinlich prim“ aus, ansonsten „\(n\) nicht prim“.
Der Test basiert auf dem kleinen Satz von Fermat: Für \(\ggT (a, n) = 1\) und \(n\) prim gilt \(a^{n-1} \equiv _n 1\). Ist die Kongruenz also nicht erfüllt, kann \(n\) nicht prim sein.
Carmichael-Zahl:
Eine Zahl \(n \in \natural \) heißt Carmichael-Zahl, falls \(n\) zusammengesetzt ist und \(\forall _{a \in (\ZnZ )^\ast }\; a^{n-1}
\equiv _n 1\).
Es gibt unendlich vieler solcher Zahlen, die kleinste ist \(561 = 3 \cdot 11 \cdot 17\). Bei bestimmten \(n\) gibt also der Fermat-Test immer „\(n\) wahrscheinlich prim“ aus, obwohl \(n\) nicht prim ist (wenn der Test nicht
zufällig einen nicht-trivialen Teiler \(a\) von \(n\) erwischt). Daher ist der Fermat-Test als Primzahltest ungeeignet.
Miller-Rabin-Test: Der Miller-Rabin-Test
(MR-Test) ist ein probabilistischer Primzahltest und läuft wie folgt ab. Gegeben sei \(n \in \natural \) ungerade mit \(n \ge 3\).
Schreibe \(n - 1 = 2^\ell u\) mit \(u \in \natural \) ungerade und \(\ell \in \natural \).
Wähle \(a \in \{1, \dotsc , n - 1\}\) zufällig. Falls \(\ggT (a, n) > 1\) gilt, dann gib „\(n\) nicht prim“ aus.
Sonst berechne \(b := a^u \bmod n\).
Wenn \(b = 1\) ist, dann gib „\(n\) wahrscheinlich prim“ aus.
Sonst berechne die Folge \((b, b^2, b^{2^2}, \dotsc , b^{2^{\ell -1}})\) in \(\ZnZ \).
Falls \(-1\) in dieser Folge vorkommt, dann gib „\(n\) wahrscheinlich prim“ aus, ansonst gib „\(n\) nicht prim“ aus.
Der Miller-Rabin-Test ist gewissermaßen eine Verallgemeinerung des Fermat-Tests: Wenn der MR-Test „\(n\) wahrscheinlich prim“ ausgibt, dann gibt der Fermat-Test dies auch aus (wenn der Fermat-Test „\(n\) nicht prim“ ausgibt,
dann ist \(\ggT (a, n) > 1\) oder \(a^{n-1} \not \equiv _n 1\)). Die Umkehrung gilt allerdings nicht, d. h. der MR-Test erkennt mehr zusammengesetzte Zahlen sicher als solche.
Korrektheit
Satz (Korrektheit des MR-Tests):
Wenn der MR-Test „\(n\) nicht prim“ ausgibt, dann ist \(n\) nicht prim.
Beweis: Sei \(n \ge 3\) prim. Dann gibt es kein \(a \in \{1, \dotsc , n - 1\}\) mit \(\ggT (a, n) > 1\), d. h. in Schritt (2) wird nichts ausgegeben. Sei also \(a \in (\ZnZ )^\ast \)
beliebig. Ist \(b := a^u \bmod n = 1\), dann gibt der Test „\(n\) wahrscheinlich prim“ aus.
Sei also \(b \not = 1\). Es gilt \(a^{n-1} \equiv _n 1\) nach dem kleinen Satz von Fermat (weil \(n\) prim), also \(1 \equiv _n a^{2^\ell u} \equiv _n b^{2^\ell }\). Daher gilt \(b^{2^{\ell -1}} \equiv _n \pm 1\)
(\(\ZnZ \) Körper wegen \(n\) prim).
Ist \(b^{2^{\ell -1}} \equiv _n -1\), dann gibt der Test „\(n\) wahrscheinlich prim“ aus. Sonst ist \(b^{2^{\ell -1}} \equiv _n 1\) und man kann die Argumentation wiederholen. Der Test gibt also „\(n\) wahrscheinlich
prim“ aus oder es gilt \(b^{2^\ell } \equiv _n b^{2^{\ell -1}} \equiv _n \dotsb \equiv _n b \equiv _n 1\), ein Widerspruch zur Annahme \(b \not = 1\). Somit gibt der Algorithmus in jedem Fall „\(n\)
wahrscheinlich prim“ aus.
Zuverlässigkeit
Im Folgenden wird gezeigt, dass für \(n\) zusammengesetzt die Wahrscheinlichkeit, dass ein \(a\) gewählt wird, sodass „\(n\) wahrscheinlich prim“ ausgegeben wird, höchstens 50 % ist (in
Wahrheit ist diese Fehlerwahrscheinlichkeit sogar höchstens 25 %). Bei \(m\) Iterationen des Algorithmus ist deswegen die Fehlerwahrscheinlichkeit höchstens \(\frac {1}{2^m}\). Andersherum ist die
Wahrscheinlichkeit, dass \(n\) prim ist, wenn \(m\)-mal „\(n\) wahrscheinlich prim“ ausgegeben wurde, mindestens \(1 - \frac {1}{2^m}\).
Lemma: Seien \(p \ge 3\) prim und \(d \ge 2\). Dann gilt \((p^{d-1} + 1)^{p^d-1} \not \equiv \pm 1 \pmod {p^d}\).
Beweis: Im Folgenden wird immer modulo \(p^d\) gerechnet.
Nach dem Binomischen Lehrsatz gilt \((p^{d-1} + 1)^{p^d-1} = \sum _{k \in \natural _0} \binom {p^d - 1}{k} p^{(d-1)k}\). Für \(k \ge 2\) ist \((d-1)k \ge d\), weil \(k \ge 2 \ge \frac {d}{d-1}\)
wegen \(d \ge 2\). Damit gilt \(p^d \teilt p^{(d-1)k}\) für \(k \ge 2\), d. h. \(p^{(d-1)k} \equiv 0\) und alle Summanden für \(k \ge 2\) verschwinden modulo \(p^d\).
Daher gilt \((p^{d-1} + 1)^{p^d-1} = 1 + (p^d - 1) p^{d-1} \equiv 1 + (0 - 1)p^{d-1} = 1 - p^{d-1}\).
Wäre \(1 - p^{d-1} \equiv 1\), so würde \(p^{d-1} \equiv 0\) gelten, also \(p^d \teilt p^{d-1}\), ein Widerspruch.
Wäre \(1 - p^{d-1} \equiv -1\), so würde \(p^{d-1} \equiv 2\) gelten, also \(p^d \teilt (p^{d-1}-2)\), ein Widerspruch.
Insbesondere ist \(p^d\) für \(p \ge 3\) und \(d \ge 2\) keine Carmichael-Zahl, weil dann \(p^d\) zusammengesetzt ist und \(\ggT (p^{d-1}+1, p^d) = 1\) gilt.
Satz: Seien \(n \ge 3\) ungerade und zusammengesetzt, \(u \in \natural \) ungerade und \(\ell \in \natural \).
Definiere \(G := \{a \in (\ZnZ )^\ast \;|\; a^{2^\ell u} \equiv _n 1\}\) und \(H := \{a \in G \;|\; a^{2^{\ell ’-1} u} \equiv _n \pm 1\}\) mit
\(\ell ’ := \min \{k \in \natural _0 \;|\; \forall _{a \in G}\; a^{2^k u} \equiv _n 1\}\). Dann gilt \(H < G < (\ZnZ )^\ast \) mit \(H \not = (\ZnZ )^\ast \).
Beweis: Zunächst ist \(\ell ’ > 0\), da \(-1 \in G\) (wegen \(\ell \ge 1\)) und \(a^{2^k u} = (-1)^u = -1 \not \equiv _n 1\) für \(a = -1 \in G\) und \(k = 0\) (wegen \(u\)
ungerade und \(n \not = 2\)). Außerdem ist \(\ell ’ \le \ell \), weil \(\forall _{a \in G}\; a^{2^k u} \equiv _n 1\) für \(k = \ell \). (Damit ist \(\ell ’ \in \{1, \dotsc , \ell \}\)
tatsächlich endlich.)
Es gilt \(G < (\ZnZ )^\ast \), weil \(1 \in G\), \((ab)^{2^\ell u} = a^{2^\ell u} b^{2^\ell u} \equiv _n 1\) und \((a^{-1})^{2^\ell u} = (a^{2^\ell u})^{-1} \equiv _n 1\) für \(a, b \in G\).
Analog ist \(H < G\), weil \(1 \in H\), \((ab)^{2^{\ell ’-1} u} = a^{2^{\ell ’-1} u} b^{2^{\ell ’-1} u} \equiv _n (\pm 1)^2 = 1\) und \((a^{-1})^{2^{\ell ’-1} u} = (a^{2^{\ell ’-1} u})^{-1} \equiv
_n (\pm 1)^{-1} = \pm 1\) für \(a, b \in G\).
Für \(G \not = (\ZnZ )^\ast \) ist nichts zu zeigen. Sei also \(G = (\ZnZ )^\ast \). Wegen der Minimalität von \(\ell ’\) existiert ein \(a \in G\) mit \(a^{2^{\ell ’-1} u} \not \equiv _n 1\).
Schreibe \(n = r \cdot s\) mit \(r, s \ge 3\) und \(\ggT (r, s) = 1\). Nach dem chin. Restsatz kann \(a^{2^{\ell ’-1} u} \equiv 1\) nicht gleichzeitig modulo \(r\) und modulo \(s\) gelten. Sei also oBdA \(a^{2^{\ell
’-1} u} \not \equiv _r 1\). Wähle ein \(c \in (\ZnZ )^\ast \) mit \(c \equiv _r a\) und \(c \equiv _s 1\) (existiert nach dem chin. Restsatz). Dann gilt \(c \in G = (\ZnZ )^\ast \), aber \(c \notin H\):
Wäre \(c^{2^{\ell ’-1} u} \equiv _n 1\), dann \(a^{2^{\ell ’-1} u} \equiv _r c^{2^{\ell ’-1} u} \equiv _r 1\) (wegen \(c \equiv _r a\)), Widerspruch zu \(a^{2^{\ell ’-1} u} \not \equiv _r
1\).
Wäre \(c^{2^{\ell ’-1} u} \equiv _n -1\), dann \(1 \equiv _s c^{2^{\ell ’-1} u} \equiv _s -1\) (wegen \(c \equiv _s 1\)), was nur für \(s = 2\) gehen würde.
Damit gilt \(H \lneqq G = (\ZnZ )^\ast \).
Seien \(u \in \natural \) ungerade und \(\ell \in \natural \) ab jetzt wieder so gewählt, dass \(n-1 = 2^\ell u\).
Lemma: Seien \(n \ge 3\) ungerade und \(a \in (\ZnZ )^\ast \).
Wenn \(a \notin H\) gilt, dann gibt der MR-Test „\(n\) nicht prim“ aus.
Beweis: Sei \(b := a^u \bmod n\). Wäre \(b = 1\), dann wäre \(a^{2^{\ell ’-1} u} = b^{2^{\ell ’-1}} = 1\), d. h. \(a \in H\), ein Widerspruch zur Voraussetzung. Daher gilt \(b
\not = 1\) und in Schritt (3) wird nichts ausgegeben.
Ist \(1 \in \{b, b^2, b^{2^2}, \dotsc , b^{2^{\ell -1}}\}\) modulo \(n\), dann gilt \(a \in G\), da dann \(a^{2^\ell u} = (a^u)^{2^\ell } \equiv _n b^{2^\ell } \equiv _n 1\). Damit gilt \(a \in G
\setminus H\) und \(b^{2^{\ell ’-1}} \not \equiv _n \pm 1\). Daraus folgt \(b^{2^k} \not \equiv _n -1\) für alle \(k \in \{0, \dotsc , \ell ’ - 1\}\). Nach Def. von \(\ell ’ \le \ell \) gilt
außerdem \(b^{2^{\ell ’}} \equiv _n 1\). Daraus folgt \(b^{2^k} \equiv _n 1\) für alle \(k \in \{\ell ’, \dotsc , \ell - 1\}\). In jedem Fall gilt \(b^{2^k} \not \equiv _n -1\) für alle \(k
\in \{0, \dotsc , \ell - 1\}\).
Ist \(1 \notin \{b, b^2, b^{2^2}, \dotsc , b^{2^{\ell -1}}\}\) modulo \(n\), dann ist \(b^{2^k} \not \equiv _n -1\) für \(k \in \{0, \dotsc , \ell -2\}\). Zusätzlich gilt \(b^{2^{\ell -1}}
\not \equiv _n -1\), da sonst \(a \in G\) (wegen \(a^{2^\ell u} \equiv _n (b^{2^{\ell -1}})^2 \equiv _n (-1)^2 = 1\)) und man wie eben argumentieren kann.
Es gilt also immer, dass \(-1\) nicht in der Folge \((b, b^2, b^{2^2}, \dotsc , b^{2^{\ell -1}})\) in \(\ZnZ \) vorkommt. Damit gibt der Algorithmus „\(n\) nicht prim“ aus.
Satz (Zuverlässigkeit des MR-Tests): Sei \(n \ge 3\) ungerade und zusammengesetzt.
Dann liefert der MR-Test bei mindestens der Hälfte aller \(a \in (\ZnZ )^\ast \) „\(n\) nicht prim“.
Beweis: Seien \(n-1 = 2^\ell u\) und \(G\) und \(H\) wie im obigen Satz. Nach demselben Satz gilt \(H \lneqq (\ZnZ )^\ast \), d. h. \([(\ZnZ )^\ast : H] \ge 2\). Für mindestens der
Hälfte aller \(a \in (\ZnZ )^\ast \) gilt daher \(a \notin H\). Nach obigem Lemma gibt der MR-Test für diese \(a\) „\(n\) nicht prim“ aus.
Faktorisierung: Gilt \(b^{2^k} \equiv _n 1\) für ein \(k \in \{1, \dotsc , \ell - 1\}\), dann kommt nach dem Beweis des letzten Lemmas keine \(-1\) in der Folge vor und man kann \(n\) sogar
faktorisieren.
Sei dazu \(c := (b^{2^{k-1}} \bmod n) \not = 1\) mit \(b^{2^k} \equiv _n 1\). Dann gilt \(c^2 \equiv _n 1\) sowie \(c \not \equiv _n \pm 1\), d. h. \((c-1)(c+1) \equiv _n 0\) bzw. \(n \teilt
(c-1)(c+1)\), aber \(n \notteilt (c-1)\) und \(n \notteilt (c+1)\).
Damit folgt \(1 < \ggT (c-1, n), \ggT (c+1, n) < n\).