סימן יעקובי

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

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

הגדרהעריכה

עבור מספר שלם   וּמספר טבעי אי־זוגי  , סימן יעקובי   מוגדר כמכפלת סימני לז׳נדר המתאימים לפירוק של   לגורמיו הראשוניים:

  כאשר  .

עבור כל זוג   סימן לז'נדר מוגדר על ידי:

  •   מתחלק ב־  ללא שארית;
  •   אינו מתחלק ב־  וקיים   שלם המקיים  , כלומר   שארית ריבועית של  ;
  •   אינו מתחלק ב־  ולא קיים   שלם המקיים  , כלומר   אינו שארית ריבועית של  .

 

תכונותעריכה

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

  • אם   ראשוני אי־זוגי, סימן יעקובי הוא פשוט סימן לז׳נדר (כלומר, סימן לז׳נדר הוא מקרה פרטי של סימן יעקובי כאשר   ראשוני אי־זוגי).
  • אם   אז  
  •  
  •   ולכן   (או  )
  •   ולכן   (או  )
  • משפט ההדדיות הריבועית: אם   ו־  מספרים אי־זוגיים שלמים וזרים, אזי מתקיים:

 

  •  
  •  


בדומה לסימן לז׳נדר,
אם   אז   הוא שארית אי־ריבועית  
אם   הוא שארית ריבועית   אז  
אבל, בשונה מסימן לז׳נדר, אם   אז   לא בהכרח שארית ריבועית  .

דוגמאותעריכה

 

 

 

 

 

 

ולכן, סימן יעקובי אינו מגלה אם 33 הוא שארית ריבועית  

קישורים חיצונייםעריכה