Jacobi sembolü - Vikipedi
İçeriğe atla
Ana menü
Gezinti
  • Anasayfa
  • Hakkımızda
  • İçindekiler
  • Rastgele madde
  • Seçkin içerik
  • Yakınımdakiler
Katılım
  • Deneme tahtası
  • Köy çeşmesi
  • Son değişiklikler
  • Dosya yükle
  • Topluluk portalı
  • Wikimedia dükkânı
  • Yardım
  • Özel sayfalar
Vikipedi Özgür Ansiklopedi
Ara
  • Bağış yapın
  • Hesap oluştur
  • Oturum aç
  • Bağış yapın
  • Hesap oluştur
  • Oturum aç

İçindekiler

  • Giriş
  • 1 Tanım
  • 2 Özellikleri
  • 3 Jacobi sembol hesaplanması
  • 4 Hesaplama Örnekleri
    • 4.1 Legendre sembolü kullanarak
    • 4.2 Jacobi sembolü kullanarak
  • 5 Asallık testi
  • 6 Ayrıca bakınız
  • 7 Kaynakça

Jacobi sembolü

  • বাংলা
  • Català
  • Čeština
  • Deutsch
  • English
  • Esperanto
  • Español
  • فارسی
  • Suomi
  • Français
  • עברית
  • Magyar
  • İtaliano
  • 日本語
  • ភាសាខ្មែរ
  • 한국어
  • Nederlands
  • Polski
  • Português
  • Русский
  • Slovenščina
  • Українська
  • Tiếng Việt
  • 中文
Bağlantıları değiştir
  • Madde
  • Tartışma
  • Oku
  • Değiştir
  • Kaynağı değiştir
  • Geçmişi gör
Araçlar
Eylemler
  • Oku
  • Değiştir
  • Kaynağı değiştir
  • Geçmişi gör
Genel
  • Sayfaya bağlantılar
  • İlgili değişiklikler
  • Kalıcı bağlantı
  • Sayfa bilgisi
  • Bu sayfayı kaynak göster
  • Kısaltılmış URL'yi al
  • Karekodu indir
Yazdır/dışa aktar
  • Bir kitap oluştur
  • PDF olarak indir
  • Basılmaya uygun görünüm
Diğer projelerde
  • Vikiveri ögesi
Görünüm
Vikipedi, özgür ansiklopedi
Carl Gustav Jacob Jacobi (1804-1851)

Jacobi sembolü Legendre sembolünün bir genellemesidir. 1837 yılında Jacobi tarafından tanıtılan bu teori, modüler aritmetik ve sayılar teorisinin diğer dallarındandır ama ana kullanımı hesaplamada sayılar teorisi, özellikle asallık testi ve tam sayıları çarpanlara ayırma olarak kriptografide oldukça önemlidir.

Tanım

[değiştir | kaynağı değiştir]

Herhangi bir a tam sayısı ve herhangi bir n pozitif tek tam sayısı için Legendre sembolünün ana faktörlerine karşılık olarak Jacobi sembolünün bir ürünü olarak tanımlanır

( a n ) = ( a p 1 ) α 1 ( a p 2 ) α 2 ⋯ ( a p k ) α k  ,  n = p 1 α 1 p 2 α 2 ⋯ p k α k {\displaystyle {\Bigg (}{\frac {a}{n}}{\Bigg )}=\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}}{\mbox{ , }}n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{k}^{\alpha _{k}}} {\displaystyle {\Bigg (}{\frac {a}{n}}{\Bigg )}=\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}}{\mbox{ , }}n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{k}^{\alpha _{k}}}


( a p ) {\displaystyle \left({\tfrac {a}{p}}\right)} {\displaystyle \left({\tfrac {a}{p}}\right)} a {\displaystyle a} {\displaystyle a} ve tüm tek sayılar için p {\displaystyle p} {\displaystyle p}tarafından sağlanan değerler

