סימן יעקובי

בתורת המספרים, סימן יעקובי הוא הכללה של סימן לז'נדר.

שימושו העיקרי הוא בפירוק ובדיקת ראשוניות של מספרים שלמים, בעיקר בשביל יישומים שונים בתחום הקריפטוגרפיה.

הגדרה

עבור מספר שלם a ומספר שלם אי-זוגי חיובי n, סימן יעקובי מוגדר כמכפלת סימני לז'נדר המתאימים לפירוק n לגורמיו הראשוניים:

${\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{where }}n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{k}^{\alpha _{k}}$

עבור כל זוג (p,a) סימן לז'נדר מוגדר על ידי:

a מתחלק ב-p ללא שארית a לא מתחלק ב-p וקיים x שלם המקיים (x²≡a (mod p, כלומר a שארית ריבועית של p a לא מתחלק ב-p ולא קיים x שלם המקיים (x²≡a (mod p, כלומר a אינו שארית ריבועית של p

$\left({\frac {a}{p}}\right)=\left\{{\begin{matrix}0&a\equiv 0{\pmod {p}}&\\1&a\not \equiv 0{\pmod {p}};&a\equiv x^{2}{\pmod {p}}\\-1&a\not \equiv 0{\pmod {p}};&a\not \equiv x^{2}{\pmod {p}}\end{matrix}}\right.$

תכונות

התכונות של סימן יעקובי נובעות ישירות מהקשר שלו לסימן לז'נדר.

• אם n ראשוני, סימן יעקובי הוא סימן לז'נדר.
• אם מתקיים $a\equiv b{\pmod {n}}$ אז מתקיים גם: $\left({\frac {a}{n}}\right)=\left({\frac {b}{n}}\right)$
• $\left({\frac {a}{n}}\right)={\begin{cases}\;\;\,0{\mbox{ if }}\gcd(a,n)\neq 1\\\pm 1{\mbox{ if }}\gcd(a,n)=1\end{cases}}$
• $\left({\frac {ab}{n}}\right)=\left({\frac {a}{n}}\right)\left({\frac {b}{n}}\right)$ ולכן $\left({\frac {a^{2}}{n}}\right)=1$ (או $0$)

• $\left({\frac {a}{mn}}\right)=\left({\frac {a}{m}}\right)\left({\frac {a}{n}}\right)$ ולכן $\left({\frac {a}{n^{2}}}\right)=1$ (או $0$)

• משפט ההדדיות הריבועית: אם m ו-n מספרים אי-זוגיים שלמים וזרים אז

$\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{ or }}m\equiv 1{\pmod {4}}\\-\left({\frac {n}{m}}\right)&{\text{if }}n\equiv m\equiv 3{\pmod {4}}\end{cases}}$

• $\left({\frac {-1}{n}}\right)=(-1)^{\tfrac {n-1}{2}}={\begin{cases}\;\;\,1&{\text{if }}n\equiv 1{\pmod {4}}\\-1&{\text{if }}n\equiv 3{\pmod {4}}\end{cases}}$

• $\left({\frac {2}{n}}\right)=(-1)^{\tfrac {n^{2}-1}{8}}={\begin{cases}\;\;\,1&{\text{if }}n\equiv 1,7{\pmod {8}}\\-1&{\text{if }}n\equiv 3,5{\pmod {8}}\end{cases}}$

בדומה לסימן לז'נדר,
אם $\left({\frac {a}{n}}\right)=-1$ אז $a$ הוא שארית אי-ריבועית ${\pmod {n}}$
אם $a$ הוא שארית ריבועית ${\pmod {n}}$ אז $\left({\frac {a}{n}}\right)=1$
אבל, בשונה מסימן לז'נדר, אם $\left({\frac {a}{n}}\right)=1$ אז $a$ לא בהכרח שארית ריבועית ${\pmod {n}}$.

דוגמאות

$\left({\frac {33}{5045}}\right)=\left({\frac {33}{5\cdot 1009}}\right)=\left({\frac {33}{5}}\right)\cdot \left({\frac {33}{1009}}\right)$

$\left({\frac {33}{5}}\right)=\left({\frac {3\cdot 11}{5}}\right)=\left({\frac {3}{5}}\right)\cdot \left({\frac {11}{5}}\right)=\left({\frac {5}{3}}\right)\cdot (-1)^{{{5-1} \over 2}\cdot {{3-1} \over 2}}\left({\frac {1}{5}}\right)=\left({\frac {2}{3}}\right)\cdot 1=-1=-1$

$\left({\frac {33}{1009}}\right)=\left({\frac {3}{1009}}\right)\cdot \left({\frac {11}{1009}}\right)$

$\left({\frac {3}{1009}}\right)=\left({\frac {1009}{3}}\right)\cdot (-1)^{{1009-1} \over 2}=\left({\frac {1009}{3}}\right)=\left({\frac {1}{3}}\right)=1$

$\left({\frac {11}{1009}}\right)=\left({\frac {1009}{11}}\right)\cdot (-1)^{{{1009-1} \over 2}\cdot {{11-1} \over 2}}=\left({\frac {1009}{11}}\right)=\left({\frac {8}{11}}\right)={\left({\frac {2}{11}}\right)}^{3}=(-1)^{3}=-1$

$\left({\frac {33}{5045}}\right)=\left({\frac {33}{5\cdot 1009}}\right)=\left({\frac {33}{5}}\right)\cdot \left({\frac {33}{1009}}\right)=(-1)\cdot (-1)=1$

ולכן, סימן יעקובי לא מספק מידע לגבי אם 33 הוא שארית ריבועית ${\pmod {5045}}$

ערך זה מוגש באדיבות ויקיפדיה העברית, תחת רשיון ייחוס שיתוף זהה (CC BY-SA 3.0). (הדף המקורי, רשימת התורמים)
הערך בוויקיפדיה גדול מערך זה ב +962 תווים

לעדכון מוויקיפדיה, לחץ כאן.

רענן נתונים