עבודה עם מספרים גדולים.

[shirbi]

עבודה עם מספרים גדולים.

אני צריך לממש מחלקה המתעסקת עם מספרים גדולים. במילה גדולים, כוונתי היא שמספר הספרות לא מוגבל, והוא יכול להגיע למאות ואף לאלפים. מה שמיממשתי עד כה הוא מחלקה המכילה רשימה מקושרת דו כיוונית של מספרים, כל אחד בן 16 ביטים, המייצגים ביחד את המספר. כאשר מבקשים לבצע פעולת חיבור, עוברים מהימני ביותר (LSB) ועד לשמאלי ביותר, ומבצעים חיבור כמו בכיתה ב', כאשר מעבירים CARRY מאחד לשני. כפל מתבצע באופן דומה, ע"פ האלגוריתם של כפל ארוך, וגם חיסור או השוואה אינם בעייתיים. הבעיה שנתקלתי בה היא כאשר אני מנסה לבצע פעולות כמו מודולו או חילוק, שבהן זמן הריצה הוא O של N בריבוע, כאשר N הוא מספר הביטים, ועבור N בסדר גודל של כמה אלפים, זה יכול לקחת כמה שניות טובות לבצע פעולת מודולו. יש לכם רעיון איך מבצעים מודולו (או חילוק - באמצעות חילוק, חיסור, כפל וחיבור, אין בעיה לממש מודולו) בזמן לינארי ביחס למספר הביטים? (ההודעה המקורית היתה בפורום שפות תכנות, http://www.tapuz.co.il/tapuzforum/main/addmsg.asp?id=1428 אולם שם לא קיבלתי שום רעיון).

 

[vinney]

המם...

למדת קצת מתמטיקה? בעזרת ייצוג פולינומים אתה יכול לבצע הכפלה בNLOG N, ולא בN בריבוע, שזה האלגוריתם הטריויאלי. תסתכל בפרק 32 בקורמן, או תחפש מקור אחר על כפלי פולינומים אמצעות מקדמים.

 

[shirbi]

הממ...

נדמה לי שזה מוכר לי מהקורס אלגוריתמים. נראה לי שאני אוותר על המימוש של זה. לא בזה מתמקד התרגיל - אחרי שאני אסיים לייצר את המחלקה הזאת, אני צריך לממש ספריה מתמטית שתומכת בביצוע פעולות חיבור, כפל וחזקה במודולו, המוגנת בפני התקפת תזמון (Timming attack). תודה בכל אופן.

 

[vinney]

להקל על החיפוש שלך

תתחיל מפה

 

[DadleFish]

הנה לינק

לספריה שעושה את מה שאתה צריך לעשות, בין היתר גם חילוק. רוב הספריה ממומשת באסמבלי עם תיעוד מצוין שיאפשר לך להבין. יש שם פונקציה מרכזית שמבצעת במקביל div ו-mod. LINT

 

[yossiea]

חילוק ארוך...

תראה האלגוריתם הטריוויאלי לביצוע חילוק ארוך במספרים מרובי ספרות פועל בסיבוכיות של O(lg n)^2) במילים אחרות האלגוריתם מבצע עבור המספרים x,y באורך n, t בהתאמה: (n-t)(t+3) פעולות בספרות בודדות. במספרים מנורמלים (normalization). אני לא יודע איך נסית לממש את האלגוריתם. לא הבנתי איך הגעת ל-O של N.

 

[vinney]

יוסי, זה לא טריויאלי ../images/Emo13.gif

ולא, אין אלגוריתם לינארי, הוא לא הגיע לזה, הוא רוצה להגיע לזה

 

[yossiea]

אם הבנתי נכון...