( a p ) = { 0  if  a ≡ 0 ( mod p ) + 1  if  a ≢ 0 ( mod p )  ve bazı x tamsayısı için,  a ≡ x 2 ( mod p ) − 1  böyle bir x olmaması durumunda  {\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}\;\;\,0{\mbox{ if }}a\equiv 0{\pmod {p}}\\+1{\mbox{ if }}a\not \equiv 0{\pmod {p}}{\mbox{ ve bazı x tamsayısı için, }}\;a\equiv x^{2}{\pmod {p}}\\-1{\mbox{ böyle bir x olmaması durumunda }}\end{cases}}} {\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}\;\;\,0{\mbox{ if }}a\equiv 0{\pmod {p}}\\+1{\mbox{ if }}a\not \equiv 0{\pmod {p}}{\mbox{ ve bazı x tamsayısı için, }}\;a\equiv x^{2}{\pmod {p}}\\-1{\mbox{ böyle bir x olmaması durumunda }}\end{cases}}}

Normal kuralı takip eden boş bir ürün için ( a 1 ) = 1. {\displaystyle \left({\tfrac {a}{1}}\right)=1.} {\displaystyle \left({\tfrac {a}{1}}\right)=1.}aynı değere sahip alt argümanların ne zaman Legendre ne zaman Jacobi sembolleri olduğu ayırt edilemez.

Özellikleri

[değiştir | kaynağı değiştir]

Aşağıdaki gerçekler, jacobi sembolü ve legendre sembolü karşılıklılık yasalarına karşılık gelen özellikleri tanımından kesintiler bulundurur. Şunu belirtmek gerekir ki, Jacobi sembolü sadece üst argüman("pay")bir tam sayı, alt argüman ("payda")pozitif tek tam sayı olduğunda tanımlanır.

1) Eğer n {\displaystyle n} {\displaystyle n}tek asal sayı ise,sonrasında ( a n ) {\displaystyle {\Bigg (}{\frac {a}{n}}{\Bigg )}} {\displaystyle {\Bigg (}{\frac {a}{n}}{\Bigg )}} Jacobi sembolü aynı yazılmış olan Legendre sembolüne eşittir.
2) Eğer a ≡ b ( mod n ) {\displaystyle a\equiv b{\pmod {n}}} {\displaystyle a\equiv b{\pmod {n}}} ise ( a n ) = ( b n ) {\displaystyle {\Bigg (}{\frac {a}{n}}{\Bigg )}=\left({\frac {b}{n}}\right)} {\displaystyle {\Bigg (}{\frac {a}{n}}{\Bigg )}=\left({\frac {b}{n}}\right)}
3) ( a n ) = { 0  eğer  gcd ( a , n ) ≠ 1 ± 1  eğer  gcd ( a , n ) = 1 {\displaystyle \left({\frac {a}{n}}\right)={\begin{cases}\;\;\,0{\mbox{ eğer }}\gcd(a,n)\neq 1\\\pm 1{\mbox{ eğer }}\gcd(a,n)=1\end{cases}}} {\displaystyle \left({\frac {a}{n}}\right)={\begin{cases}\;\;\,0{\mbox{ eğer }}\gcd(a,n)\neq 1\\\pm 1{\mbox{ eğer }}\gcd(a,n)=1\end{cases}}}

Eğer üst veya alt argüman sabit ise,tamamen çarpımsal fonksiyon içinde kalan argüman Jacobi sembolüdür:

4) ( a b n ) = ( a n ) ( b n ) {\displaystyle \left({\frac {ab}{n}}\right)={\Bigg (}{\frac {a}{n}}{\Bigg )}\left({\frac {b}{n}}\right)} {\displaystyle \left({\frac {ab}{n}}\right)={\Bigg (}{\frac {a}{n}}{\Bigg )}\left({\frac {b}{n}}\right)}, bu yüzden ( a 2 n ) = 1 \ yada\  0 {\displaystyle \left({\frac {a^{2}}{n}}\right)=1{\textrm {\ yada\ }}0} {\displaystyle \left({\frac {a^{2}}{n}}\right)=1{\textrm {\ yada\ }}0}
5) ( a m n ) = ( a m ) ( a n ) {\displaystyle \left({\frac {a}{mn}}\right)=\left({\frac {a}{m}}\right)\left({\frac {a}{n}}\right)} {\displaystyle \left({\frac {a}{mn}}\right)=\left({\frac {a}{m}}\right)\left({\frac {a}{n}}\right)}, yani ( a n 2 ) = 1 \ yada\  0 {\displaystyle \left({\frac {a}{n^{2}}}\right)=1{\textrm {\ yada\ }}0} {\displaystyle \left({\frac {a}{n^{2}}}\right)=1{\textrm {\ yada\ }}0}

