סימן יעקובי

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

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

הגדרהעריכה

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

 

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

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

 

תכונותעריכה

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

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

 

  •  
  •  


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

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

 

 

 

 

 

 

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

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