סימן יעקובי

From האנציקלופדיה היהודית
Jump to navigation Jump to search

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

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

הגדרה[edit | edit source]

עבור מספר שלם 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

תכונות[edit | edit source]

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

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


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

דוגמאות[edit | edit source]













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

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

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

NivdakVeushar.png