karesel karışıklık yasası:Eğer m ve n göreceli tek asal tam sayılar ise

6) ( m n ) = ( n m ) ( − 1 ) m − 1 2 n − 1 2 = { ( n m ) if  n ≡ 1 ( mod 4 )  ya da  m ≡ 1 ( mod 4 ) − ( n m ) if  n ≡ m ≡ 3 ( mod 4 ) {\displaystyle \left({\frac {m}{n}}\right)=\left({\frac {n}{m}}\right)(-1)^{{\tfrac {m-1}{2}}{\tfrac {n-1}{2}}}={\begin{cases}\;\;\;\left({\frac {n}{m}}\right)&{\text{if }}n\equiv 1{\pmod {4}}{\text{ ya da }}m\equiv 1{\pmod {4}}\\-\left({\frac {n}{m}}\right)&{\text{if }}n\equiv m\equiv 3{\pmod {4}}\end{cases}}} {\displaystyle \left({\frac {m}{n}}\right)=\left({\frac {n}{m}}\right)(-1)^{{\tfrac {m-1}{2}}{\tfrac {n-1}{2}}}={\begin{cases}\;\;\;\left({\frac {n}{m}}\right)&{\text{if }}n\equiv 1{\pmod {4}}{\text{ ya da }}m\equiv 1{\pmod {4}}\\-\left({\frac {n}{m}}\right)&{\text{if }}n\equiv m\equiv 3{\pmod {4}}\end{cases}}}

ve ekleri

7) ( − 1 n ) = ( − 1 ) n − 1 2 = { 1 eğer  n ≡ 1 ( mod 4 ) − 1 eğer  n ≡ 3 ( mod 4 ) {\displaystyle \left({\frac {-1}{n}}\right)=(-1)^{\tfrac {n-1}{2}}={\begin{cases}\;\;\,1&{\text{eğer }}n\equiv 1{\pmod {4}}\\-1&{\text{eğer }}n\equiv 3{\pmod {4}}\end{cases}}} {\displaystyle \left({\frac {-1}{n}}\right)=(-1)^{\tfrac {n-1}{2}}={\begin{cases}\;\;\,1&{\text{eğer }}n\equiv 1{\pmod {4}}\\-1&{\text{eğer }}n\equiv 3{\pmod {4}}\end{cases}}}
8) ( 2 n ) = ( − 1 ) n 2 − 1 8 = { 1 eğer  n ≡ 1 , 7 ( mod 8 ) − 1 eğer  n ≡ 3 , 5 ( mod 8 ) {\displaystyle \left({\frac {2}{n}}\right)=(-1)^{\tfrac {n^{2}-1}{8}}={\begin{cases}\;\;\,1&{\text{eğer }}n\equiv 1,7{\pmod {8}}\\-1&{\text{eğer }}n\equiv 3,5{\pmod {8}}\end{cases}}} {\displaystyle \left({\frac {2}{n}}\right)=(-1)^{\tfrac {n^{2}-1}{8}}={\begin{cases}\;\;\,1&{\text{eğer }}n\equiv 1,7{\pmod {8}}\\-1&{\text{eğer }}n\equiv 3,5{\pmod {8}}\end{cases}}}

Legendre sembolü gibi,

Eğer ( a n ) = − 1 {\displaystyle \left({\frac {a}{n}}\right)=-1} {\displaystyle \left({\frac {a}{n}}\right)=-1} ise a {\displaystyle a} {\displaystyle a}bir kuadratik kalan olmayandır ( mod n ) {\displaystyle {\pmod {n}}} {\displaystyle {\pmod {n}}} e göre.
Eğer a {\displaystyle a} {\displaystyle a} bir kuadratik kalan ise ( mod n ) {\displaystyle {\pmod {n}}} {\displaystyle {\pmod {n}}} ve a ≢ 0 ( mod n ) {\displaystyle a\not \equiv 0{\pmod {n}}} {\displaystyle a\not \equiv 0{\pmod {n}}}, sonrasında ( a n ) = 1 {\displaystyle \left({\frac {a}{n}}\right)=1} {\displaystyle \left({\frac {a}{n}}\right)=1}

Fakat Legendre sembolü gibi değilse,

Eğer ( a n ) = 1 {\displaystyle \left({\frac {a}{n}}\right)=1} {\displaystyle \left({\frac {a}{n}}\right)=1} ise a {\displaystyle a} {\displaystyle a} bir kuadratik kalan olabilir veya olmayabilir ( mod n ) {\displaystyle {\pmod {n}}} {\displaystyle {\pmod {n}}}.

Jacobi sembol hesaplanması

[değiştir | kaynağı değiştir]

yukarıdaki formüller için etkin yol ((log a)(log b)) dir.Jacobi sembolünün hesaplanmasında kullanılan algoritma,iki sayının obebini bulan Öklid algortiması ile benzerdir.

  1. kural 2 kullanılarak "pay" mod "payda" azaltılır.
  2. kural 4 ve kural 8 kullanılarak "pay"dan herhangi 2 faktör ayıklanır.
  3. Eğer "pay" 1 ise, kural 3 ve 4 sonucu 1 verir.Eğer "pay" ve "payda" aralarında asal değilse, kural 3 sonucu 0 verir.
  4. Aksi takdirde "pay" ve "payda" şu an göreceli tek pozitif tam sayıdır, bu yüzden kural 6 yı ters çevirip sonrasında 1.adıma dönebiliriz.

Hesaplama Örnekleri

[değiştir | kaynağı değiştir]

Legendre sembolü ( a p ) {\displaystyle ({\tfrac {a}{p}})} {\displaystyle ({\tfrac {a}{p}})} sadece tek asal sayılar için tanımlanır.Bu Jacobi sembolü olarak aynı kurallara itaat eder (yani, karşılıklılık ve ek için formüller ( − 1 p ) {\displaystyle ({\tfrac {-1}{p}})} {\displaystyle ({\tfrac {-1}{p}})} ve ( 2 p ) {\displaystyle ({\tfrac {2}{p}})} {\displaystyle ({\tfrac {2}{p}})} "pay"ın çarpımsalıdır

Legendre sembolü kullanarak

[değiştir | kaynağı değiştir]
( 1001 9907 ) = ( 7 9907 ) ( 11 9907 ) ( 13 9907 ) . {\displaystyle \left({\frac {1001}{9907}}\right)=\left({\frac {7}{9907}}\right)\left({\frac {11}{9907}}\right)\left({\frac {13}{9907}}\right).} {\displaystyle \left({\frac {1001}{9907}}\right)=\left({\frac {7}{9907}}\right)\left({\frac {11}{9907}}\right)\left({\frac {13}{9907}}\right).}
( 7 9907 ) = − ( 9907 7 ) = − ( 2 7 ) = − 1 {\displaystyle \left({\frac {7}{9907}}\right)=-\left({\frac {9907}{7}}\right)=-\left({\frac {2}{7}}\right)=-1} {\displaystyle \left({\frac {7}{9907}}\right)=-\left({\frac {9907}{7}}\right)=-\left({\frac {2}{7}}\right)=-1}
( 11 9907 ) = − ( 9907 11 ) = − ( 7 11 ) = ( 11 7 ) = ( 4 7 ) = 1 {\displaystyle \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} {\displaystyle \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}
( 13 9907 ) = ( 9907 13 ) = ( 1 13 ) = 1 {\displaystyle \left({\frac {13}{9907}}\right)=\left({\frac {9907}{13}}\right)=\left({\frac {1}{13}}\right)=1} {\displaystyle \left({\frac {13}{9907}}\right)=\left({\frac {9907}{13}}\right)=\left({\frac {1}{13}}\right)=1}
( 1001 9907 ) = − 1 {\displaystyle \left({\frac {1001}{9907}}\right)=-1} {\displaystyle \left({\frac {1001}{9907}}\right)=-1}

Jacobi sembolü kullanarak

[değiştir | kaynağı değiştir]
( 1001 9907 ) = ( 9907 1001 ) = ( 898 1001 ) = ( 2 1001 ) ( 449 1001 ) = ( 449 1001 ) {\displaystyle \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)} {\displaystyle \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)}
= ( 1001 449 ) = ( 103 449 ) = ( 449 103 ) = ( 37 103 ) = ( 103 37 ) {\displaystyle =\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)} {\displaystyle =\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)}
= ( 29 37 ) = ( 37 29 ) = ( 8 29 ) = ( 2 29 ) 3 = − 1. {\displaystyle =\left({\frac {29}{37}}\right)=\left({\frac {37}{29}}\right)=\left({\frac {8}{29}}\right)=\left({\frac {2}{29}}\right)^{3}=-1.} {\displaystyle =\left({\frac {29}{37}}\right)=\left({\frac {37}{29}}\right)=\left({\frac {8}{29}}\right)=\left({\frac {2}{29}}\right)^{3}=-1.}

