„Jacobi-szimbólum” változatai közötti eltérés

[ellenőrzött változat]

← Régebbi szerkesztés Újabb szerkesztés →

Tartalom törölve Tartalom hozzáadva

Sorban

A lap 2023. november 24., 11:47-kori változata

A számelméletben a Jacobi-szimbólum a Legendre-szimbólum általánosítása. Szerepet játszik prímteszt- és prímfelbontási algoritmusokban, és így jelentőséggel bír a kriptográfia számára is.

Definíciója

Ha $P>2$ páratlan szám, a hozzá relatív prím egész, akkor

\left({\frac {a}{P}}\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}}

ahol $P=p_{1}^{\alpha _{1}}\cdots p_{k}^{\alpha _{k}}$ a prímhatványfelbontás, és a jobb oldalon Legendre-szimbólumok állnak. Ha a-nak és P-nek van 1-nél nagyobb közös osztója, akkor $\left({\frac {a}{P}}\right)=0$ .

Tulajdonságai

Ha $a\equiv b{\pmod {P}}$ , akkor ${\bigg (}{\frac {a}{P}}{\bigg )}={\bigg (}{\frac {b}{P}}{\bigg )}$
$\left({\frac {1}{P}}\right)=1$
${\bigg (}{\frac {ab}{P}}{\bigg )}={\bigg (}{\frac {a}{P}}{\bigg )}{\bigg (}{\frac {b}{P}}{\bigg )}$
${\bigg (}{\frac {-1}{P}}{\bigg )}=(-1)^{\frac {P-1}{2}}$
$\left({\frac {2}{P}}\right)=(-1)^{\frac {P^{2}-1}{8}}$
Ha P és Q relatív prím páratlan számok, akkor ${\bigg (}{\frac {P}{Q}}{\bigg )}={\bigg (}{\frac {Q}{P}}{\bigg )}(-1)^{\frac {(P-1)(Q-1)}{4}}$

Források

Otto Forster. Algorithmische Zahlentheorie, 2 (német nyelven), Springer Spektrum Wiesbaden. DOI: 10.1007/978-3-658-06540-9 (2015). ISBN 978-3-658-06540-9
Algoritmusok - Márton Gyöngyvér (ms.sapientia.ro)

@@ 1. sor: / 1. sor: @@
-A [[számelmélet]]ben a '''Jacobi-szimbólum''' a [[Legendre-szimbólum]] általánosítása.
+A [[számelmélet]]ben a '''Jacobi-szimbólum''' a [[Legendre-szimbólum]] általánosítása. Szerepet játszik [[prímteszt]]- és [[Prímfelbontás|prímfelbontási]] algoritmusokban, és így jelentőséggel bír a [[kriptográfia]] számára is.
 ==Definíciója==
-Ha ''P''>2 [[Páros és páratlan számok|páratlan szám]], ''a'' hozzá [[Relatív prímek|relatív prím]] egész, akkor
+Ha <math>P>2</math> [[Páros és páratlan számok|páratlan szám]], ''a'' hozzá [[Relatív prímek|relatív prím]] egész, akkor
 :<math>\left(\frac{a}{P}\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}</math>
-ahol <math>P=p_1^{\alpha_1}\cdots p_k^{\alpha_k}</math> a prímhatványfelbontás.
+ahol <math>P=p_1^{\alpha_1}\cdots p_k^{\alpha_k}</math> a prímhatványfelbontás, és a jobb oldalon Legendre-szimbólumok állnak.
 Ha ''a''-nak és ''P''-nek van 1-nél nagyobb közös osztója, akkor <math>\left(\frac{a}{P}\right)=0</math>.
@@ 22. sor: / 22. sor: @@
 #<math>
 \left(\frac{2}{P}\right) = (-1)^{\frac{P^2-1}{8}}</math>
-#Ha ''P,Q'' relatív prím páratlan számok, akkor <math>
+#Ha ''P'' és ''Q'' relatív prím páratlan számok, akkor <math>
 \bigg(\frac{P}{Q}\bigg) = \bigg(\frac{Q}{P}\bigg)(-1)^{\frac{(P-1)(Q-1)}{4}}</math>
 == Források ==
+* {{Cite book |author=Otto Forster |title=Algorithmische Zahlentheorie |url=https://link.springer.com/book/10.1007/978-3-658-06540-9 |edition=2 |year=2015 |publisher=Springer Spektrum Wiesbaden |language=német |isbn=978-3-658-06540-9 |doi=10.1007/978-3-658-06540-9}}
 * [http://www.ms.sapientia.ro/~mgyongyi/Crypto/alapok.html Algoritmusok - Márton Gyöngyvér (ms.sapientia.ro)]