שדות גלואה, ביד: GF(8) בטבלה אחת

ברשימה על ריד־סולומון, שחזור של נתונים שאבדו דרש חילוק אחד: חילוק ב־2 הפך לכפל ב־4, כי 2 × 4 = 8 = 1 מודולו 7. זה עבד רק כי 7 ראשוני. מחשבים רוצים שדות שהגודל שלהם הוא חזקה של שתיים, כדי שכל סימבול יהיה מספר שלם של ביטים, ו־8, 16 או 256 הם לא ראשוניים. הרשימה הזו מראה איך פותרים את זה.

מה הופך קבוצה לשדה

שדה הוא קבוצה עם חיבור וכפל שמתנהגים כמו שמצפים ממספרים רגילים: שניהם חילופיים וקיבוציים, הכפל מתפלג על החיבור, יש 0 ו־1, לכל איבר יש נגדי, ולכל איבר חוץ מ־0 יש הופכי, מספר שכופלים בו ומקבלים 1.

הכלל האחרון הוא מה שמאפשר חילוק, והוא זה שנשבר בקלות. שדה סופי הוא שדה עם מספר סופי של איברים. קוראים להם גם שדות גלואה, על שם אווריסט גלואה, וכותבים GF(q) לשדה עם q איברים.

למה מודולו 7 עובד ומודולו 8 לא

כופלים את 2 בכל מספר מודולו 7: 0, 2, 4, 6, 1, 3, 5. כל ערך מופיע פעם אחת, כולל 1, ב־2 × 4. אז ל־2 יש הופכי, 4. אותו דבר נכון לכל מספר שאינו אפס מודולו 7, ומודולו כל ראשוני p. השלמים מודולו p הם השדה GF(p).

כופלים את 2 בכל מספר מודולו 8: 0, 2, 4, 6, 0, 2, 4, 6. יוצאים רק מספרים זוגיים, אז 1 אף פעם לא יוצא, ול־2 אין הופכי. יותר גרוע, 2 × 4 = 0 מודולו 8: שני מספרים שאינם אפס שמכפלתם אפס. חשבון מודולו 8 הוא לא שדה, וגם לא חשבון מודולו כל מספר שאינו ראשוני.

אז את שמונת המספרים 0 עד 7 אי אפשר להפוך לשדה עם חשבון רגיל. עם חשבון אחר אפשר.

בונים את GF(8)

קוראים כל מספר של 3 ביטים כפולינום שהמקדמים שלו הם הביטים. 6 הוא 110 בבינארי, אז הוא x² + x. 3 הוא 011, אז x + 1. המקדמים עצמם שייכים ל־GF(2), השלמים מודולו 2, שבהם 1 + 1 = 0.

חיבור מחבר מקדמים מודולו 2, וזה XOR על הביטים. 5 + 3 הוא 101 XOR 011 = 110 = 6. כל איבר הוא הנגדי של עצמו, כי x + x = 0, אז חיסור הוא אותה פעולה כמו חיבור. בלי נשא, אף פעם.

כפל כופל את הפולינומים, ואז לוקח את השארית מחילוק בפולינום קבוע ממעלה 3. כאן זה x³ + x + 1. הוא חייב להיות אי־פריק, כלומר אי אפשר לפרק אותו לפולינומים קטנים יותר מעל GF(2). הוא ממלא את התפקיד שהראשוני 7 מילא קודם.

מחשבים 3 × 7. זה (x + 1)(x² + x + 1) = x³ + x² + x + x² + x + 1. איברי x² מתבטלים בזוג, וגם איברי x, ונשאר x³ + 1. כלל השארית אומר ש־x³ + x + 1 = 0, אז x³ = x + 1 (זוכרים שחיסור הוא חיבור). ואז x³ + 1 = x + 1 + 1 = x. ו־x הוא 010, כלומר 2.

אז ב־GF(8), 3 × 7 = 2.

הטבלה כולה

אותו חישוב לכל זוג נותן את הטבלה בשרטוט. כל שורה מ־1 עד 7 היא סידור מחדש של 1 עד 7, בלי אפסים ובלי חזרות. זו תכונת השדה שאפשר לראות בעין: 1 מופיע בכל שורה, אז לכל איבר שאינו אפס יש הופכי. ההופכיים הם 1 ↔ 1, 2 ↔ 5, 3 ↔ 6 ו־4 ↔ 7.

לוגריתמים: כפל על ידי חיבור

קוראים ל־x בשם α ולוקחים את החזקות שלו: α⁰ = 1, α¹ = 2, α² = 4, α³ = 3, α⁴ = 6, α⁵ = 7, α⁶ = 5, ו־α⁷ = 1 שוב. כל איבר שאינו אפס מופיע בדיוק פעם אחת. איבר שהחזקות שלו מגיעות לכולם נקרא פרימיטיבי.

זה הופך כפל לחיבור של מעריכים, מודולו 7. בודקים שוב את 3 × 7: 3 = α³ ו־7 = α⁵, אז המכפלה היא α⁸ = α¹ = 2. אותה תשובה. מימושים אמיתיים עובדים ככה, עם טבלת לוגריתמים וטבלה הפוכה, כך שכפל של שני סימבולים עולה שתי שליפות מטבלה וחיבור אחד.

GF(256): בייט אחד לסימבול

אותה בנייה עם פולינומים של 8 ביטים ופולינום אי־פריק ממעלה 8 נותנת את GF(256). כל איבר הוא בדיוק בייט אחד. החיבור הוא עדיין XOR.

איזה פולינום, זו בחירה, ותקנים שונים בחרו אחרת. קודי QR משתמשים ב־x⁸ + x⁴ + x³ + x² + 1, שנכתב הרבה כ־0x11D. AES משתמש ב־x⁸ + x⁴ + x³ + x + 1, 0x11B. שניהם נותנים שדה של 256 איברים, אבל טבלאות הכפל שונות, אז מפענח QR ומימוש של AES לא חולקים טבלה.

ההבדל נראה בפרט קטן. עם 0x11D, x עצמו, הבייט 2, הוא פרימיטיבי: החזקות שלו עוברות על כל 255 הבייטים שאינם אפס. עם 0x11B לא. החזקות של 2 מגיעות רק ל־51 מהם, ולכן מימושים של AES שמשתמשים בטבלאות לוגריתמים בונים אותן מ־3, שהחזקות שלו מגיעות לכל ה־255. בדקתי את שניהם בהרצה של החזקות בקוד. FIPS 197, התקן של AES, נותן את {57} × {83} = {c1} כדוגמה מחושבת, ואותו קוד משחזר אותה.

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