Asallık testi

[değiştir | kaynağı değiştir]

Legendre ve Jacobi sembolünün farklı başka yolları yoktur.Eğer Euler kriteri asal olmayan bir sayı için uygulanırsa, sonuç Jacobi sembol değeri ile farklı olabilir ve hatta gerçek değer -1 veya 1 olmayabilir.

( 19 45 ) = 1 ve 19 ( 45 − 1 ) / 2 ≡ 1 ( mod 45 ) {\displaystyle \left({\frac {19}{45}}\right)=1\quad {\textrm {ve}}\quad 19^{(45-1)/2}\equiv 1{\pmod {45}}} {\displaystyle \left({\frac {19}{45}}\right)=1\quad {\textrm {ve}}\quad 19^{(45-1)/2}\equiv 1{\pmod {45}}}
( 8 21 ) = − 1 ama 8 ( 21 − 1 ) / 2 ≡ 1 ( mod 21 ) {\displaystyle \left({\frac {8}{21}}\right)=-1\quad {\textrm {ama}}\quad 8^{(21-1)/2}\equiv 1{\pmod {21}}} {\displaystyle \left({\frac {8}{21}}\right)=-1\quad {\textrm {ama}}\quad 8^{(21-1)/2}\equiv 1{\pmod {21}}}
( 5 21 ) = 1 ama 5 ( 21 − 1 ) / 2 ≡ 16 ( mod 21 ) {\displaystyle \left({\frac {5}{21}}\right)=1\quad {\textrm {ama}}\quad 5^{(21-1)/2}\equiv 16{\pmod {21}}} {\displaystyle \left({\frac {5}{21}}\right)=1\quad {\textrm {ama}}\quad 5^{(21-1)/2}\equiv 16{\pmod {21}}}

