Jakobia simbolo

La jakobia simbolo estas ĝeneraligo de la simbolo de Legendre donita de Jakobio en 1837. Ĝi estas de teoria intereso en modula aritmetiko kaj aliaj branĉoj de nombroteorio, sed ĝia ĉefa uzo estas en komputa nombroteorio, aparte primeco-testo kaj faktorigo de entjero; ĉi tiuj laŭvice estas gravaj en ĉifriko.

Difino

Por ĉiu entjero a kaj ĉiu pozitiva nepara entjero n la jakobia simbolo estas difinita kiel produto de la simboloj de Legendre respektivaj al la primaj faktoroj de n:

$\left({\frac {a}{n}}\right)=\left({\frac {a}{p_{1}}}\right)^{\alpha _{1}}\left({\frac {a}{p_{2}}}\right)^{\alpha _{2}}\cdots \left({\frac {a}{p_{k}}}\right)^{\alpha _{k}}{\text{ kie }}n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{k}^{\alpha _{k}}$

Kun la normala konvencio por la malplena produto estas $\left({\frac {a}{1}}\right)=1$.

La simbolo de Legendre $\left({\frac {a}{p}}\right)$ estas difinita por ĉiuj entjeroj a kaj ĉiuj neparaj primoj p per

$\left({\frac {a}{p}}\right)={\begin{cases}\;\;\,0{\text{ se }}a\equiv 0{\pmod {p}}\\+1{\text{ se }}a\not \equiv 0{\pmod {p}}{\text{ kaj por iu entjero }}x,\;a\equiv x^{2}{\pmod {p}}\\-1{\text{ se ne ekzistas cxi tia }}x.\end{cases}}$

Se $\left({\frac {a}{p}}\right)=1$, a estas kvadrata restaĵo (mod p). Se $\left({\frac {a}{p}}\right)=-1$, a estas kvadrata nerestaĵo (mod p). Nulo estas kutime traktata kiel speciala okazo.

Propraĵoj de la simbolo de Legendre

La simbolo de Legendre havas jenajn propraĵojn, kiuj estas facile konkludataj de ĝia difino:

$\left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right)$, do $\left({\frac {a^{2}}{p}}\right)=1$ aŭ $\left({\frac {a^{2}}{p}}\right)=0$

Se $a\equiv b{\pmod {p}}$ do $\left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right)$

La simbolo de Legendre obeas ankaŭ la leĝon de kvadrata reciprokeco (kiu estas ne tiel facile konkludata):

Se p kaj q estas neparaj primoj do $\left({\frac {p}{q}}\right)=\left({\frac {q}{p}}\right)(-1)^{\frac {(p-1)(q-1)}{4}}$

kaj ĝiaj suplementoj