הוא הגיע למשהו גרוע יותר ממה שאמרתי. לא? כי log n בחזקת 2 זה הרבה יותר נמוך ממה שהוא אמר. רק רציתי להבין איך הוא מימש את זה. אני קראתי לאלגוריתם טריוויאלי להבדילו מאלגוריתמים יותר מורכבים שמיועדים למספרים גדולים מאוד (הדגש על מאוד). במספרים גדולים רגילים האלגוריתם הרגיל הוא היעיל ביותר שידוע (ולא מדובר כמובן באריתמטירקה מודולרית שם יש את מונטגומרי שהוא יעיל יותר). הזה די דומה למה שלמדנו בבית הספר עם כמה שיפורים מעניינים.

 

[shirbi]

לא, הגעתי לאותה סיבוכיות שאתה הגעת.

המטרה שלי היא אומנם לחשב מודולו, אבל אני מניח שאת האלגוריתם שאני אתאר אפשר להמיר בקלות לחשב גם חילוק: כאשר אני רוצה לחשב A מודולו B, אז אם A קטן יותר מ B אני מחזיר את A. אחרת: אני מחשב את B, B*2, B*4, B*8 וכן הלאה, עד שאני מגיע למספר שהוא יותר גדול מ A. מרגע זה אני מתחיל לחזור אחורה, וכל מספר שהוא יותר קטן מ A, אני מחסיר אותו מ A, עד שמה שנשאר מ A הוא קטן ממש מ B, ואז אני מחזיר אותו כתשובה. אם המספר מכיל N ביטים, אז כל הכפלה ב 2 דורשת O של N וכך גם חיסור וחיבור והשוואה. כמות המספרים שאני אחשב היא לכל היותר N, ולכן סה"כ האלגוריתם יעבור בסיבוכיות N בריבוע. אם n הוא הגודל של A, אז אני אצטרך כמובן log n בריבוע פעולות.

 

[yossiea]

בסדר אבל...

למה כל ההכפלות האלו (במאמר מוסגר אני מאוד מקווה שאתה לא מתכוון ממש לכפל אלא בעצם ל-shift כי אתה מדבר על חזקות של 2). אבל תחשוב לרגע על אסטרטגיה כזו. אם תיישר את B לשמאל של A ואז תבצע חיסור. (נניח לרגע שהבסיס הוא 10 אם כי הדברים נכונים לגבי כל בסיס) נניח למשל ש- A=12345678, B=456 תבצע חיסור כזה: 12345678 4560000 - ---------- 7785678 במילים אתה מזיז (shift) את B שמאלה לכיוון הספרות הגבוהות, כשאתה שומר על B נמוך מ-A מרפד באפסים ומבצע חיסור. כבר הקטנת את הבעיה בספרה אחת במחיר של פעולת חיסור אחת. חיסור דורש Lg B פעולות ומספר הלולאות הוא בערך Lg A - Lg B לולאות. אבל יש פה קטש קטן, אנחנו חייבים 'להרים' את B למקסימום האפשרי כדי להבטיח כי שבכל לולאה (פעולת חיסור) אחת הפחתנו ספרה מ-A וזאת מבלי להיתקל במצב ש-B יהיה גדול מ-A כי אנחנו לא רוצים לקבל תוצאה שלילית. אתה מבין? כי למשל אם A=890, B=20 כעת אם נבצע חיסור: 890 200- ---- 690 למרות ההזזה שמאלה אנחנו עדיין תקועים עם הספרה הגבוהה ולא הצלחנו להיפטר ממנה. הטריק הוא, כדי שנצליח להפטר ממנה אנחנו מבצעים "הערכת סיפרת מנה נוכחית" בעזרת שני ספרות העליונות של A חלקי הסיפרה העליונה של B. מכפילים את B בספרה זו ואז מזיזים שמאלה ומבצעים חיסור. למרות שאתה מעוניין בעצם רק בשארית כדאי לעקוב אחרי המנה כיון שהרעיון הוא לחסוך פעולות חיסור והערכת סיפרת המנה דורשת פעולה אחת. טוב צריך להוסיף את ההכפלה של B בסיפרת המנה לסיבוכיות, שים לב שזו הכפלה חלקית והיא לינארית. ועדיין אתה נשאר עם סדר גודל של Lg A * Lg A פעולות בדידות פחות או יותר. אהה. ויש עוד משהו, לפני שאנחנו מתחילים (בשלב הראשון בלבד) אנחנו חייבים לוודא שכאשר B מיושר לשמאל של A הוא גדול מ-A. כלומר בדוגמא האחרונה צריך קודם לבצע 890-200 כמה פעמים שידרש (4 פעמים) עד ש-B יהיה גדול מ-A (כשהוא מיושר לשמאלו). ולכן דיברתי על מספרים מנורמלים, כי הנירמול מבטל את הצורך בשלב ההכנה הזה. אם כי זה לא קריטי. אני מקוה שהבנת אותי...

 