Ayrıca bakınız

[değiştir | kaynağı değiştir]
  • The Kronecker symbol is a generalization of the Jacobi symbol to all integers.
  • The power residue symbol is a generalization for third, fourth, and higher powers.

Kaynakça

[değiştir | kaynağı değiştir]
  • Cohen, Henri (1993), A Course in Computational Algebraic Number Theory, Berlin: Springer, ISBN 3-540-55640-0 
  • Ireland, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (Second edition), New York: Springer, ISBN 0-387-97329-X 
  • Lemmermeyer, Franz (2000), Reciprocity Laws: from Euler to Eisenstein, Berlin: Springer, ISBN 3-540-66957-4 
"https://tr.wikipedia.org/w/index.php?title=Jacobi_sembolü&oldid=34133894" sayfasından alınmıştır
Kategori:
  • Modüler aritmetik
  • Sayfa en son 20.49, 26 Ekim 2024 tarihinde değiştirildi.
  • Metin Creative Commons Atıf-AynıLisanslaPaylaş Lisansı altındadır ve ek koşullar uygulanabilir. Bu siteyi kullanarak Kullanım Şartlarını ve Gizlilik Politikasını kabul etmiş olursunuz.
    Vikipedi® (ve Wikipedia®) kâr amacı gütmeyen kuruluş olan Wikimedia Foundation, Inc. tescilli markasıdır.
  • Gizlilik politikası
  • Vikipedi hakkında
  • Sorumluluk reddi
  • Davranış Kuralları
  • Geliştiriciler
  • İstatistikler
  • Çerez politikası
  • Mobil görünüm
  • Wikimedia Foundation
  • Powered by MediaWiki
Jacobi sembolü
Konu ekle