$\left({\frac {-1}{p}}\right)=(-1)^{\frac {(p-1)}{2}}=\left\{{\begin{array}{cl}1&{\text{se}}\;p\equiv 1{\pmod {4}}\\-1&{\text{se}}\;p\equiv 3{\pmod {4}}\end{array}}\right.$

${\left({\frac {2}{p}}\right)=(-1)^{\frac {(p^{2}-1)}{8}}=\left\{{\begin{array}{cl}1&{\text{se}}\;p\equiv 1{\pmod {8}}\;{\text{ aux }}\;p\equiv 7{\pmod {8}}\\-1&{\text{se}}\;p\equiv 3{\pmod {8}}\;{\text{ aux }}\;p\equiv 5{\pmod {8}}\end{array}}\right.}$

Estas formulo por la simbolo de Legendre nomata kiel eŭlera kriterio: $\left({\frac {a}{p}}\right)\equiv a^{(p-1)/2}{\pmod {p}}$

Propraĵoj de la jakobia simbolo

Ĉi tiuj faktoj, eĉ la reciprokecaj leĝoj, estas simplaj konkludoj de la difino de la jakobia simbolo kaj de la respektivaj propraĵoj de la simbolo de Legendre.

Se m estas nepara primo do jakobia simbolo $\left({\frac {a}{n}}\right)$ estas ankaŭ simbolo de Legendre.

$\left({\frac {a}{n}}\right)={\begin{cases}\;\;\,0{\text{ se }}\gcd(a,n)\neq 1\\\pm 1{\text{ se }}\gcd(a,n)=1\end{cases}}$

$\left({\frac {ab}{n}}\right)=\left({\frac {a}{n}}\right)\left({\frac {b}{n}}\right)$, do $\left({\frac {a^{2}}{p}}\right)=1$ aŭ $\left({\frac {a^{2}}{p}}\right)=0$

$\left({\frac {a}{mn}}\right)=\left({\frac {a}{m}}\right)\left({\frac {a}{n}}\right)$, do $\left({\frac {a}{n^{2}}}\right)=1$ aŭ $\left({\frac {a}{n^{2}}}\right)=0$

Se $a\equiv b{\pmod {n}}$ do $\left({\frac {a}{n}}\right)=\left({\frac {b}{n}}\right)$

Se m kaj n estas neparaj pozitivaj entjeroj do $\left({\frac {m}{n}}\right)=\left({\frac {n}{m}}\right)(-1)^{\frac {(m-1)(n-1)}{4}}$

$\left({\frac {-1}{n}}\right)=(-1)^{\frac {(n-1)}{2}}=\left\{{\begin{array}{cl}1&{\text{se}}\;n\equiv 1{\pmod {4}}\\-1&{\text{se}}\;n\equiv 3{\pmod {4}}\end{array}}\right.$

${\left({\frac {2}{n}}\right)=(-1)^{\frac {(n^{2}-1)}{8}}=\left\{{\begin{array}{cl}1&{\text{se}}\;n\equiv 1{\pmod {8}}\;{\text{ aux }}\;n\equiv 7{\pmod {8}}\\-1&{\text{se}}\;n\equiv 3{\pmod {8}}\;{\text{ aux }}\;n\equiv 5{\pmod {8}}\end{array}}\right.}$

Simile al la simbolo de Legendre:

Se $\left({\frac {a}{n}}\right)=-1$, a estas kvadrata nerestaĵo (mod n).

Se a estas kvadrata restaĵo (mod n) do $\left({\frac {a}{n}}\right)=1$ .

Sed, malsimile al simbolo de Legendre:

Se $\left({\frac {a}{n}}\right)=1$ do a povas esti aŭ ne esti kvadrata restaĵo (mod n).

Ĉi tiu estas ĉar por ke a estu restaĵo (mod n) ĝi devas esti restaĵo module ĉiu primo kiu dividas na n, sed por $\left({\frac {a}{n}}\right)=1$, ĝi povas esti nerestaĵo module nulo, du aŭ iu para kvanto el la primoj dividantaj na n.

Ankaŭ, se $\left({\frac {a}{n}}\right)=0$, do estas PGKD(a, b) > 1.

Motivado

La permanaj algoritmoj uzataj en la 19-a jarcento por primeco-testado kaj faktorigo de entjero, kaj ankaŭ multaj kalkuloj bezonataj por evoluo de algebra nombroteorio, postulis kalkulon de multaj simboloj de Legendre.

Ekzemple, oni scias ke 9907 estas primo. Necesas kalkuli valorojn de $\left({\frac {1001}{9907}}\right)$ kaj $\left({\frac {2183}{9907}}\right)$.

Kvankam, relative facila hodiaŭ, kalkulo kiel

$\left({\frac {1001}{9907}}\right)\equiv 1001^{4953}{\pmod {9907}}$

permane eĉ kun mekanika kalkulilo estas ne tre praktika. La eŭlera kriterio prenas O((log n)³) paŝojn. Uzante la plej kompetentajn modernajn algoritmojn por potencigo, la ekzemplo postulas po proksimume 12 multiplikojn de kvar-ciferaj nombroj kaj dividoj per 9907.

Kalkuloj uzante la simbolon de Legendre

Kalkulo uzante ĉi tiujn regulojn estas multe pli simpla ol per la eŭlera kriterio:

$\left({\frac {1001}{9907}}\right)=\left({\frac {7}{9907}}\right)\left({\frac {11}{9907}}\right)\left({\frac {13}{9907}}\right)$

$\left({\frac {7}{9907}}\right)=-\left({\frac {9907}{7}}\right)=-\left({\frac {2}{7}}\right)=-1$

$\left({\frac {11}{9907}}\right)=-\left({\frac {9907}{11}}\right)=-\left({\frac {7}{11}}\right)=\left({\frac {11}{7}}\right)=\left({\frac {4}{7}}\right)=1$

$\left({\frac {13}{9907}}\right)=\left({\frac {9907}{13}}\right)=\left({\frac {1}{13}}\right)=1$

$\left({\frac {1001}{9907}}\right)=-1$

La alia ekzemplo:

La unua paŝo estas trovo ke 2183 = 59 × 37 (tamen, ĝenerale faktorigo estas malrapida procezo).

$\left({\frac {2183}{9907}}\right)=\left({\frac {59}{9907}}\right)\left({\frac {37}{9907}}\right).$

$\left({\frac {59}{9907}}\right)=-\left({\frac {9907}{59}}\right)=-\left({\frac {54}{59}}\right)=-\left({\frac {2}{59}}\right)\left({\frac {27}{59}}\right)=\left({\frac {27}{59}}\right)$

$=-\left({\frac {59}{27}}\right)=-\left({\frac {5}{27}}\right)=-\left({\frac {2}{5}}\right)=1$

$\left({\frac {37}{9907}}\right)=\left({\frac {9907}{37}}\right)=\left({\frac {9}{37}}\right)=1$

$\left({\frac {2183}{9907}}\right)=1$

Kompreneble, eblas ke iujn el la nombroj en la enaj paŝoj necesas faktorigi.

La samaj kalkuloj, uzante la jakobian simbolon

Jacobi esploris manieron kalkuli la simbolo de Legendre sen faktorigo de iuj nombroj.

$\left({\frac {1001}{9907}}\right)=\left({\frac {9907}{1001}}\right)=\left({\frac {898}{1001}}\right)=\left({\frac {2}{1001}}\right)\left({\frac {449}{1001}}\right)=\left({\frac {449}{1001}}\right)$

$=\left({\frac {1001}{449}}\right)=\left({\frac {103}{449}}\right)=\left({\frac {449}{103}}\right)=\left({\frac {37}{103}}\right)=\left({\frac {103}{37}}\right)$

$=\left({\frac {29}{37}}\right)=\left({\frac {37}{29}}\right)=\left({\frac {8}{29}}\right)=\left({\frac {4}{29}}\right)\left({\frac {2}{29}}\right)=-1.$

$\left({\frac {2183}{9907}}\right)=-\left({\frac {9907}{2183}}\right)=-\left({\frac {1175}{2183}}\right)=\left({\frac {2183}{1175}}\right)=\left({\frac {1008}{1175}}\right)$

$=\left({\frac {16}{1175}}\right)\left({\frac {63}{1175}}\right)=\left({\frac {63}{1175}}\right)=-\left({\frac {1175}{63}}\right)=-\left({\frac {41}{63}}\right)$

$=-\left({\frac {63}{41}}\right)=-\left({\frac {22}{41}}\right)=-\left({\frac {2}{41}}\right)\left({\frac {11}{41}}\right)$

$=-\left({\frac {11}{41}}\right)=-\left({\frac {41}{11}}\right)=-\left({\frac {8}{11}}\right)=-\left({\frac {4}{11}}\right)\left({\frac {2}{11}}\right)=-\left({\frac {2}{11}}\right)=1.$

Kalkula komplikeco

La vico kie la supra nombro estas malpligrandigita module la funda nombro, la supro kaj fundo estas interŝanĝitaj, la supro estas malpligrandigita module la fundo, ... estas la samo kio okazas kiam la plej granda komuna divizoro estas kalkulata uzanta eŭklidan algoritmon. La nura reala diferenco estas la maniero je kiu paraj nombroj estas traktataj kaj tio ke la signo estas ŝanĝita en la jakobia kalkulo kiam ambaŭ nombroj estas ≡ 3 (mod 4). Tiel kalkulado de la Jakobia simbolo, aŭ la simbolo de Legendre se la funda nombro estas primo, estas de la sama kalkula komplikeco kiel eŭklida algoritmo, kaj bezonas O(log n log a) paŝojn.

Tio ke $\left({\frac {2183}{9907}}\right)=1$ kaj 9907 estas primo signifas ke 2183 estas kvadrata restaĵo (mod 9907), sed ne donas aludon pri tio al kiu kvadrato ĝi estas kongrua. La algoritmo de Shanks-Tonelli estas maniero por ekscii.

908² ≡ 2183 (mod 9907).

Primeco-testado

Estas alia eco je kiu jakobia simbolo kaj simbolo de Legendre diferenciĝas. Se la eŭlera kriteria formulo estas uzita module komponigita nombro, la rezulto povas esti aŭ ne esti la valoro de la jakobia simbolo.

Tiel se ne estas sciate ĉu nombro n estas primo aŭ komponigita, oni povas preni hazardan a, kalkuli la jakobian simbolon $\left({\frac {a}{n}}\right)$ kaj kompari ĝi kun eŭlera formulo, Se ili malsamas do n estas komponigita. Se ili egalas por multaj malsamaj valoroj de a, n estas "verŝajne primo".

Ĉi tiu estas la bazo por la primeco-testoj: probableca primeco-testo de Solovay-Strassen kaj ĝia plibonigo primeco-testo de Miller-Rabin.

Vidu ankaŭ

• La simbolo de Kronecker estas ĝeneraligo de la jakobia simbolo al ĉiuj entjeroj.

Eksteraj ligiloj

• Kalkulo de jakobia simbolo kun ekzemploj Arkivigite je 2008-07-20 per la retarkivo Wayback Machine