סריגים נחקרו על ידי מתמטיקאים במשך עשורים והם שימושיים במספר סוגיות כמו תכנון ליניארי ופירוק לגורמים. העניין בסריגים עלה בשל מאפיין שימושי במיוחד לתחום הקריפטוגרפיה שהתגלה על ידי Ajtai ב-1996 קרי רדוקציה מהמקרה הגרוע למקרה הממוצע. הוא הוכיח שווריאציות מסוימות של בעיית התרמיל קשות לפתרון במקרה הממוצע לפחות כמו המקרה הגרוע של בעיות הסריג. עניין נוסף עלה בעקבות גילוי אלגוריתם LLL על ידי Lenstra, Lenstra ו-Lovasz ב-1982.
למשל פתרון בעיית SVP (הווקטור הקצר ביותר) עד קירוב פולינומי. בהנחה שלא קיים אלגוריתם פולינומי יעיל לחישוב SVP עד פקטור של formula_1 כאשר formula_2 הוא הממד של הסריג ו-formula_3 הוא קבוע בלתי תלוי, אפשר לבנות על בסיסה פונקציה חד-כיוונית קריפטוגרפית דומה לתרמיל (knapsack) שכמעט תמיד בטוח קשה אם המפתח נבחר באקראי. הצפנת סריג היא היחידה שקיימת הוכחה לגביה שהיא בטוחה כמו המקרה הגרוע אך זאת רק מנקודת ראות תאורטית, בעוד שמעשית החיסרון העיקרי של מערכת כזו הוא מפתח ההצפנה העצום.
בהשראת הרעיון של Ajtai פיתחו ב-1996 עודד גולדרייך, שי הלוי ושפי גולדווסר מערכת הצפנה מבוססת סריג (נקראת בקיצור GGH) עם יחס מקרה ממוצע/מקרה גרוע דומה, דהיינו פענוח אתגר אקראי נתון קשה לפחות כמקרה הגרוע של וריאציית SVP הנקראת uSVP (קיצור של unique SVP). הבעיה נעשית קלה ככל שפקטור הקירוב גדל, השאלה היא מהו הגורם formula_4 הקטן ביותר כך שאפשר יהיה לבנות פונקציה קריפטוגרפית הנחשבת קשה לפתרון לפחות כמו מציאת קירוב formula_4 לבעיית הסריג. Phong Nguyen פרסם והוכיח ב-1999 פגמים ב-GGH של גולדרייך, גולדווסר והלוי והציע דרכים לתיקון הבעיות שגילה. מסקנותיו הם שהאלגוריתם אינו יעיל מעשית. כדי שמערכת GGH תקרא בטוחה סדר גודל של מפתח ההצפנה צריך להיות ריבועי ביחס לפרמטר הביטחון formula_2, מעשית זה יכול להגיע לאלפי סיביות. בימינו הממצאים הטובים ביותר הם פונקציית גיבוב חסינת התנגשויות של Micciancio המבוססת על אי-קירוב בטווח formula_7 וכן הצפנת רגב המבוססת על אי קירוב של בעיית uSVP בטווח formula_8.
הבעיות שיש בהן עניין מנקודת ראות תאורטית הן בעיית הווקטור הקצר ביותר (בקיצור SVP) והכללה שלה שנקראת בעיית הווקטור הקרוב ביותר (CVP). מצד אחד הודות לאלגוריתם LLL ניתן לבצע קירוב יעיל בפתרון הבעיות האמורות עד כדי פקטור מעריכי מסדר גודל formula_9 כאשר formula_10 הוא ממד הסריג ועם אקראיות אפשר להגיע לסדר גודל של formula_11. מצד שני, עבור קבוע כלשהו formula_12 ידוע שלא קיים אלגוריתם יעיל שיכול לבצע קירוב עד כדי formula_13 אלא אם P=NP. הממצאים הללו אומתו אחר מחקרים שנעשו בתחום זה על ידי רבים.
ב-1996 הציע Jeffrey Hoffstein אלגוריתם הצפנה אסימטרי פרקטי שנקרא NTRU שיכול להגיע עם מפתח הצפנה קטן (בסדר גודל של כמה מאות סיביות) על ידי שימוש במחלקה מיוחדת של סריגים שמאפשרת ייצוג קומפקטי. האלגוריתם מבוסס על חוג פולינומי שנקרא קונבולוציה formula_14 הפונקציה היא חישוב כפל וחיבור בפולינומיים מודולו formula_15. הקשר לסריג הוא הקונבולוציה המודולרית, אפשר לראות שקיים הומומורפיזם בין הפולינומים בחוג R ומטריצה מעגלית בגודל formula_16 עם מקדמים שלמים. הוכחת בטיחות האלגוריתם אינה לפי סיבוכיות המקרה הגרוע כמו במקרה של סריגים, ולמעשה קיימות מספר חולשות באלגוריתם שמאפשרות התקפת מוצפן-נבחר בגרסה המקורית.
סריג.
סריגים בתורת המספרים שנקראים גם "הגאומטריה של המספרים" (הרמן מינקובסקי), ניתנים להגדרה בכמה דרכים. בניסוח לא רשמי סריג הוא אוסף סדור של נקודות במרחב formula_10-ממדי. בניסוח אחר, קבוצת כל הקומבינציות הליניאריות השלמות של וקטורים בלתי תלויים ליניארית מעל formula_18, כלומר אם formula_19 הם קבוצת וקטורים בלתי תלויים ליניארית אזי formula_20 ייקרא "סריג" והווקטורים formula_21 נקראים "בסיס" הסריג.
בניסוח פורמלי אם נתונים formula_22, שני וקטורים formula_23 ו-formula_24 מעל המספרים הממשיים ויהי formula_25 מכפלה אוקלידית של formula_26 עם formula_27 כך שמתקיים formula_28 וכן יהי formula_29 הנורמה האוקלידית של formula_26 כאשר formula_31. קבוצת הווקטורים formula_32 נקראת בלתי תלויה ליניארית מעל formula_33 אם ורק אם תמיד מתקיים formula_34. סריג היא תת-קבוצה formula_35 כך שמתקיים formula_36 כל עוד formula_37 וכן קיים מספר ממשי formula_38 כך ש-formula_39 ו-formula_40 ו-formula_41. לפי הגדרות אלו formula_42 הוא סריג כש-formula_43. וכן כל תת-קבוצה של סריג היא סריג. בשל הדמיון למרחב הווקטורי תורת הסריגים מקבילה בכמה מובנים לאלגברה ליניארית. בסיס הסריג אינו ייחודי, כלומר עבור סריג formula_44 מסדר formula_45 ישנם אין סוף בסיסים עם ממד זהה.
בעיית הווקטור הקצר ביותר.
Shortest Vector Problem היא בעיית הסריג המפורסמת ביותר. בהינתן סריג formula_46 המיוצג על ידי בסיס formula_47, בעיית SVP היא למצוא את הווקטור הקצר ביותר ב-formula_46 שאינו אפס. הבעיה יכולה להיות ביחס לכל נורמה המסומנת ב-formula_49 אך הנורמה האוקלידית הכי נפוצה. גרסה אחרת של הבעיה היא לחשב רק את אורכו המסומן ב-formula_50 של הווקטור הקצר ביותר מבלי בהכרח למצוא את הווקטור עצמו הבעיה מסומנת על ידי formula_51. כאשר formula_52 הבעיה ניתנת לפתרון בזמן פולינומי אולם כאשר formula_53 האלגוריתם הטוב ביותר הידוע לפתרון בעיה זו הוא בסיבוכיות של formula_54.
בעיית SVP נחקרה על ידי מתמטיקאים עשרות שנים בשל הקרבה שלה לבעיות שונות בתורת המספרים והיא משוערת כבעיית NP-קשה. המשפט הראשון של מינקובסקי הוא משפט מפתח בתורת הסריגים שאומר שאורכו המקסימלי של כל וקטור הקצר ביותר שאינו אפס בכל סריג מממד formula_10 הוא formula_56 כאשר formula_57 הוא קבוע אבסולוטי שתלוי רק בממד formula_10 ו-formula_59 הוא הדטרמיננטה של הסריג. הגבול העליון של מינקובסקי צמוד למדי אך ישנם סריגים שבהם קיים וקטור קצר הרבה יותר. מינקובסקי לא סיפק אלגוריתם שמוצא וקטור כזה. אלגוריתם שמוצא וקטור קצר ביותר בסריג דו-ממדי היה ידוע כבר לגאוס במאה ה-19 אולם למקרה הכללי לא היה פתרון (קירוב של פתרון) עד תחילת שנות השמונים של המאה הקודמת עם המצאת LLL. האלגוריתם LLL יכול לבצע קירוב עד פקטור של formula_60 כאשר formula_10 הוא ממד הסריג. אלגוריתם אחר עם פקטור קירוב טוב יותר שהוא תת-מעריכי בזמן פולינומי הוא של שנור שנקרא Block Korkine-Zolotarev. לא קיים אלגוריתם פולינומי יעיל המחשב את אורך הווקטור הקצר ביותר בסריג (שלא לדבר על מציאת וקטור כזה) והיא משוערת כבעיה NP-קשה בטווח קירוב פחות מפקטור של formula_62.
בעיית GapCVP.
בעיית ההכרעה של CVP הנקראת GapCVP היא כדלקמן: נתון סריג formula_63 עם בסיס formula_64 וקטור formula_65 ו-formula_66 הפלט צריך להיות 1 אם formula_67 או 0 אם formula_68.
בעיית ההכרעה formula_69 היא בהינתן סריג דומה להחזיר 1 אם formula_67 או 0 אם formula_71.
בעיית GapCVP היא NP-שלמה ברדוקציה מבעיית התרמיל.
סירטיר (קומיקס)
סירטיר (באנגלית: Surtur) הוא דמות בדיונית של נבל-על המופיע בחוברות הקומיקס תור ביקום מארוול קומיקס. הדמות הופיעה לראשונה בחוברת "Journey into Mystery #97" מאוקטובר 1963, ונוצרה על ידי הכותב סטן לי והמאייר ג'ק קירבי.
כמו מקבילו מהמיתולוגיה הנורדית, סירטיר הוא שד אש ממוספלהיים. הקומיקס העמיק את דמותו של סירטיר, והפך אותו לאב כל שדי האש. סירטיר הופיע בסדרות האנימציה "ספיידרמן וחבריו המדהימים", ו"האוונג'רס התאספו!". חרבו הייתה מוקד עלילת הסרט המצויר "", והוא עצמו הופיע בסרט "הענק הירוק נגד". את דמותו בסרט הלייב אקשן "" מדבב השחקן קלנסי בראון בעוד הבמאי טאיקה וואטיטי מגלם את דמותו באמצעות לכידת תנועה.
ביוגרפיה בדיונית.
כנזכר לעיל, סירטיר הוא שד אש ובעל טינה לאודין. הוא שוחרר מכלאו בידי לוקי, ונשלח יחד עם ענק הסופה סקאאג לכדור הארץ. שם הצמד נתקל באודין, תור ובלדר, ולפני שהחל הקרב, אודין פינה את תושבי כדור הארץ. לאחר שסקאאג הובס, סירטיר הולך לקוטב הצפוני כדי להמיס קרחונים ולגרום לשיטפון, אך תור באמצעות חרב אודין לוכד אותו במטאוריט. הוא וענק הקרח יימיר זומנו לכדור הארץ בידי כת בשם בני שטניש. בעזרת האביר השחור ודוקטור סטריינג', האוונג'רס הערימו על סירטיר ויימיר וגרמו להם להביס זה את זה.
סירטיר ניסה לפלוש לאסגרד במהלך שנת אודין, אך הובס ונכלא. הוא חזר עם חרב האבדון הענקית "שחר", ולאחר ששלח קבוצות שדים לתקוף את כדור הארץ הסתער על אסגרד. הוא הביס את אודין ותור, אך לוקי עיכב את סירטיר עם אשליות עד שאודין התאושש ונלחם נגדו עד שהשניים נפלו לקרע ממדי. כשאודין חוזר לאסגרד, הוא מגלה כי ספג את מהותו של סירטיר, שהשתלט עליו. סירטיר מצליח לחזור לצורתו הפיזית ותוקף עד אסגרד, עם שתור עם כוח אודין מגרש אותו לים הלילה הנצחי. סירטיר מופיע במהלך הראגנארוק, שם הסתער על אסגרד ותקף את תור. כאשר החוצן בטא ריי ביל ביקר בחורבות אסגרד, הוא ראה את גופתו המתה של סירטיר אוחזת ב"שחר".