[shirbi]

הבנתי בערך כי מימשתי בפועל משהו

דומה. במימוש שלי כל מספר מוחזק ע"י רשימה מקושרת של מבנים שכל אחד מהם מחזיק 16 ביטים. אז אם A מכיל בהתחלה 10 מבנים כאלו, ו B מכיל 3 מבנים כאלו, אז אני באמת מוסיף קודם אפסים ל B עד שהוא יכיל 9 מבנים ורק אז מתחיל להכפיל ב 2. בפועל, התוצאה תהיה אותו הדבר, וגם הסיבוכיות. היתרון הוא שלממש שיפט של כפולות של 16 הרבה יותר קל מבחינתי מאשר לממש דחיפה של ביט אחד, שדורשת ממני N/16 פעולות כי צריך להעביר ספרה מכל אחד מהמבנים למבנה הבא בתור. אגב, יש לכם מושג איפה יש באינטרנט מחשבון שעובד עם מספרים גדולים ועם פעולות מודולו כדי שאני אוכל לבדוק את התוצאות? בפרט אני צריך את הפעולה ( A בחזקת B) מודולו N.

 

[yossiea]

אגב מודולו...

אם אתה רוצה לממש חזקה מודולרית תנסה לממש את אלגוריתם מונטגומרי. נחשב לאחד האלגוריתמים הכי טובים שיש לחזקה מודולרית. אפשר לשלב אותו עם כל אלגוריתם לביצוע חזקות כמו sliding window וכו'. אתה יכול לבדוק את התוצאות שלך עם מחשבון רגיל. אם זה עובד במספרים קטנים זה יעבוד גם בגדולים. מחשבון מדעי נותן לך חישובים בסדר גודל של 30 ספרות, זה מספיק לדעתי בשביל הבדיקות לא?. לגבי הרשימה המקושרת לא הבנתי את זה? למה לא להשתמש במערך בתים פשוט למה לסבך את הענינים. מה היתרון בזה? וכשאתה אומר מכפיל ב-2 איך אתה מבצע כפל ב-2 של המבנים שלך? לא הבנתי מדבריך האם הכפל הזה זה פעולת shift או ממש כפל. ודרך אגב 2 ספרים אתה חייב לקרוא אם אתה מתעסק בנושא הזה, הספר של קורמן (cryptography in c and c++) והספר של מנזס (handbook of applied cryptography) בעיקר פרק 14. בהצלחה.

 

[shirbi]

30 ספרות זה מעט מדי.

