סימן יעקובי

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

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

הגדרה

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

$\left({\frac {a}{n}}\right)=\left({\frac {a}{p_{1}}}\right)^{\alpha _{1}}\cdots \left({\frac {a}{p_{k}}}\right)^{\alpha _{k}},~n=p_{1}^{\alpha _{1}}\cdots p_{k}^{\alpha _{k}}$

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

$a$ מתחלק ב-$p$ ללא שארית $a$ שארית ריבועית של $p$ $a$ אינו שארית ריבועית של $p$

$\left({\frac {a}{p}}\right)={\begin{cases}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{cases}}$

תכונות

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

• אם $n$ ראשוני, סימן יעקובי הוא סימן לז'נדר.
• אם מתקיים $a\equiv b{\pmod {n}}$ אז מתקיים גם $\left({\frac {a}{n}}\right)=\left({\frac {b}{n}}\right)$
• $\left({\frac {a}{n}}\right)={\begin{cases}0&:\gcd(a,n)\neq 1\\\pm 1&:\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)&:n\equiv 1{\pmod {4}}{\text{ or }}m\equiv 1{\pmod {4}}\\-\left({\frac {n}{m}}\right)&:n\equiv m\equiv 3{\pmod {4}}\end{cases}}$

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

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

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

דוגמאות

${\begin{aligned}\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)^{{\frac {5-1}{2}}\cdot {\frac {3-1}{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)^{\frac {1009-1}{2}}=\left({\frac {1009}{3}}\right)=\left({\frac {1}{3}}\right)=1\\\left({\frac {11}{1009}}\right)=\left({\frac {1009}{11}}\right)\cdot (-1)^{{\frac {1009-1}{2}}\cdot {\frac {11-1}{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\end{aligned}}$

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