נתון מספר שלם p 2 , ויש להכריע האם p פריק או ראשוני. ענו רק על מה שנשאלתם. (א – 15%) הגדירו במדויק כיצד פועל א…

נתון מספר שלם $p \ge 2$ , ויש להכריע האם p פריק או ראשוני. ענו רק על מה שנשאלתם. (א – 15%) הגדירו במדויק כיצד פועל אלגוריתם Rabin-Miller (הגרסה הבסיסית שלו). ____________________________________________ ____________________________________________ (ב – 15%) נסחו ללא הוכחה את משפט Fermat. ____________________________________________ ____________________________________________ (ג – 70%) הוכיחו שאם p הינו מספר פריק שאיננו מספר Carmichael (כלומר יש ל-p לפחות עד Fermat אחד a שיש לו הופכי $a^{-1}$ מודולו p), אז מתקיים שהסתברות השגיאה של האלגוריתם מסעיף א' הינה לכל היותר ½ . ____________________________________________ ____________________________________________ ____________________________________________ ____________________________________________ ____________________________________________ 4