Jacobi sembolü

Vikipedi, özgür ansiklopedi
Atla: kullan, ara

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 tamsayıları çarpanlara ayırma olarak kriptografide oldukça önemlidir.

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

Herhangi bir a tamsayısı ve herhangi bir n pozitif tek tamsayı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

\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}


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


\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 \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 tamsayı,alt argüman ("payda")pozitif tek tamsayı olduğunda tanımlanır.

1) Eğer ntek asal sayı ise,sonrasında \Bigg(\frac{a}{n}\Bigg) Jacobi sembolü aynı yazılmış olan Legendre sembolüne eşittir.
2) Eğer a \equiv b \pmod{n} ise \Bigg(\frac{a}{n}\Bigg) = \left(\frac{b}{n}\right)
3)\left(\frac{a}{n}\right) = 
\begin{cases}
\;\;\,0\mbox{ eğer } \gcd(a,n) \ne 1
\\\pm1\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) \left(\frac{ab}{n}\right) = \Bigg(\frac{a}{n}\Bigg)\left(\frac{b}{n}\right), bu yüzden \left(\frac{a^2}{n}\right) = 1 \textrm{\ ya da \ } 0
5) \left(\frac{a}{mn}\right)=\left(\frac{a}{m}\right)\left(\frac{a}{n}\right), yani \left(\frac{a}{n^2}\right) = 1 \textrm{\ ya da\ } 0

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

6) \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) 
\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) 
\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 \left(\frac{a}{n}\right) = -1 ise abir kuadratik kalan olmayandır \pmod{n} e göre.
Eğer a bir kuadratik kalan ise \pmod{n} ve a \not\equiv 0\pmod n, sonrasında \left(\frac{a}{n}\right) = 1

Fakat Legendre sembolü gibi değilse,

Eğer \left(\frac{a}{n}\right) = 1 ise a bir kuadratik kalan olabilir veya olmayabilir \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" göreceli değilse,kural 3 sonucu 0 verir.
  4. Aksi takdirde "pay" ve "payda" şuan göreceli tek pozitif tamsayı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ü (\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 (\tfrac{-1}{p}) ve (\tfrac{2}{p}) "pay"ın çarpımsalıdır

Legendre sembolü kullanarak[değiştir | kaynağı değiştir]


\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

Jacobi sembolü kullanarak[değiştir | kaynağı değiştir]


 \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{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 kritik formülü bir birleşik sayı modülü olarak kullanılırsa,sonuç Jacobi sembol değeri olabilir veya olmayabilir ve hatta gerçek değer -1 veya 1 olmayabilir.

\left(\frac{19}{45}\right) = 1\quad\textrm{ ve }\quad19^{(45-1)/2} \equiv 1\pmod{45}
\left(\frac{8}{21}\right) = -1\quad\textrm{ ama }\quad8^{(21-1)/2} \equiv 1\pmod{21}
\left(\frac{5}{21}\right) = 1\quad\textrm{ ama }\quad5^{(21-1)/2} \equiv 16\pmod{21}

Ayrıca bakınız[değiştir | kaynağı değiştir]

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

  • Ireland, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (Second edition), New York: Springer, ISBN 0-387-97329-X