tomron87/hebrew-wikipedia-sentences-corpus huggingface dataset:
לשם כך נגדיר משתנה מקרי נציב את ההסתברות לקבלת עץ בנוסחה לפונקציית ההסתברות של משתנה מקרי המתפלג גאומטרית ונקבל: .
כעת נוכל לחשב ביתר קלות את ההסתברות שיידרשו הטלות בכדי לקבל עץ בפעם הראשונה.
למשל ההסתברות שהמטבע ייפול על עץ בפעם הראשונה לאחר 5 הטלות היא: .
בהתפלגות אחידה רציפה נשתמש כדי לתאר ניסוי שבו כל תוצאה מתקבלת באותה ההסתברות, כאשר טווח הערכים האפשרי נתון על ידי התחום .
פונקציית ההסתברות של משתנה מקרי המתפלג בהתפלגות אחידה רציפה נתונה על פי הנוסחה הבאה:נבחין בסקלר שהתווסף אל נוסחת הפונקציה.
ייעודו הוא לוודא כי הסכום של כלל ההסתברויות שהפונקציה מפיקה הוא בתהליך המכונה נירמול.
נוכל להשתמש במשתנה מקרי בעל התפלגות רציפה בכדי לתאר את הניסוי הבא: כדור מתגלגל לאורכו של קרש ועוצר באופן אקראי בנקודה מסוימת בקטע .
נרצה לחשב את ההסתברות שעצר בנקודה .
לשם כך נציב את הפרמטרים הנתונים בניסוי בנוסחה לקבלת פונקציית ההסתברות של משתנה מקרי בעל התפלגות אחידה רציפה ואז נציב בפונקציה זו כדי לקבל את ההסתברות המבוקשת: .
ההתפלגות האקספוננציאלית מהווה מעין הרחבה של ההתפלגות הגאומטרית באופן המאפשר את הרחבת כמות הניסויים ממספר טבעי למספר ממשי.
פונקציית ההסתברות של משתנה מקרי המתפלג אקספוננציאלית נתונה על פי הנוסחה הבאה: דוגמה לשימוש במשתנה מקרי המתפלג אקספוננציאלית היא מדידת הזמן החולף בין התרחשות של אירועים נדירים לרבות מדידת זמן החיים של מכשיר חשמלי.
פונקציית גִּבּוּב קריפטוגרפית היא פונקציית גיבוב חד-כיוונית הממירה קלט באורך כלשהו לפלט קצר, באורך קבוע, הנקרא קוד גיבוב או ערך גיבוב.
ערך הגיבוב משרת כייצוג קומפקטי של הקלט או כאמצעי זיהוי ייחודי שלו, מעין טביעת אצבע דיגיטלית.
יש נוהגים לכנותו תמצית-מסר (message digest) ועיקר השימוש בו הוא להוכחת שלמות ואימות הקלט.
אם נעשה שינוי כלשהו אפילו מינורי בתוכן הקלט לפונקציה, בסבירות גבוהה מאוד הפלט יהיה שונה לגמרי ולכן ניתן יהיה להבחין בזאת בקלות.
בניגוד לפונקציית גיבוב רגילה, פונקציית גיבוב קריפטוגרפית חייבת להיות חד-כיוונית במובן שבהינתן הפלט יהיה קשה מבחינה חישובית למצוא את קלט המקור שלו ולכן יהיה קשה ביותר לגורם זדוני לזייף קלט באופן כזה שיתקבל ממנו ערך גיבוב זהה.
פונקציות גיבוב קריפטוגרפיות ממלאות תפקיד חשוב בקריפטוגרפיה מודרנית, הן מהוות חלק בלתי נפרד מפרוטוקולים קריפטוגרפיים רבים; חתימה דיגיטלית, קוד אימות מסרים, הגנה על סיסמאות, מחולל פסאודו-אקראי, אנטי-וירוס, קוד תיקון שגיאות, סכמת התחייבות ועוד.
כמו פונקציית גיבוב קונבנציונלית הנפוצה ביישומי מחשב לא קריפטוגרפיים, תפקידה העיקרי הוא למפות תחום גדול לטווח קטן, אך הן נבדלות במספר היבטים חשובים.
פונקציית גיבוב כללית מקבלת קלט באורך שרירותי ומפיקה פלט באורך קבוע.
בניסוח פורמלי עבור התחום והטווח תמיד מתקיים .
לפי עקרון שובך היונים העובדה שהפונקציה ממפה מקורות רבים לתמונות מעטות משמעה שבהכרח קיימות התנגשויות - שני קלטים שונים שהפונקציה מפיקה מהם פלט זהה.
בהנחה שפונקציית הגיבוב רנדומלית, אם הוא אורך הקלט בסיביות ו- אורך הגיבוב בסיביות הרי שבמקרה הממוצע קלטים ימופו באופן זהה.
במילים אחרות ההסתברות להתנגשות היא ללא תלות ב-.
השאלה האם קיימת פונקציה חד-כיוונית מוכחת מבחינה מתמטית, נובעת מהשאלה הפתוחה האם P=NP.
לאור זאת לא ידוע אם ניתן ליצור פונקציית גיבוב קריפטוגרפית חד-כיוונית 'אמיתית'.
עם זאת, קיימות פונקציות הנחשבות כחד-כיווניות לכל צורך מעשי שביטחונן מתואר במונחים של כח המחשוב הדרוש כדי להפוך אותן.
מסיבה זו ככל שכח המחשוב עולה, נדרש להחליפן מעת לעת בפונקציות חזקות יותר.
פונקציית גיבוב תקרא קריפטוגרפית אם היא מקיימת שלוש תכונות בסיסיות (לפחות את שתי הראשונות), מהקל אל הכבד:
קושי בהיפוך (preimage resistance); בהינתן פלט מסוים, מציאת הקלט המקורי שלו, קשה מבחינה חישובית.
או בניסוח פורמלי, בהינתן פונקציית גיבוב קריפטוגרפית וערך גיבוב , מציאת ערך שעבורו , היא משימה קשה.
קושי במציאת מקור נוסף (2nd-preimage resistance); בהינתן קלט כלשהו יהיה קשה חישובית למצוא קלט אחר המוביל לאותו פלט, או בניסוח פורמלי, בהינתן , מציאת שעבורו כך שיתקיים , היא משימה קשה.
קושי במציאת התנגשויות (collision resistance); מציאת שני קלטים שונים כלשהם המפיקים פלט זהה קשה מבחינה חישובית.
בניסוח פורמלי מציאת מקורות עבורם ומתקיים היא משימה קשה.
בניגוד לתכונה הקודמת שני הקלטים חופשיים ויכולים להיות כל אחד מהמקורות שישנם בתחום ההגדרה של פונקציית הגיבוב.
מלבד זאת, פונקציית גיבוב קריפטוגרפית מקיימת את התכונות הבסיסיות של פונקציית גיבוב בכלל.
פונקציית גיבוב אמורה להפיק פלט שהוא קטן יותר מהקלט וכן זמן ביצועה צריך להיות יעיל במונחי מחשוב.
פונקציה חד-כיוונית העמידה בפני התנגשויות (הגדרה 3) היא החזקה ביותר והיא אינה הכרחית בכל המקרים.
המודל המקובל להגדרת קושי מבחינה חישובית הוא במונחים של סיבוכיות זמן.
כלומר פונקציית גיבוב נחשבת לחזקה מספיק (לכל צורך מעשי) אם זמן הריצה של האלגוריתם הטוב ביותר שידוע למציאת מקור x לתמונה z (הפיכת הפונקציה ) הוא מסדר גודל של (מספר תתי-הקבוצות שישנן ב- ).
להבדיל, זמן הריצה של אלגוריתם למציאת התנגשויות עשוי להיות קצר באופן משמעותי, במקרה גרוע במיוחד עבור המצפין, רק .
זאת בגלל התקפת יום הולדת שמבוססת על פרדוקס יום ההולדת.
פרדוקס יום ההולדת טוען שהסיכויים שיימצאו בחדר אחד שניים מתוך 23 אנשים שלהם יום הולדת זהה, הם בערך 0.507 (מעל 50 אחוז), שזוהי באופן מפתיע תוצאה גבוהה מהאינטואיציה הראשונית (ולכן תוצאה זו בתורת ההסתברות נקראת 'פרדוקס').
היות שלא מדובר על יום הולדת ספציפי אלא כל זוג תואם, מספר הזוגות האפשריים בקבוצה כזו הוא רק .
במילים אחרות כדי שההסתברות ששני משתנים מקריים יהיו זהים מעל מרחב הסתברות בהתפלגות אחידה בהסתברות גבוהה מחצי נדרשים לפחות מאורעות.
במקרה של יום הולדת השורש הריבועי של 365 הוא בערך 19.10 ולכן צריכים להיות לפחות 23 אנשים, אך בכל הקשור לימי הולדת נתון זה אינו מדויק כיוון שהתפלגות הלידות אינה אחידה (למשל באוקטובר נולדים כ-5% יותר תינוקות בממוצע מאשר בחודשים האחרים בשנה).
העובדה שמבחינה סטטיסטית היתכנות של התנגשויות גבוהה יחסית ניתנת לניצול לשבירת פונקציית גיבוב (או כל פונקציה חד-כיוונית).
הרעיון הוא שהמתקיף שמקבל לידיו קלט מסוים נניח אותו הוא מעוניין לזייף ואת ערך הגיבוב שלו נניח המשמש כהוכחה למקוריותו.
הוא מכין תחילה וריאציות של וכן וריאציות של הקלט המזויף אותו הוא מעוניין להחליף איתו.
את כל הערכים הוא מגבב ומאחסן בטבלה ממוינת.
לאחר מכן הוא מחפש בטבלה שני קלטים האחד מקורי והשני מזויף שלהם ערך גיבוב זהה.
במידה שנמצא זוג תואם כזה נניח הוא יכול לשייך את ערך הגיבוב של לקלט ולטעון שהוא מקורי היות שמתקיים .
ההבדלים בין הקלטים יכולים להיות כל הבדל קל שאינו משנה את משמעות התוכן כמו רווחים כפולים, שורות ריקות וכדומה.
מבחינה הסתברותית מספר ההתנגשויות הצפוי הוא והסיכוי למצוא התנגשות אחת הוא בסדר גודל שהוא בערך 63% עם זיכרון בסדר גודל של כאשר .
יש להביא בחשבון גם את מיון הערכים שהוא בסיבוכיות של וכן החיפוש שהוא בסיבוכיות אך פעולות אילו אינן משמעותיות ואפשר להתעלם מהן.
את ההתקפה פיתח גידעון יובל ב-1979.
יתרה מזו, אפשר לצמצם את דרישות הזיכרון באופן משמעותי אם ממירים את בעיית חיפוש ההתנגשויות לבעיה אחרת מאוד דומה שנקראת בעיית מציאת מחזוריות של פונקציה אקראית.
אם נתונה פונקציה אקראית , קיימים אלגוריתמים מהירים למציאת שני ערכים כך שמתקיים כאשר וזאת ללא צורך בזיכרון כלל.
בנוסף אפשר ליישם את אלגוריתם החיפוש באופן מקבילי.
לדוגמה בטכנולוגיה של 1994 אפשר היה לבנות בעלות של 10 מיליון דולר, חומרה ייעודית למציאת התנגשויות בפונקציית הגיבוב MD5 כאשר בתוך 21 יום.
בשנת 2004 במחיר נמוך מזה אפשר היה למצוא התנגשויות בתוך 4 שעות.
להתקפה זו השלכה מהותית על ביטחון כל פונקציית גיבוב.
אם פונקציית גיבוב מפיקה פלט של סיביות, בהנחה שלא קיימת נגדה התקפה טובה מכוח גס אז אומרים שביטחונה המרבי הוא בפקטור של כמחצית ללא תלות באיכותה.
למשל ב-SHA-1 פלט הפונקציה המינימלי הוא 160 סיביות ועל כן מציאת התנגשות בכוח גס היא בסיבוכיות של .
נכון לשנת 2015 מקובל להשתמש בערכי גיבוב באורך של לפחות 256 סיביות כדי לקבל ביטחון ברמה של שהוא המינימום הנדרש כיום.
ליתר דיוק מספיק שהזיכרון הפנימי של האלגוריתם יהיה גדול כדי לסכל התקפה זו ואילו ערך הגיבוב המתקבל ממנו ניתן ל"קיטום" לגודל הרצוי.
הוכח שאם פונקציית הגיבוב בטוחה, הרי שאפשר ליטול רק חלק מתוצאת הגיבוב מבלי להסתכן בירידה בביטחון כל עוד אורך הגיבוב שמשתמשים בו מספיק גדול כדי למנוע ניחוש בכוח גס, למעשה זו השיטה הרווחת כיום.
השימוש העיקרי בפונקציית גיבוב הוא הבטחת שלמות של פיסת מידע דיגיטלי כמו קובץ, הודעת דואר, מפתח הצפנה או מסר כלשהו.
תחילה מפיקים מהמסמך תמצית קצרה אותה שולחים יחד עם המסמך או מאחסנים במקום שמור.
בנקודת זמן כלשהי, אם מעוניינים לוודא את שלמות המסמך מחשבים את פונקציית הגיבוב מתוכן המסמך הנוכחי ומשווים את התוצאה מול התמצית השמורה, אם ישנו הבדל משמע שבוצע שינוי.
פונקציית הגיבוב מבטיחה מעצם הגדרתה שניסיון לבצע שינוי זדוני במסמך מבלי שהמשתמשים הלגיטימיים יבחינו בו יתגלה מיד היות שתמצית המסמך השמורה לא תתאים למסמך לאחר השינוי.
אלא אם כן המתקיף מסוגל לשנות גם את התמצית.
היות שהתמצית בדרך כלל מאומתת בדרך כלשהי לא סביר שהוא יצליח.
פונקציית גיבוב בדרך כלל מהירה מאוד לכן מסיבות של יעילות כאשר רוצים לחתום חתימה דיגיטלית על מסמך גדול, עדיף תחילה להכין מהמסמך תמצית ולחתום עליה במקום לחתום על המסמך כולו.
היות שיש התאמה חד-ערכית בין המסמך לתמצית שלו אם החתימה על התמצית נמצאת תקפה, הרי שעובדה זו מבטיחה שהמסמך עצמו אותנטי.
בנוסף פונקציית גיבוב יכולה לשמש כבסיס לחתימה דיגיטלית חד-פעמית.
הרעיון לחתימה דיגיטלית חד-פעמית מבוססת פונקציית גיבוב עלה כבר ב-1979 והסיבה שהיא אינה בשימוש נרחב כיום נובע בעיקר בגלל מפתחות חתימה ואימות גדולים מדי.
לאורך השנים נעשו מאמצים להקטין את המפתחות, ביניהם הרעיון של שימוש בעץ גיבוב או בטביעת אצבע ציבורית.
שיטה ותיקה לניהול סיסמאות נעשית באמצעות פונקציית גיבוב.
סיסמאות לא נשמרות במצב גלוי מחשש לפריצה למערכת וגנבתן.
לא מקובל להשתמש בפונקציית הצפנה כדי להגן על סודיות הסיסמאות מפני שלוש סיבות.
אין צורך בפענוח כלל כי אפשר להשאיר את הסיסמאות במצב מוצפן.
בכל ניסיון אימות השרת יכול להצפין את הסיסמה שהוקלדה על ידי המשתמש ולהשוות את התוצאה עם הסיסמה המוצפנת השמורה במערכת.
מסיבה זו פונקציית גיבוב מועדפת כי אינה זקוקה למפתח הצפנה כלל.
יש עניין של מגבלות חוקיות על הצפנה חזקה במדינות מסוימות כמו ישראל לכן כל דרך שנמנעת מהצפנה עדיפה.
פונקציית גיבוב מהירה, פשוטה ויעילה יותר מפונקציית הצפנה.
לכן מקובל שהשרת מאחסן רק את קוד הגיבוב של הסיסמאות וכאשר משתמש מעוניין להתחבר הוא מתבקש להקליד סיסמה, השרת מחשב את פונקציית הגיבוב של הסיסמה שהקליד ובודק האם הערך שהתקבל תואם לזה השמור במערכת, אם כן השרת מאשר את ההתחברות.
אמנם זו שיטה יעילה ומקובלת בעולם כיום אך היא אינה מספקת הגנה הרמטית.
למעשה אינה מונעת לחלוטין התקפת כוח גס על קובץ הסיסמאות כולו, גם אם הסיסמאות אינן שמורות במצב קריא.
המתקיף יכול לגנוב את קובץ הסיסמאות המוצפנות, לנחש סיסמאות כלשהן, לבצע גיבוב שלהן ולבדוק האם התוצאה מופיעה בקובץ, גם אם לא של משתמש ספציפי.
היות שהתקפה כזו יכולה להתבצע בצורה לא מקוונת, למתקיף יש זמן בשפע.
דרך יותר בטוחה מאימות באמצעות סיסמה המציעה מה שקרוי "אימות חזק" היא סיסמה חד-פעמית.
הרעיון הוצע לראשונה על ידי לזלי למפורט והוא שימוש בפונקציית גיבוב לצורך אימות זהויות ברשת לא בטוחה מבלי להשתמש בסיסמה קבועה.
דוגמה למערכת כזו היא S/KEY.
אפשר להכין סכמת התחייבות מפונקציית גיבוב, הרעיון הבסיסי פועל כדלהלן: אם אליס רוצה להוכיח לבוב ידיעת סוד מסוים אך אינה רוצה לחשוף אותו בפניו (כעת), היא יכולה להכין תמצית גיבוב מהסוד ולשלוח אותה לבוב כהתחייבות.
בבוא העת כאשר הסוד נחשף בוב יכול לייצר ערך גיבוב חדש של הסוד ולהשוותו מול זה שאליס שלחה קודם.
בדרך זו בוב יכול להבטיח שאליס לא שינתה את הסוד ולמעשה הסוד שנחשף הוא הסוד שהיא התחייבה על ידיעתו קודם לכן.
לסכמות התחייבות שימושים במכרז והצבעה דיגיטליים.
פונקציית גיבוב קריפטוגרפית יכולה לשמש כבסיס למחולל פסאודו-אקראי.
טכניקה זו מנוצלת בהרבה פרוטוקולים.
במחולל פסאודו אקראי קריפטוגרפי מקובל לא להשתמש ישירות בערכים אקראיים שנאספו ממקורות שונים (כגון מחולל אקראי פיזי, פונקציה קריפטוגרפית או נתוני מערכת אקראיים חסרי חשיבות) זאת בגלל שההתפלגות הסטטיסטית שלהם עלולה להיות נמוכה, אלא תחת זאת מעבירים אותם בפונקציית גיבוב ותוצאת הגיבוב היא פלט המחולל הסופי (דוגמאות; האלגוריתמים Yarrow ו-TrueRand).
פונקציית גיבוב קריפטוגרפית טובה לגזירת מפתחות הצפנה רבים מתוך מפתח מאסטר יחיד.
כל אימת שזקוקים למפתח חדש מבצעים גיבוב של המפתח הקודם ולוקחים חלק מהתוצאה לפי הצורך כמפתח חדש.
בגלל החד-כיווניות של פונקציית הגיבוב, יהיה קשה למתקיף לנסות לנחש את המפתחות שהופקו.
אך אם עלה בידו לנחש את מפתח המאסטר יהיה קל לו לנחש את כל המפתחות כי הוא פשוט יכול להריץ את פונקציית הגיבוב בעצמו.
פונקציות גיבוב קריפטוגרפיות מתחלקות לשתי משפחות עיקריות:
פונקציית גיבוב ללא מפתח; נקראת גם modification detection code בקיצור MDC.
תפקידה להוות ייצוג תמציתי של המסר כך שיהיה אפשר לחשוף כל שינוי אפילו קל ביותר בסבירות גבוהה.
דוגמאות שימוש; הגנה על סיסמאות וחתימה דיגיטלית.
בסיסמאות למשל הן אינן נשמרות במצב גלוי אלא רק ערך הגיבוב שלהן נשמר ובחתימה דיגיטלית מסיבות של יעילות, החתימה מתבצעת על תמצית מהמסר במקום על המסר עצמו.
פונקציית גיבוב ללא מפתח מוגדרת באופן כללי כך:
הכוכבית מציינת שאורך המידע אינו קבוע ו- הוא אורך התג בסיביות (למשל 160 סיביות ב-SHA-1 או 256 סיביות ב-SHA-2).
פונקציית גיבוב עם מפתח; נקראת גם message authentication code בקיצור MAC ומשמשת בעיקר לאימות מסרים.
היא מוגדרת באופן כללי כך:
הוא אורך המפתח בסיביות ויכול להיות בכל אורך שרירותי שמתאים לגודל הבלוק שפונקציית הגיבוב מקבלת.
אפשר להפוך כל פונקציית גיבוב לפונקציית MAC עם מפתח.
דרך אחת נקראת HMAC והיא שילוב בטוח של המפתח הסודי עם המסר וערכים קבועים נוספים, על ידי XOR.
מבנה טיפוסי של פונקציית גיבוב קריפטוגרפית מורכב משלושה שלבים עיקריים; שלב הכנה, הליבה שנקראת 'פונקציית תמצות' ושלב סיום אופציונלי.
היות שבדרך כלל המסר גדול במידה נכרת מהקלט אותו מקבלת פונקציית התמצות הפנימית יש צורך ליישם שיטה כלשהי לחלוקה לבלוקים בגודל קבוע וריפוד הבלוק האחרון כאשר אורך המסר אינו מתחלק היטב.
השיטה הנפוצה שנקראת MD strengthening הומצאה על ידי רונלד ריבסט והיא מיישמת את מבנה מרקל ודמגרד.
בשיטה זו מחלקים את הקלט לבלוקים בגודל קבוע מוסיפים '1' בסוף המסר ומרפדים באפסים ואז מוסיפים בלוק אחד המייצג את גודל המסר בסיביות ומבצעים את פעולת הפונקציה על כל הבלוקים בזה אחר זה.
מרקל ודמגרד הוכיחו שאם נתונה פונקציית כיווץ (compression function) חסינת התנגשויות (בקיצור CRHF) למשל פונקציה מהצורה כאשר , אפשר להכין ממנה פונקציית גיבוב בטוחה לגיבוב מסר בכל אורך רצוי, שגם היא חסינת התנגשויות.
כלומר ביטחון המבנה האמור אינו חלש מביטחונה של הפונקציה הפנימית עצמה.
כמתואר בתרשים השיטה באופן כללי פועלת כדלהלן:
הקלט מחולק ל- בלוקים בגודל סיביות, .
אם (אורך בסיביות) אינו מתחלק ב- בשלמותו מוסיפים '1' בבלוק לאחר המידע ומשלימים באפסים.
תוספת זו מכונה MD strengthening והיא הוכנסה לראשונה באלגוריתם MD4 של רונלד ריבסט.
מוסיפים בלוק שמכיל ייצוג של אורך המסר בסיביות.
מכינים וקטור אתחול בגודל סיביות, נקרא בקיצור ומציבים בבלוק .
מבצעים איטרציה של הפונקציה הפנימית; עבור כל הבלוקים כאשר מבצעים .
בכל סבב מפיקה ערך ביניים שנקרא chaining value שהוא תוצאת החישוב על הבלוק הנוכחי בשילוב עם פלט הבלוק הקודם .
מבנה הפונקציה הפנימית ואופן שילוב הערכים משתנה בהתאם לשיטה עליה בנוי האלגוריתם (כמתואר תרשים).
בגמר כל הסבבים הפלט הוא .
לסיום טרנספומציה אופציונלית ממירה את הפלט האחרון לתוצאה הסופית .
פונקציית התמצות שנקראת גם פונקציית כיווץ (compression function) היא הליבה של פונקציית הגיבוב.
אפשר להכין פונקציית תמצות חד-כיוונית וחסינת התנגשויות בשלושה אופנים עיקריים;
פונקציית תמצות מבוססת צופן בלוקים; קיימים שלושה מודלים בטוחים לבניית פונקציית תמצות על בסיס צופן בלוקים (כמתואר בתרשים).
לפי מודל מטיאס-מאייר-אוסאס (האיור השמאלי בתרשים) הפונקציה היא .
לפי מודל דויס-מאייר הפונקציה היא .
לפי מודל מיאגוצ'י-פרניל הפונקציה היא .
באופן כללי הסתמכות על צופן בלוקים לבניית פונקציית גיבוב איטית יחסית ואינה נפוצה בשימוש.
פונקציית תמצות ייעודית; זוהי פונקציה חד כיוונית חסינת התנגשויות (CRHF) שמבצעת סדרה של פעולות אריתמטיות בסיסיות תוך מתן דגש על ביצוע יעיל וקל ליישום במחשב הן בתוכנה והן בחומרה.
קיימים מספר אלגוריתמים פופולריים שמסתמכים על פונקציית תמצות ייעודית.
ביניהם אפשר למנות את משפחת תמצית המסרים של רונלד ריבסט, MD4 ו-MD5 וכן משפחת SHA בה כלולים שלושה אלגוריתמים SHA-2, SHA-1 ו-SHA-3 וכן RIPE-MD.
שני האחרונים במשפחת SHA מומלצים כתקן גיבוב רשמי של ממשלת ארצות הברית המנוהל על ידי NIST.
פונקציית גיבוב מבוססת אריתמטיקה מודולרית.
פונקציה חד כיוונית שמסתמכת על בעיה מתורת המספרים שמאמינים שהיא קשה.
סכמות מסוג זה בדרך כלל איטיות מאוד ומגיעות לתפוקה של בערך סיביות פר העלאה בחזקה מודולרית אחת.
נקרא המודולוס והוא בדרך כלל בסגנון RSA - כפולה של שני מספרים ראשוניים סודיים .
יש לציין שבמקרה של פונקציית גיבוב בעלת מבנה אלגברי כמו זו מכילה חולשה מובנית, קל להחדיר דלת אחורית לפרמטרים של הסכמה כדי לגרום להתנגשויות.
מלבד זאת חלק מהפרמטרים אמורים להיות נסתרים מהעין, למשל הגורמים הראשוניים של , ואסור לאף צד לראותם.
לכן יש צורך לנקוט משנה זהירות בבחירת הפרמטרים.
דרך אחת היא להיעזר בצד שלישי מהימן, ודרך אחרת היא שימוש בסכמת שיתוף בטוחה.
פונקציית גיבוב מבוססת אריתמטיקה מודולרית
איוון דמגרד הציע סכמה כזו המבוססת על צופן אל-גמאל וגיבסון ובלייר הציעו מבנים דומים המבוססים על בעיית לוגריתם דיסקרטי שפועלים מעל חבורה מסדר ראשוני .
הרעיון הוא להכפיל את הבלוקים של המסר עם אלמנטים אקראיים מתוך .
ערך הגיבוב יהיה תוצאה של:
כאשר הוא הבלוק של המסר לאחר שרופד ב-'1' כדי למנוע מצב שהבלוק יהיה כולו מאופס.
בכל אופן מרבית הסכמות המבוססות על אריתמטיקה מודולרית כמו זו הן סכמות שפותחו בשיטות אד הוק, לא הוכחו כבטוחות וחלקן הגדול אף נפרצו בקלות.
במיוחד ראוי לציון תקן איזו 4–10118 (MASH) שנפרץ פעם אחר פעם באופן מביך, לאחר שתוקן ובכל פעם התגלו בו שוב חולשות.
המבנה הכללי הטוב ביותר היודע הוא מהצורה:
כאשר הוא ערך הביניים ו- הם הבלוקים של המסר עם יתירות מוספת.
חשוב מאוד להוסיף יתירות מכוונת למסר לפני הגיבוב כדי למנוע את 'התקפת בלוק מתקן' (להלן).
הגרסה העדכנית של תקן איזו 4–10118 נכון לשנת 1998 (ISO/IEC 10118-4) נקראת MASH קיצור של modular arithmetic secure hash והיא מופיעה בשתי גרסאות MASH-1 ו-MASH-2. פונקציית התמצות הפנימית של MASH היא מהצורה:
כאן הוא קבוע (בבסיס הקסדצימלי) וכן את הבלוקים בגודל סיביות מכינים על ידי שמחלקים תחילה את המסר לבלוקים בגודל סיביות ומרחיבים כל בלוק על ידי הוספת יתירות, מחלקים את המידע לחצאי בתים ומציבים '1111' בארבע הסיביות המשמעותיות הנותרות של כל בית.
הסימן מייצג OR, הסימן מייצג XOR והסימן אומר שתוצאת ההעלאה בריבוע נחתכת בכל סבב ל- סיביות האחרונות.
בנוסף התקן מגדיר פונקציה מסיימת מסובכת שנועדה למחוק כל זכר של המבנה האלגברי של הפונקציה.
התוצאה האחרונה של פונקציית התמצות מחולקת ל-4 תת-בלוקים, איתם מחשבים ברקורסיה עוד שנים-עשר בלוקים בגודל סיביות , מאחדים את כל 16 הבלוקים שנוצרו לשמונה בלוקים בני סיביות , מרחיבים אותם לפי השיטה האמורה לעיל ומבצעים עוד שמונה סבבים של פונקציית התמצות על הבלוקים האחרונים.
ולסיום התוצאה הסופית היא מחרוזת סיביות בגודל המחושבת על ידי .
ההתקפה הטובה ביותר הידועה כנגד מבנה זה היא בסיבוכיות של שהיא לא יותר טובה מכוח גס.
MASH-2 היא גרסה שונה במעט שבה ההעלאה בריבוע מוחלפת ב-.
התקפת בלוק מתקן (correcting block) היא התקפה המנצלת את המבנה האלגברי של פונקציית התמצות הפנימית.
ההתקפה מתמקדת בחיפוש התנגשויות או מקור נוסף על ידי החלפת בלוק אחד או יותר בסוף, באמצע או בהתחלה של המסר.
ההתקפה מתבצעת על ידי חישוב כאשר הוא הבלוק המתקן.
מבנה אלגברי פגיע במיוחד להתקפה זו משום שאפשר להפוך לפעמים את פונקציית התמצות הפנימית בעזרת מניפולציה אלגברית.
דרך נפוצה להתמודד עם התקפה זו היא להוסיף יתירות מכוונת למסר לפני הגיבוב כך שיהיה קשה למצוא בלוק מתקן עם היתירות הדרושה.
המחיר כמובן הוא ירידה בביצועים.
לדוגמה ב-1984 הציעו דייוויס ופרייס פונקציית גיבוב עם פונקציית תמצות כדלהלן: .
היתירות שהם הוסיפו הייתה 64 אפסים שנוספו לכל בלוק לפנים או בסוף.
גיראולט ואחרים הראו כיצד אפשר לתקוף פונקציה כזו ולמצוא מקור נוסף.
CCITT X.509 הייתה פונקציית גיבוב שפותחה ב-1988 וניסתה למנוע את ההתקפה המתוארת על ידי הוספת היתירות באופן כזה שכל ניבל (חצי בית) בכל הבתים של המסר יכיל ארבעה אפסים.
למרות זאת הראה קופרשמידט שאפשר למצוא התנגשויות במבנה זה באמצעות ההתקפה האמורה.
פונקציית ספוג היא כלי קריפטוגרפי ורסטילי שיכול בין היתר לשמש כבסיס להכנת פונקציית גיבוב על ידי מה שקרוי "מבנה ספוג".
מבנה ספוג הוא מצב הפעלה של פרמוטציה קבועה, עם כלל ריפוד מתאים, שמקבל כקלט מחרוזת בינארית בכל אורך, מכיל זיכרון פנימי רחב ומפיק פלט כאשר מוגדר על ידי המשתמש.
מבנה ספוג הוא הכללה של פונקציית גיבוב באופן שמאפשר קלט קבוע כמו בצופן זרם או פלט קבוע כמו באימות מסרים.
הוא מכיל זיכרון, דהיינו הפונקציה הפנימית מופעלת באופן איטרטיבי על המצב הפנימי בשילוב עם הקלט.
את ביטחון האלגוריתם מבטאים במונחים של גודל הזיכרון הפנימי.
בפונקציית ספוג נעשה שימוש בפועל בכמה אלגוריתמים חדשים, ביניהם SHA-3.
פונקציית גיבוב אקראית היא פונקציית גיבוב המשלבת בנוסף לקלט הרגיל גיוון אקראי הנקרא מלח (salt).
מהיבט תאורטי המטרה של המלח היא לאפשר הסתמכות על פונקציית גיבוב בעלת ביטחון חלש כמו MD5 ו-SHA-1 שבעקבות קרפיטואנליזה חדשה שמצביעה על בעיות בעמידות מפני התנגשויות מומחים המליצו שלא להשתמש בהן.
הרעיון הוצע ב-2007 על ידי שי הלוי והוגו קרווציק לחיזוק אלגוריתם חתימה דיגיטלית DSA, המשלב בין היתר פונקציית גיבוב.
פונקציית גיבוב אוניברסלית או בשמה האחר TCR קיצור של Target Collision Resistance היא פונקציית גיבוב אקראית שאינה עמידה מפני התנגשויות באופן מלא.
פונקציה זו פותחה בהשראת נאור ויונג שהציעו לראשונה את פונקציית הגיבוב האוניברסלית בקיצור UOWHF ששמה שונה לאחר מכן על ידי בלייר ורוגווי ל-TCR.
בניסוח רשמי, פונקציית גיבוב אוניברסלית היא בעצם משפחה של פונקציות עבור קבוצה כלשהי .
היא תקרא אוניברסלית או TCR אם לא קיים אלגוריתם יעיל שאיתו אפשר לנצח במשחק הבא למעט בהסתברות זניחה.
בוחר קלט כלשהו ומקבל ערך אקראי והוא צריך למצוא קלט אחר כך שמתקיים .
כאשר היא פונקציית גיבוב כמו MD5 והערך הוא מעין מפתח ונקרא גם "מלח".
למתקיף אין שליטה על ערך זה, הוא חייב לקבל אותו עבור כל מסר שהוא מנסה לגבב.
בדרך זו אפשר להפוך כל פונקציית גיבוב דטרמיניסטית ל-TCR.
המלח יכול להיות ערך קצר כלשהו אך חייב להיות חד-פעמי עבור כל מסר נתון.
מבנה זה נחשב יעיל ומבטיח קושי רב יותר במציאת התנגשויות כלומר למצוא המקיים מאשר במודל הסטנדרטי של פונקציות גיבוב.
כאן התקפת יום הולדת אינה ישימה כיוון שהיא לא יכולה להיות אוף ליין, כלומר התוקף חייב לקבל בנוסף לתמצית הקלט את שמיוצר באופן אקראי עבור כל מסר, לכן אפשר להסתפק בכל פונקציית גיבוב במבנה מרקל דמגרד שהיא בעלת עמידות מפני מציאת מקור נוסף ואינה חסינת התנגשויות (הגדרה 3 לעיל).
הגדרה פורמלית של פונקציית גיבוב TCR היא:
פשוט הקלט לפונקציית הגיבוב מחובר עם מחרוזת המלח הקצרה בלוק אחר בלוק ב-XOR לפני שמפעילים את פונקציית הגיבוב.
בגלל השימוש במלח האקראי לא תמיד הפונקציה ניתנת לשימוש כחלק ממנגנון חתימה דיגיטלית כי יש צורך לחתום גם על המלח ושלוח אותו יחד עם המסר לצד המקבל, מה שמחייב שינויים משמעותיים בקוד המקור של המערכות הקיימות.
אפשר לפתור את הבעיה על ידי הכללת כחלק מהמסר כך:
כאן בנוסף לחיבור מחרוזת המלח הקצרה עם כל הבלוקים של הקלט, משרשרים את מחרוזת המלח עצמה בראש הקלט ואת הכול ביחד מגבבים עם פונקציית הגיבוב כרגיל.
גרסה זו נקראת eTCR והיא מציעה ביטחון רב יותר, יתרונה הוא שאין צורך לחתום על המלח בנפרד וניתן להכניס את השינוי במערכות הקיימות ללא שינויים מרחיקי לכת בקוד המערכת.
תקן פונקציית גיבוב בטוחה (SHA)
במטרה ליצור תקן בין-לאומי אחיד של פונקציות גיבוב קריפטוגרפיות פרסם המכון הלאומי לתקנים וטכנולוגיה האמריקאי את תקן SHA קיצור של secure hash algorithm.
בשנת 1993 פורסמה הראשונה מבין הפונקציות במשפחה שנקראה SHA-0 (האפס נוסף מאוחר יותר כדי להבדילה מהגרסאות המתקדמות).
הפונקציה הוחלפה ב-1995 בגרסה המחוזקת SHA-1, עקב חולשות שנתגלו בה.
SHA-1 דמתה ל-SHA-0 בשינויים קלים.
שתי הפונקציות מבוססות על אלגוריתם תמצית מסרים של רונלד ריבסט MD5, פועלות בשיטת מרקל-דמגרד ומפיקות פלט באורך 160 סיביות.
ב-2002 פרסם NIST את משפחת הפונקציות SHA-2, המפיקות ארבעה פלטים אפשריים 224, 256, 384 ו-512 סיביות.
משפחת SHA היא סדרת פונקציות גיבוב ייעודיות המבוססות על הידע שנצבר בעקבות סדרת האלגוריתמים MD (תמצית מסרים).
פונקציות אלו נבנו תוך שימת דגש על פיזור אחיד של כל סיביות המסר באופן כזה שלכל חלקי המסר תהיה השפעה על הפלט.
הפונקציות משתמשות בפעולות פשוטות כמו XOR, Shift ו-Rotate הבנויות כסדרה של פונקציות לוגיות המקבלות שלושה ערכים ומפיקות ערך אחד בגודל קבוע.
כאשר ב-SHA1 וכן SHA256 הערכים בגודל מילה (32 סיביות) ואילו ב-SHA384 ו-SHA512 הערכים בגודל מילה כפולה (64 סיביות).
ההבדל העיקרי בין הפונקציות השונות במשפחה הוא בכמות סיביות הפלט וערכי האתחול הקבועים.
בנובמבר 2007 הושקה תחרות פתוחה לתקן SHA החדש, בדומה לתחרות שהתקיימה לצפני בלוקים שבה זכה AES.
באוקטובר 2012 נסגרה התחרות והוכרז Keccak האלגוריתם הזוכה בתחרות, זה שיחליף בהדרגה את קודמו לתפקיד ונקרא SHA-3. בארגון התקינה ממליצים שלא להשתמש יותר ב-SHA-1 וממליצים לעבור ל-SHA-2 או SHA-3. בארגון התקינה רואים בתקן SHA-2 עדיין בטוח לשימוש נכון לשנת 2013 ולא מתוכנן להחליפו בזמן הקרוב.
העובדה ש-SHA-3 שונה מאוד בעיצובו ואופן פעולתו מתקן SHA-2 רק מרחיב את האפשרויות כיוון שלא סביר שתמצא התקפה אחת שתהיה יעילה כנגד שניהם.
Keccak הזוכה בתחרות SHA-3 הוא אלגוריתם גיבוב יעיל ובטוח, שפותח על ידי קריפטוגרפים בלגיים ואיטלקיים.
הוא מצטיין בגמישות רבה, שולי ביטחון גבוהים, ביצועים כלליים טובים ומימוש יעיל בחומרה.
באלגוריתם זה הוכנס לראשונה מבנה הספוג הנחשב למבנה יעיל ובטוח.
להלן רשימה חלקית של פונקציות גיבוב פופולריות, חלקן חדשות, חלקן היו בשימוש נרחב בעשור האחרון וחלקן לא בטוחות לאחר שהתגלו בהן חולשות והן מובאות כאן רק למען התיעוד.
ב-2004 בתוך ארבעה חודשים נמצאו התנגשויות בגרסה מלאה של MD5 בפרויקט שנקרא MD5CRK.
ב-2005 ארג'ן לנסטרה הראה שאפשר לזייף סרטיפיקט X.509 בגרסה שעושה שימוש ב-MD5 באמצעות חיפוש התנגשויות בפונקציית הגיבוב, בתוך מספר שעות.
ב-2010 דווחה התקפה נוספת, היעילה ביותר עד כה כנגד MD5 שפרטיה לא פורסמו אלא הוצעה כאתגר בסך 10,000 דולר למי שיצליח למצוא התנגשות עם 64 בתים עד ינואר 2013. ייתכן שהאלגוריתם נמצא עדיין בשימוש מוגבל והוא למעשה מוחלף כעת בהדרגה על ידי ארגוני התקינה הבינלאומיים באלגוריתם בטוח יותר.
שלושת האלגוריתמים הראשונים HAVAL, GOST, MD5 וכן RIPEMD-128 לא מומלצים לשימוש כיום, והם מופיעים לצורך התיעוד בלבד.
כמו כן ארגוני התקינה המליצו לעבור ל-SHA-2 ולא להשתמש יותר ב-SHA-1.
פונקציית גמא הלא שלמה מוגדרת על ידי אינטגרל בעל אותו אינטגרנד כמו פונקציית גמא, אך עם גבולות אינטגרציה שונים.
ישנם שתי פונקציות המכונות פונקציית גמא הלא שלמה: עליונה ותחתונה.
פונקציית גמא הלא שלמה העליונה מוגדרת:
פונקציית גמא הלא שלמה התחתונה מוגדרת:
מאפיינים של פונקציית גמא הלא שלמה
על ידי אינטגרציה בחלקים אפשר להגיע למסקנה:
הגדרת מקרה מיוחד של פונקציית "G" של ("Meijer G") מאייר:
פונקציית ההישרדות, נקראת גם פונקציית אמינות , היא פונקציה המוגדרת מעל משתנה מקרי מסוג זמן-לאירוע (time-to-event), המייצג לרוב את הזמן הנמדד עד לתמותה או לכישלון מערכת מסוימת.
הפונקציה מקבלת זמן ומחזירה את ההסתברות שהמערכת תשרוד מעבר לזמן זה.
יהי משתנה מקרי רציף המייצג זמן-לאירוע, עם פונקציית התפלגות מצטברת ופונקציית צפיפות על ציר הזמן החיובי .
פונקציית ההישרדות של מוגדרת כ:
כל פונקציית הישרדות היא פונקציה מונוטונית יורדת במובן הרחב.
הזמן מייצג התחלה, בדרך כלל את התחלת המחקר או את ההפעלה ראשונה של מערכת כלשהי.
הערך לעיתים קרובות מוגדר כ-, אולם ניתן להגדירו כקטן מ- על מנת לייצג את ההסתברות שמערכת נופלת מיד עם הקמתה.
באנליזה לא סטנדרטית, פונקציית החלק הסטנדרטי, או צל, היא פונקציה מהמספרים הסופיים ההיפר-ממשיים למספרים הממשיים.
פונקציית החלק סטנדרטי "מעגלת" מספר סופי היפר-ממשי למספר ממשי הקרוב ביותר.
היא מייחסת לכל היפר-ממשי את המספר הממשי היחיד כאשר הוא אינפיניטסימל.
היחס הזה מתבטא על ידי נוסחה .v החלק הסטנדרטי של כל אינפיניטסימל הוא 0.
במתמטיקה, פונקציית האינטגרל הלוגריתמי היא פונקציה מתמטית חשובה, הידועה בעיקר בזכות משפט המספרים הראשוניים.
לפונקציה יש סינגולריות בתחום t=1, ולכן הפונקציה מוגדרת במדויק לכל , ומוגדרת לכל באמצעות הערך הראשי של קושי , בנוסחה:
פונקציית האינטגרל הלוגריתמי או פונקציית האינטגרל הלוגרתמי של אוילר מוגדרת להיות:
פונקציה זו אינה בעלת נקודה סינגולרית, והיא מדויקת בחישוב כמות של מספרים ראשונים הקטנים מ-x.
הצגות נוספות של פונקציית האינטגרל הלוגריתמי
הצגה על ידי פונקציית האינטגרל האקספוננטי
לפונקציה יש קשר עם פונקציית האינטגרל האקספוננטי (Ei(x)) על ידי המשוואה:
שנפתרת על ידי כל מספר חיובי.
קשר נוסף הוא על ידי קבוע אוילר-מסקרוני:
חישוב נוסף של פונקציית האינטגרל הלוגריתמי היא:
הצגה על ידי הרחבה אסימפטוטית
ניתן להציג את פונקציית האינטגרל הלוגריתמי גם על ידי הרחבה אסימפטוטית שיש לו.
כאשר O הוא סימון לנדאו.
רישום מלא של הפונקציה על ידי הרחבה אסימפטוטית הוא:
רישום זה גורר לרישם הבא:
הערה, הרישום האחרון כסדרה אינו מתכנס, אז חשוב לסדרה תהיה מספר סופי של איברים.
לפונקציה יש שורש חיובי יחיד, הידוע בתור קבוע רמנוג'אן-סולדר, אשר קרוב שלה הוא x ≈ 1.45136 92348 ...
.בנוסף לכך, הערך של הפונקציה בנקודה x=2 הוא כאשר היא פונקציית גמא הלא שלמה.
במתמטיקה ובעיקר בתורת המספרים, פונקציית המספרים הראשוניים (ללא קשר למספר פאי) היא פונקציה הסופרת את כמות המספרים הראשוניים שגודלם אינו עולה על כלשהו.
הפונקציה ידועה בעיקר ממשפט המספרים הראשוניים, הטוען כי פונקציית המספרים הראשוניים אסימפטוטית לפונקציה
כאשר היא פונקציית האינטגרל הלוגריתמי.
עובדה זו שוערה לראשונה על ידי גאוס ולז'נדר בסוף המאה ה-18 בנפרד, והוכחה על ידי אדמר ופוסן ב-1896 כשהם מתבססים על מאפיינים של פונקציית זטא של רימן שרימן הציג בשנת 1859. המשפט הוכח ללא שימוש בפונקציית זטא של רימן או אנליזה מרוכבת על ידי פאול ארדש בשנת 1948.
במכניקת הזורמים, פונקציית הזרם של סטוקס משמשת כדי לתאר את קווי הזרימה ומהירות הזרימה בזרימה אי-דחיסה תלת-ממדית עם סימטריה גלילית.
משטח עליו יש ערך קבוע של הפונקציה תוחם שפופרת זרימה, המשיקה בכל מקום לווקטורי שדה הזרימה.
יותר מכך, השטף הנפחי של הזרימה לאורך שפופרת הזרימה הזאת קבוע - בהגדרתה פונקציית זרם היא נקייה מדיברגנצים (אין בה בורות או מקורות).
פונקציית הזרם הזאת נקראת על שם ג'ורג' גבריאל סטוקס.
השימוש בפונקציית הזרם הוא בכל בעיה בה הזרימה היא בעלת סימטריה סביב ציר מסוים.
סטוקס נעזר בה במקור כדי לחשב את שדה המהירות מסביב לספירה ברדיוס a בגבול של מספרי ריינולדס נמוכים.
הדבר אפשר לו לגזור את חוק סטוקס לזרימה צמיגה.
רקע: פונקציית זרם ופוטנציאל מהירות
פונקציית הזרם היא דרך לתאר את התפלגות הספיקה הנפחית של זרימה במרחב.
למשל, במקרה הדו-ממדי, הפרש הערכים שלה בין שני קצוות של עקום מבטא את הספיקה הכוללת של הזרימה דרך העקום הזה.
יש להבהיר שפונקציית זרם יכולה להיות מוגדרת היטב רק במקרה של זרימה נטולת מקורות או בורות, בדיוק כשם שפונקציית פוטנציאל מהירות מוגדרת היטב רק לזרימה ללא ערבוליות.
אחרת, ניתן לבנות מסלול סגור (או משטח סגור במקרה התלת-ממדי), ולקבל שכאשר הולכים לאורכו עד שחוזרים לנקודת ההתחלה ערך פונקציית הזרם משתנה - כלומר היא אינה מקבלת ערך יחיד בנקודה (פונקציה רב-ערכית).
לפונקציית הזרם יש התנהגות הפוכה לזה של פוטנציאל המהירות ; בכיוון המרחבי בו פוטנציאל המהירות משתנה בצורה המרבית פונקציית הזרם אינה משתנה כלל, בעוד בכיוון בו פונקציית הזרם משתנה בצורה המרבית פוטנציאל המהירות אינו משתנה כלל.
בשפה מתמטית: , כלומר המכפלה הסקלרית של גרדיאנט פונקציית הזרם בגרדיאנט פוטנציאל המהירות היא אפס (שני הווקטורים ניצבים זה לזה).
אינטואיטיבית, התמונה נראית כך: פוטנציאל המהירות משתנה בצורה המרבית כאשר הולכים לאורך קו הזרם, בעוד פונקציית הזרם משתנה בצורה המרבית כאשר הולכים בניצב לקו הזרם (כלומר היא "סופרת" את קווי הזרימה).
לכן, קווים הניצבים לקווי הזרם נקראים גם קווים "שווי פוטנציאל" (פוטנציאל המהירות).
בקואורדינטות כדוריות ( r, θ, φ ), המרחק הרדיאלי מהראשית הוא r, הזווית θ היא זווית הזנית ו- φ היא הזווית האזימוטלית.
בזרימה עם סימטריה גלילית, בה θ = 0 הוא ציר הסימטריה הסיבובית, הגדלים שמתארים את הזרימה הם בלתי תלויים באזימוט φ.
מכיוון שאלמנט נפח בקואורדינטות כדוריות מקיים:
כיוון שפונקציית זרם מוגדרת כך שהפרש ערכיה בין שתי נקודות (או עקומות סגורות במקרה התלת-ממדי) שווה לספיקה העוברת דרך קו המחבר ביניהן, ניתן לקבל לפי הגדרת פונקציית הזרימה ש-:
השטף הנפחי דרך שפופרת זרם התחומה על ידי משטח שעליו ערך הפונקציה ψ קבוע, הוא 2π ψ.
הדיברגנץ של שדה הזרימה בכל נקודה במרחב, לפי הנחת אי-הדחיסות של הזורם, הוא:
ו- הוא וקטור יחידה בכיוון (הכיוון האזימוטלי).
גזירה של הערבוליות באמצעות פונקציית הזרימה של סטוקס
מהגדרת הרוטור בקואורדינטות כדוריות נקבל:
ראשית שים לב שרכיבי העירבוליות בצירים ו- שווים לאפס.
שנית, נציב את הביטויים ל- ו- בביטוי ל-.
לאחר מכן, התהליך האלגברי הבא מניב:
כתוצאה, החישוב של וקטור הערבוליות נותן:
כאשר האופרטור E המוגדר כ-: הוא אופרטור חשוב בחישוב פילוג הלחץ על כדור (פילוג מאמצי הלחיצה) וכוחות הצמיגות (פילוג מאמצי הגזירה) שהזורם מפעיל על השכבה הצמודה לכדור, ולפיכך שימוש בו הוא שלב קריטי בגזירת חוק סטוקס: .
בסטטיסטיקה, פונקציית הניקוד () של פרמטר היא הגרדיאנט של לוג פונקציית הנראות בכיוון של הפרמטר.
הפונקציה מציינת עד כמה רגישה פונקציית הנראות לשינויים ב-.
פונקציית הנראות ממלאת תפקיד חשוב במספר היבטים של הסקה סטטיסטית, כגון:
מציאת סטטיסטי מבחן בעל עוצמה מקסימלית מקומית
הערכת גודל השגיאה של אומד נראות מקסימלית
פונקציית הניקוד ממלאת גם תפקיד חשוב בסטטיסטיקה חישובית , שכן היא יכולה לקחת חלק בחישוב של אומדי נראות מקסימלית.
הערך של פונקציית הניקוד (או בקיצור: "הניקוד") הוא הגרדיאנט (וקטור של נגזרות חלקיות), בהתייחס לפרמטר מסוים , של הלוגריתם (בדרך כלל הלוגריתם הטבעי) של פונקציית הנראות.
אם התצפית היא והנראות שלה היא , אז הניקוד ניתן לחישוב לפי כלל השרשרת באופן הבא:
לכן הניקוד מציין את הרגישות של (הנגזרת כשהיא מנורמלת על ידי ערך הפונקציה).
היא פונקציה גם של התצפית אך גם של הפרמטר , לכן זהו לא סטטיסטי.
אף על פי כן ניתן להשתמש בו ביישומים מסוימים, על ידי חישוב ערך הפונקציה עבור ערך ספציפי (כמו ערך ה- של השערת האפס, או אומד הנראות המקסימלית של ), והתוצאות של חישובים אלו הן סטטיסטים.
תחת תנאי רגולריות מסוימים, התוחלת של פונקציית הניקוד בהתייחס לתצפית , בהינתן הפרמטר האמיתי , כלומר , שווה ל-0. על מנת לראות זאת נכתוב מחדש את פונקציית הנראות כפונקציית צפיפות: , ואז:
אם תנאי גזירות מסוימים מתקיימים, אינטגרל זה שווה:
מכיוון שהתוחלת של פונקציית הניקוד היא 0 כאמור לעיל, אם נדגום פעם אחר פעם מהתפלגות מסוימת, ובכל פעם נחשב את הניקוד, אז ממוצע ערכי הניקוד ישאף ל-0 כשמספר הדגימות ישאף לאינסוף.
השונות של פונקציית הניקוד ידועה בשם האינפורמציה של פישר, ומסומנת .
מכיוון שהתוחלת של פונקציית הניקוד היא 0, ניתן לנסח את השונות בצורה הבאה:
האינפורמציה של פישר כפי שהוגדרה לעיל, איננה פונקציה של תצפית מסוימת, אלא רק של הפרמטר , שכן המשתנה המקרי מתקזז בנוסחה.
מושג זה של אינפורמציה שימושי כשמבצעים השוואה בין שתי שיטות תצפית מתהליך סטוכסטי כלשהו.
פונקציית הפסד או פונקציית עלות היא פונקציה הממפה מאורע או ערכים של משתנה אחד או יותר למספר ממשי המייצג "עלות" של מאורע.
בבעיות אופטימיזציה מנסים למזער את פונקציית ההפסד.
פונקציות הפסד או עלות נמצאות בשימוש נרחב במגוון תחומים בהם אופטימיזציה מתמטית, סטטיסטיקה, אקונומטריקה, תורת ההחלטות ולמידת מכונה.
בתחומים מסוימים מתייחסים לפונקציית מטרה שעשויה להיות פונקציית הפסד או הפונקציה הנגדית שלה שאותה רוצים למקסם (למשל פונקציית תועלת ופונקציית כשירות).
בסטטיסטיקה נעשה שימוש בפונקציית הפסד באמידת פרמטרים, כשפונקציית ההפסד אומדת את הסתברות המאורע של תצפיות הנתונים על פי הפרמטרים הנאמדים.
שימוש בפונקציית הפסד ריבועית נפוץ בין היתר בבעיות רגרסיה ליניארית למשל בשיטת הריבועים הפחותים.
אחד היתרונות של פונקציה ריבועית ביחס לפונקציות הפסד אחרות הוא הסימטריות שלה - שגיאה של הערכה מעל המטרה או מתחת למטרה יתנו הפסד דומה.
כאשר ערך המטרה הוא t ניתן להציג פונקציית הפסד ריבועית כך:
כאשר C הוא קבוע (שאותו אפשר גם להגדיר כאחד).
בסטטיסטיקה ובתורת ההחלטות אחת מפונקציות ההפסד המוכרות היא פונקציית הפסד 0-1:
אחת מפונקציות ההפסד הנפוצות בלמידת מכונה היא פונקציית הפסד Hinge המוגדרת:
כאשר מייצג את המטרה, ו־ הוא הפרדיקציה.
במתמטיקה ובפרט בתורת הקבוצות, פונקציית גימל היא פונקציה המסומנת באות העברית ג, אשר פועלת על מספרים מונים, ומוגדרת על פי הנוסחה:
כאשר היא הקופינליות של .
ממשפט קניג נובע כי : תהי ולכן לכל מותאם מספר מונה כך ש- .
אם הוא מונה סדיר, אז .
השערת גימל היא ההשערה לפיה כאשר הוא העוקב של .
פונקציית דן של חבורה נוצרת סופית היא פונקציה המתארת את אי-השוויון האיזופרימטרי בגרף קיילי של החבורה, ומודדת את הסיבוכיות של פתרון בעיית המילה בחבורה זו.
תהי G חבורה הנוצרת על ידי קבוצה X עם קבוצת יחסים R.
כל מילה w המייצגת את איבר היחידה אפשר להציג כמכפלה של צמודים , כאשר הם יחסים.
המספר המינימלי של יחסים כאלה הוא השטח של w.
פונקציית דן המתאימה ל-X מוגדרת כך ש- הוא השטח הגדול ביותר של מילים באורך n.
מגדירים יחס שקילות על פונקציות, כך ש- אם קיים קבוע c כך ש-, וכן להפך.
כל שתי פונקציות דן של אותה חבורה שקולות זו לזו.
בפרט, אם פונקציית דן שקולה לחזקה , אז המעלה מוגדרת היטב.
יש חבורות מוצגות סופית עם פונקציות דן כאלה עבור קבוצה צפופה של ערכים .
פונקציית דן עשויה להיות אקספוננציאלית, אפילו עבור חבורה מטא-אבלית.
כל פונקציית דן תת-ריבועית היא ליניארית.
חבורה היא היפרבולית אם ורק אם יש לה פונקציית דן ליניארית.
יש חבורות רבות עם פונקציית דן ריבועית: כל חבורה אבלית, כל חבורה חופשית-על-ציקלית, חבורת תומפסון, וגם החבורות כאשר .
פונקציית דן קשורה בזמן הריצה של מכונת טיורינג לא דטרמיניסטית הפותרת את בעיית המילה בחבורה.
למעשה, הפונקציה רקורסיבית אם ורק אם בעיית המילה פתירה.
בעיית המילה של חבורה נוצרת סופית היא במחלקת הסיבוכיות NP אם ורק אם החבורה מוכלת בחבורה מוצגת סופית שיש לה פונקציית דן פולינומית.
עם זאת, יש חבורה מוצגת סופית עם פונקציית דן ריבועית, שבעיית הצמידות שלה אינה פתירה.
בעיית האיזומורפיזם פתירה עבור חבורות היפרבוליות, אבל לא עבור חבורות מוצגות סופית עם פונקציית דן ריבועית.
פונקציית דן של תת-חבורה עשויה לגדול מהר יותר מזו של החבורה עצמה.
פונקציית המשולש היא פונקציה שהגרף שלה הוא בצורת משולש, פעמים רבות משולש שווה-צלעות שגובהו 1 ואורך בסיסו 2. פונקציית המשולש שימושית בעיבוד אותות ובהנדסת מערכות תקשורת, כמייצגת של אותות אידיאליים, שממנה ניתן לגזור פונקציות מציאותיות יותר.
הפונקציה שימושית גם באפנון דופק מקודד כצורת דופק לשידור אותות דיגיטליים וכמסנן מתואם לקליטת האותות.
היא משמשת גם להגדרת החלון המשולש .
ההגדרה הנפוצה של פונקציית המשולש היא:
באופן שקול ניתן להגדיר את הפונקציה כקונבולוציה של שתי פונקציות מלבן זהות:
את פונקציית המשולש ניתן להציג גם כמכפלה של פונקציית המלבן ופונקציית הערך המוחלט:
יש שמגדירים את פונקציית המשולש כבעל בסיס באורך 1 (במקום 2) כך:
ההגדרה הכללית של פונקציית המשולש היא:
במסגרת הגדרה כללית זו, ההגדרה שבתחילת פרק זה היא מקרה פרטי:
כאשר היא פונקציית ה-sinc המנורמלת.
פונקציית גיבוב מתגלגלת היא פונקציית גיבוב אשר מופעלת על חלקים שונים של מידע כלשהו, בכדי להשוות מול תוצאות גיבוב של בקשות חיפוש.
השימוש העיקרי בה הוא האצת חיפושים.
תהליך הגיבוב נעשה בסוג של "חלון מתגלגל", כלומר חלקי המידע בגודל קבוע עוברים אחד אחד את תהליך הגיבוב ומושווים מול תוצאת הגיבוב של החיפוש.
הרעיון מאחורי זה הוא שבמקרים רבים השוואת תוצאות הגיבוב של חלקי המידע אל מול בקשת החיפוש מהירה יותר מהשוואה ישירה של חלקי המידע מול בקשת החיפוש.
כלומר השוואת תוצאות הגיבוב מורידה את סיבוכיות החיפוש לפעמים.
ראשית, המידע לחיפוש עובר גיבוב בפונקציה ידועה מראש.
שנית, המידע בו נרצה לחפש עובר גיבוב בחלקים (אשר גודלם נקבע על ידי גודל בקשת החיפוש).
ב"חלון מתלגלג" אנו בוחרים מעין "חלון" (חלק מהמידע באורך החיפוש) ובכל פעם מעבירים אותו בפוקנציית הגיבוב ומשווים אל מול תוצאת הגיבוב של החיפוש.
שלישית, אם נמצאה התאמה בין פונקציות הגיבוב ניתן לאמת את ההתאמה בבדיקות אחרות.
אם נרצה לחפש "דהו" ב"אבגדהוזחטיכלמנסעפצקרשת"
ראשית, נקבל את תוצאת הגיבוב של "דהו", נניח לדוגמה בלבד שפוקנציית הגיבוב היא חיבור ערכי הגימטריה, כלומר במקרה הגיבוב של "דהו" יהיה: 4(ד) + 5(ה)+ 6(ו) = 15.
שנית, נעבור "בחלון מתלגל" על המידע ונחשב את ערכי הגיבוב בכל פעם עד שנמצא התאמה, כאשר נשים לב שאורך ה"חלון" הוא כאורך החיפוש שרצינו (שלושה תווים):
אם מצאנו התאמה, נוכל להשוות בצורה ישירה (לדוגמה אינדקס מול אינדקס) כדי לוודא שההתאמה נכונה, זאת מכיוון שיכולות להיות מספר התאמות בפונקנציות הגיבוב לקטעי מידע שונים בגלל שפונקציות הגיבוב בהם משתמשים באלגוריתם זה אינן בהכרח חד חד ערכיות.
אם ההשוואה הישירה לא צלחה, נמשיך בחיפוש עד סוף המידע.
מכיוון שהחיפוש במקרה שלנו כן מתאים, ניתן להגיד שמצאנו את המידע שחיפשנו.
במילים אחרות, אם נניח (או ) כסיבוכיות ההשוואה של פיסות המידע לאחר ההתאמה בגיבוב, כאשר m שואף ל n (הרבה התאמות מול הגיבוב), נקבל .
במתמטיקה, פונקציית הדיגמא מוגדרת כנגזרת הלוג של פונקציית הגמא:
זאת הראשונה מבין פונקציות הפוליגמא.
פונקציה זו מונוטונית עולה ממש וקעורה ממש על , והיא שקולה אסימפטוטית ל-
עבור () בגזרה לכל .
פונקציית הדיגמא מסומנת לעיתים קרובות כ- או .
פונקציית הגמא מקיימת את המשוואה
ניקח לוג של שני האגפים:
מכיוון שהמספרים ההרמוניים מוגדרים עבור מספרים שלמים חיוביים
כאשר ו- הוא קבוע אוילר-מסקרוני.
עבור ארגומנטים של חצי מספר שלם פונקציית דיגמא מקבלת את הערכים
אם החלק הממשי של הוא חיובי אז לפונקציית הדיגמא יש את הייצוג האינטגרלי של גאוס:
שילוב של ביטוי זה עם זהות אינטגרלית עבור קבוע אוילר-מסקרוני נותן:
האינטגרל הזה הוא המספר ההרמוני של אוילר , כך שניתן לכתוב:
כתוצאה מקבלים הכללה של נוסחת נסיגה:
מהייצוג האינטגרלי של גאוס ניתן לקבל את הנוסחה הבאה של .
נוסחה זו היא גם תוצאה של האינטגרל הראשון של בינה עבור פונקציית הגמא.
ניתן לזהות את האינטגרל כהתמרת לפלס.
האינטגרל השני של Binet לפונקציית גמא נותן נוסחה שונה עבור :
מתוך ההגדרה של והייצוג האינטגרלי של פונקציית הגמא, מקבלים
הפונקציה היא פונקציה שלמה, והיא יכולה להיות מיוצגת על ידי מכפלה אינסופית:
כאשר הוא האפס ה- של (ראה להלן) ו- הוא קבוע אוילר-מסקרוני.
הערה: זה גם שווה ל- בשל ההגדרה של פונקציית הדיגמא:
מנוסחת המכפלה של אוילר לפונקציית הגמא, בשילוב עם המשוואה הפונקציונלית וזהות עבור הקבוע של אוילר-מסקרוני, מתקבל הביטוי הבא לפונקציית הדיגמא, התקף במישור המורכב פרט למספרים השלמים השליליים (אברמוביץ וסטגון 6.3.16):
חישוב סכומים של פונקציות רציונליות
ניתן להשתמש בזהות לעיל כדי להעריך סכומים מהצורה
כאשר ו- הם פולינומים של .
פירוק לשברים חלקיים של בשדה המורכב, במקרה שבו כל השורשים של הם שורשים פשוטים,
אחרת הטור יהיה גדול מהטור ההרמוני ויתבדר.
ניתן לקבל גם נוסחה כללית באמצעות טורים עם פונקציות פוליגמא בדרגה גבוהה יותר:
לדיגמא יש טור זיטה רציונלית, הניתן על ידי פיתוח טור טיילור סביב הנקודה :
כאשר, היא פונקציית הזטה של רימן.
טור זה מתקבל מהטור טיילור של פונקציית הזטה של Hurwitz.
טור ניוטון לפונקציית דיגמא, המכונה לפעמים גם טור שטרן:
פונקציית הדיגמא מקיימת נוסחת שיקוף דומה לזו של פונקציית הגמא:
פונקציית האן (; נקראת גם מסנן האן, חלון האן או חלון פון האן) נקראת על שם המטאורולוג האוסטרי יוליוס פון האן .
זוהי פונקציית חלון המשמשת לביצוע החלקת האן.
הפונקציה, בעלת אורך ומשרעת , מוגדרת כך:
עבור עיבוד אותות ספרתי, הפונקציה נדגמת באופן סימטרי (עם מרווח דגימה של ומשרעת ):
יכול להיות זוגי או אי זוגי.
התמרת פורייה של ניתנת על ידי:
הפונקציה נקראת על שם יוליוס פון האן, שהשתמש בטכניקת ההחלקה הממוצעת המשוקללת של שלושה איברים על נתונים מטאורולוגיים.
עם זאת, המונח פונקציית האנינג (Hanning) המשמש גם באופן קונבנציונלי, נגזר מהמאמר שבו השתמשו בביטוי Hanning a sign במשמעות של החלת חלון האן על סימן (sign).
הבלבול נבע מפונקציית המינג הדומה .
משפחת פונקציות המינג המוכללת (או משפחת חלונות המינג המוכללת; ) היא משפחה של פונקציות חלון מסוג קוסינוס מוגבה (raised cosine) המהווה הכללה של פונקציית האן, והיא מוגדרת כך:
פונקציית האן מתקבלת עבור ().
פונקציית המינג (או חלון המינג) היא מקרה פרטי של משפחת פונקציות המינג המוכללת, המתקבלת עבור ().
פונקציית המינג קרויה על שם המתמטיקאי האמריקאי ריצ'רד המינג.
בכלכלה ובאקונומטריקה, פונקציית הייצור של קוב-דאגלס היא צורה פונקציונלית מסוימת של פונקציית הייצור, הנמצאת בשימוש נרחב לייצוג הקשר הטכנולוגי בין כמויות של שתי תשומות או יותר (במיוחד הון ועבודה) לבין כמות התפוקה שניתן לייצר על ידי תשומות אלו.
הפונקציה פותחה ונבדקה מול תצפיות סטטיסטיות על ידי צ'ארלס קוב ופול דאגלס בין השנים 1927 ו-1947. לפי דאגלס, הפונקציה עצמה נוסחה קודם לכן על ידי פיליפ ויקסטיד.
בצורתה הסטנדרטית ביותר לייצור של מוצר יחיד עם שני גורמים, הפונקציה ניתנת על ידי:
Y = סך התוצרת (הערך האמיתי של כל הסחורות שיוצרו בשנה או 365.25 ימים)
L = משתנה עבודה (שעות עבודה בשנה או 365.25 ימים)
K = משתנה הון (מדד של כל המכונות, הציוד והמבנים; ערך ההון מחולק במחיר ההון)
A = מקדם פריון כולל
ו הם גמישות ההון והעבודה של התפוקה, בהתאמה.
ערכים אלה הם קבועים שנקבעו על ידי הטכנולוגיה הזמינה.
הון ועבודה הם שני "גורמי הייצור" של פונקציית הייצור של קוב-דאגלס.
זמן קצר לאחר מותו של קנוט ויקסל בשנת 1926, פול דאגלס וצ'ארלס קוב יישמו את פונקציית קוב-דאגלס בעבודתם שעסקה באופן הנושא של תורת היצרנים בפעם הראשונה.
גמישות גורם הייצור של התפוקה היא השינוי באחוזים בתפוקה הנובע משינוי של 1% בגורם ייצור זה, תוך שמירה על קבועים של כל גורמי הייצור האחרים וכן של הפריון הכולל.
בפונקציית הייצור של קוב-דאגלס, גמישות ההון של התפוקה היא , בעוד שגמישות העבודה של התפוקה היא .
התוצר השולי של ההון הוא .
התוצר השולי של העבודה הוא .
כלומר, הגדלת ההון תמיד מובילה לעלייה בתפוקה, הגדלת העבודה תמיד מובילה לעלייה בתפוקה, והגדלת גורם הפריון הכולל.
מגדיל את התוצר השולי של ההון ואת התוצר השולי של העבודה.
פונקציית ויירשטראס היא הדוגמה הראשונה שפורסמה לפונקציה רציפה בכל נקודה על הישר הממשי אך לא גזירה באף נקודה.
לפי משפט הקטגוריה של בר, אוסף הפונקציות הרציפות הגזירות בנקודה אחת לפחות הוא קבוצה מקטגוריה ראשונה.
בצורה פשטנית אומר המשפט כי "רוב" הפונקציות הרציפות אינן גזירות באף נקודה, אולם המשפט אינו מצביע על פונקציה מסוימת כזו.
הדוגמה הראשונה שפורסמה לפונקציה כזו היא זו שנתן קארל ויירשטראס בשנת 1872 (היסטורית, הדוגמה של ויירשטראס קדמה להוכחת משפט הקטגוריה).
הגדרת הפונקציה היא: כאשר שלם אי-זוגי ו-.
פונקציית ויירשטראס מורכבת מאינסוף עותקים של הרמוניה בסיסית, העוברת שני שינויי סקלה (במשרעת ובתדירות).
גרף הפונקציה הוא פרקטל, שממד האוסדורף שלו הוא .
ניתן להוכיח שהפונקציה רציפה, משום שהטור מתכנס במידה שווה (ממבחן M של ויירשטראס), וכל סכום חלקי מהווה פונקציה רציפה (ולכן נוכל להשתמש במשפט הגבול האחיד , הגורס כי אם סדרת פונקציות רציפות מתכנסת במידה שווה, אז הפונקציה הגבולית רציפה).
ההוכחה שהפונקציה אינה גזירה באף נקודה מורכבת יותר.
במתמטיקה, פונקציית מביוס, המסומנת היא פונקציה אריתמטית שהוצגה לראשונה על ידי אוגוסט פרדיננד מביוס.
הפונקציה מוגדרת על המספרים הטבעיים והיא תלויה רק בפירוק לגורמים של המספר שעליו היא פועלת.
לפונקציה שימושים בתורת המספרים ובקומבינטוריקה, ויש לה גרסאות מוכללות (המוגדרות על קבוצה סדורה).
אם יש ל- גורם ריבועי אז .
אחרת הוא מכפלה של (נאמר) גורמים ראשוניים שונים, ואז .
כלומר, הפונקציה מחזירה 1 עבור מכפלה של מספר זוגי של ראשוניים, ו-1- עבור מכפלה של מספר אי-זוגי של ראשוניים, לרבות עבור הראשוניים עצמם.
פונקציית מביוס היא פונקציה כפלית, כלומר אם אז .
תכונה שימושית היא נוסחת ההיפוך של מביוס, הנובעת מהיותה של פונקציית מביוס האיבר ההופכי לפונקציה ביחס לקונבולוציית דיריכלה.
נסמן , פונקציית מספר המספרים בין 1 ל- שזרים ל-.
נרצה למצוא נוסחה לחישוב .
נסמן ב- את הראשוניים השונים שמחלקים את (ייתכן יותר מפעם אחת).
נחשב את לפי עקרון ההכלה וההפרדה: ראשית נוסיף את כל המספרים בין 1 ל-, יש כאלה.
אחר כך לכל נוריד את כל המספרים שמתחלקים בו, יש כאלה (לפירוש הסימון ראו פונקציית רצפה) אחר כך נוסיף לכל את כל המספרים שמתחלקים בשניהם, יש כאלה, וכן הלאה.
בסך הכל נקבל את הנוסחה:
שבעזרת פונקציית מביוס אפשר להציגה בדרך פשוטה יותר:
אם לוקחים הביטוי בתוך הערך השלם נהיה שלם; במקרה זה אפשר לפשט את הביטוי ל-, שהיא הנוסחה הידועה לחישוב פונקציית אוילר.
אם היא קבוצה עם יחס סדר חלש, פונקציית מביוס של הקבוצה מוגדרת לפי השוויון , כאשר המטריצה מתארת את היחס
עבור המספרים הטבעיים עם יחס החילוק, מתקבלת פונקציית מביוס הרגילה.
פונקציית זטא של רימן היא פונקציה מרוכבת הקרויה על שמו של המתמטיקאי ברנהרד רימן, ונודעת לה חשיבות רבה בתורת המספרים, בשל הקשר שלה להתפלגותם של המספרים הראשוניים.
לפונקציה שימושים גם בפיזיקה, בתורת ההסתברות ובסטטיסטיקה.
באפסים של פונקציה זו, שהם הערכים שהצבתם בפונקציה תיתן אפס, עוסקת השערת רימן, שהיא אחת הבעיות הפתוחות המרכזיות במתמטיקה.
הראשון שחקר את הפונקציה היה לאונרד אוילר במאה ה-18.
פונקציית זטא של רימן היא פונקציה מרוכבת המוגדרת עבור מספרים מרוכבים בעלי חלק ממשי גדול מ-1 על ידי .
לטור דיריכלה זה קיימת המשכה אנליטית יחידה לכל המישור המרוכב, עם קוטב פשוט בנקודה .
פונקציה זו היא הדוגמה המוכרת ביותר למשפחה של פונקציות הקרויות כולן פונקציות זטא.
ניתן לחשב באופן אנליטי את הערכים של פונקציית זטא בנקודות ממשיות שלמות זוגיות, באמצעות שוויון פרסבל.
כאשר n מספר טבעי ו הוא המספר ברנולי ה.
באפסים של פונקציה זו, שהם הערכים שהצבתם בפונקציה תיתן אפס, עוסקת השערת רימן: ההשערה קובעת שכל האפסים ה"לא טריויאליים", כלומר האפסים שאינם מהצורה כאשר טבעי, נמצאים על הישר .
השערה זו היא אחת הבעיות הפתוחות המרכזיות במתמטיקה.
הקשר בין פונקציית זטא למספרים הראשוניים נובע מנוסחת המכפלה של אוילר: , כאשר המכפלה עוברת על כל המספרים הראשוניים.
כפי שהיא מוגדרת בדרך כלל, על ידי הסכום , הפונקציה מתכנסת רק לערכים מימין לישר .
כדי להגדיר את הפונקציה על כל המישור, יש לבצע המשכה אנליטית: נשים לב תחילה ש-
האינטגרל בביטוי האחרון מתכנס מימין לישר , ואפשר להשתמש בשוויון הזה כדי להגדיר את הפונקציה בתחום הרחב יותר.
אם מגדירים , כאשר היא פונקציית גמא, אז מתקיים השוויון לכל מרוכב שאינו שלם.
משוואה זו, המדגימה את הסימטריה של פונקציית זטא ביחס לציר , היא הבסיס לתאוריה הענפה של פונקציה זו, ושל פונקציות זטא בכלל.
אפשר להוכיח אותה מן הזהות שמקיימת פונקציית תטא .
לפונקציית זטא של רימן יש גם גרסה סימטרית, שהיא פונקציית קסי של רימן, המוגדרת .
פונקציית החלוקה (מסומנת בדרך כלל )
היא מושג בפיזיקה, ובייחוד בתרמודינמיקה ומכניקה סטטיסטית.
מקור פונקציה זו היא בגורם נרמול של התפלגויות סטטיסטיות של מצבי מערכת פיזיקלית.
פונקציה זו מכילה מידע סטטיסטי רב על המערכת הפיזיקלית ובעזרתה ניתן לחשב גדלים תרמודינמיים רבים.
הפונקציה תלויה בטמפרטורה ובמאפיינים שונים של המערכת הפיזיקלית.
הפונקציה מסומנת באות Z, שהיא האות הראשונה של שמה הגרמני Zustandssumme (מילולית - סכום על מצבים).
פונקציית החלוקה עבור מערכת קנונית (מערכת עם מספר חלקיקים, טמפרטורה ונפח קבועים) מוגדרת על ידי:
כאשר הסכום הוא על כל המצבים האפשריים של המערכת.
היא האנרגיה במצב ה-T, i היא הטמפרטורה ו- הוא קבוע בולצמן.
פונקציה זו משמשת גורם נרמול עבור התפלגות בולצמן, לפיה הסיכוי שמערכת תמצא במצב בעל אנרגיה פרופורציוני ל-
כאשר Z (פונקציית החלוקה) היא מקדם פרופורציה.
על מנת שההתפלגות תהיה מנורמלת, סכום ההסתברויות עבור כל המצבים צריך להיות שווה ל-1, ולכן :
עבור מערכת קוונטית, ניתן לכתוב את פונקציית החלוקה גם כ
כאשר H הוא אופרטור ההמילטוניאן ו- היא העקבה.
עבור מערכת קלאסית בעלת רצף של אנרגיות, פונקציית החלוקה נתונה על ידי:
כאשר האינטגרציה מתבצעת על הקואורדינטות והתנעים של כל N החלקיקים ו־h הוא קבוע פלאנק
פונקציית חלוקה של מערכת הכוללת חלקיק יחיד, מכונה פונקציית חלוקה חד חלקיקית ומסומנת לרוב באות .
אם המערכת מורכבת מ-N חלקיקים זהים ללא אינטראקציה ביניהם, פונקציית החלוקה של כלל המערכת קשורה לפונקציית החלוקה החד חלקיקית באופן הבא:
הגורם נדרש במידה ומדובר בחלקיקים (קלאסיים) זהים שאינם ברי הבחנה (פרדוקס גיבס).
במידה והחלקיקים ברי הבחנה .
1. פונקציית החלוקה של גז אידיאלי של חלקיקים קלאסיים ללא דרגות חופש פנימיות:
2. פונקציית החלוקה של ספין 1/2 בשדה מגנטי H (בהנחה שהספין קבוע למקום):
3. פונקציית חלוקה של אוסצילטור הרמוני קוונטי בעל תדירות :
מפונקציית החלוקה ניתן לקבל את האנרגיה החופשית, שהיא הפוטנציאל התרמודינמי הקובע את התנהגות המערכת:
כעת, על ידי גזירת האנרגיה החופשית (או לחלופין פונקציית החלוקה), ניתן לקבל את כל הגדלים התרמודינמיים המאפיינים את המערכת.
ניתן גם לחשב את הפלוקטואציות בגדלים הנ"ל.
פונקציית החלוקה עבור מערכת גרנדקנונית (מערכת עם טמפרטורה ונפח קבועים, אך מספר החלקיקים המערכת משתנה), מסומנת לרוב על ידי אות Z מסולסלת ומוגדרת על ידי:
כאשר הוא הפוטנציאל הכימי של המערכת, הוא מספר החלקיקים במערכת במצב ה-i.
כמו קודם, הסכימה היא על כל מצבי המערכת האפשריים, היא האנרגיה במצב ה-T, i היא הטמפרטורה ו- הוא קבוע בולצמן.
קיים הקשר הבא בין פונקציות החלוקה הגרנדקנונית והקנונית:
כאשר היא פונקציית חלוקה קנונית עם N חלקיקים.
פונקציית החלוקה של גז אידיאלי של חלקיקים קלאסיים ללא דרגות חופש פנימיות:
ניתן לקבל את הפוטנציאל הגראנד קנוני ומנגזרות הפוטנציאל הגראנד קנוני את כל הגדלים התרמודינמיים הרלוונטיים למערכת.
במתמטיקה, פונקציית מדרגה, או פונקציית הביסייד (על שם אוליבר הביסייד) היא פונקציה המקבלת את הערך 0 עבור מספרים שליליים ואת הערך אחד עבור מספרים חיוביים, כלומר זוהי הפונקציה המציינת של הקרן :
(הערך ב- מוגדר לעיתים אחרת, למשל ).
הפונקציה רציפה בכל נקודה פרט ל-.
הפונקציה גזירה בכל נקודה פרט ל-.
הפונקציה אינטגרבילית בכל קטע סופי.
באופן לא פורמלי, "פונקציית הנגזרת" של היא הדלתא של דיראק (נוסח זה אינו נכון מתמטית מכיוון שפונקציית מדרגה אינה גזירה באפס).
זוהי דיסטריבוציה המקבלת בכל נקודה את הערך , פרט לנקודה בה היא "מקבלת את הערך אינסוף".
זהו תיאור איכותי בלבד ואיננו מדויק מתמטית.
באופן יותר ריגורוזי, מה שנכון לרשום הוא ש- פרט אולי ל-.
הפונקציה הקדומה של היא , שנקראת לעיתים פונקציית רמפה.
התמרת לפלס של פונקציית המדרגה היא .
בתורת המספרים ובתחומים אחרים במתמטיקה, פונקציית זטא הוא שם כללי לכמה פונקציות מרוכבות הלוקחות את השראתם מהדוגמה הראשונה והחשובה ביותר לפונקציה כזו - פונקציית זטא של רימן.
המושג אינו מוגדר באופן מדויק ומשמעותו תלויה בהקשר.
מאידך, ישנן פונקציות זטא רבות שאינן מקיימות תכונות אלו כלל.