המחלקה שלי אמורה להתמודד גם עם מספרי בני מאות ואף אלפי ביטים. לכן מחשבון מדעי, או המחשבון של וינדוס, לא מספיקים. מה גם שאין בהם פעולת העלאה בחזקה ואז מודולו. כלומר, אם אני רוצה לחשב מליון בחזקת מליון מודולו מליון ושש, אין לי דרך לעשות את זה, כי אני חייב קודם כל להעלות בחזקת מליון, ואז המספר גדול מדי. האלגוריתם שאני מכיר, (יכול להיות שזה מה שאתה קראת לו "מונטגומרי") הוא לקבוע משתנה T ל 1, ואז לעבור על כל הביטים של המאריך מה MSB ועד ל LSB, ועבור כל אחד מהם להכפיל את T בעצמו, ואז, אם הביט הוא 1, אז להכפיל את T במספר המקורי. כך עד הביט האחרון, ואז להחזיר את T. כמובן שבכל שלבי הביניים ניתן לבצע פעולת מודולו. הבעיה עם מערך זה מה לעשות כאשר צריך לשנות את הגודל שלו. יותר נוח לי להסתדר עם רשימות מקושרות (ומשום מה, גם יותר קל לדבג את זה בויזו'אל סטודיו, כי לגשת לתאים ספציפיים במערך זה צרה.) כרגע אני מממש כפל ע"י הכפלה פי 2 של כל אחד מהמספרים בני ה 16 ביטים, והעברת CARRY מאחד לשני. איך אתה היית עושה את זה בצורה יותר יעילה? אני לא מתכוון להתעסק בנושא יותר מדי. זה בסך הכל תרגיל בית שאני צריך לבצע.

 

[yossiea]

חזקות של 2...

א. אני חושב שלצורך הבדיקה אתה יכול לעשות משהו אחר. אם למשל אתה מחשב את M^E mod N ואתה רוצה לוודא שקיבלת תוצאה נכונה. אני עשיתי טריק קטן. ממשתי את RSA ועשיתי הצפנה ופיענוח והופ התוצאה הייתה נכונה קיבלתי את M בחזרה ועשיתי את זה עם מספר בן 1024 סיביות. אבל בכל זאת לא הבנתי אם האלגוריתם שלך עובד עם 30 ספרות למה שלא יעבוד עם 1000 לא הבנתי!. ב. האלגוריתם שאתה מתאר אינו מונטגומרי זהו "אלגוריתם חזקה וכפל" הרגיל והוא בסדר גמור. רק שלא משתמשים בו מעשית כיוון שיש את מונטגומרי כמו שציינתי. הבעיה היא בעיקר במודולו. אם למשל אתה מבצע M^E mod N למעשה אתה מקבל Lg E העלאות בחזקת 2 ועוד ממוצע של Lg E/2 הכפלות במקרים של סיבית 1 במעריך. זה תלוי במשקל הבינארי או Hamming Weught של המעריך. מה שעושים כדי לשפר ביצועים, א. את החזקות עושים עם טבלאות (רצוי לא טבלאות סטטיות כי יש בעיה עם Timing Attack) של חזקות כדי לבצע כפל מזורז במקום חזקות של 2. ולגבי המודולו האסטרטגיה היא להימנע מביצוע חילוק. עושים את זה בשיטות שאני לא יכול להרחיב כאן על זה. אבל נתתי לך 2 ספרים מצויינים בנושא. אגב הספר הראשון בטעות כתבתי שהוא של קורמן אבל השם צריך להיות קריימר. ג. עדיין אני סולד מהרשימות המקושרות. אתה יכול להקצות מערכים באיזה גודל שבא לך. ועוד משהו אתה יכול לבצע את החישובים בתוך buffer זמני אחרי הכל כמה פעמים תצטרך לשנות גודל מערך? זה נשמע לי לא טוב. ד. לגבי כפל ב-2 תראה קח משתנה 32 סיביות תבצע שיפט של סיבית אחת. ואז תקח את 16 הסיביות התחתונות בעזרץ AND ואז תוריד את הסיבית של ה-carry לחלק התחתון. תראה דוגמא באדיבות קריימר: c = (INT32)A + (INT32)B + (INT32)(INT16)(c >> INT16BITS) w = (INT16)(c)

 

[shirbi]

עוד שאלה בנושא

כחלק מהפונקציות שאני צריך לממש, אני צריך למצוא את המספר ההופכי של מספר X במודולו N. כלומר מספר Y כך ש X כפול Y שווה ל 1 במודולו N. אתם מכירים אלגוריתם שעושה זאת?

 

[yossiea]

אלגוריתם אוקלידס המורחב

האמת ידידי אתה קצת עקשן. אני מנסה לעזור לך ועוד בחינם אבל אתה משום מה מתנגד. אבל זה בסדר אני מקבל את זה ברוח טובה.