הוכחה באפס ידיעה – הבדלי גרסאות

במקרה ההפוך, אם <math>y</math> אינו ריבועי מודולו <math>N</math>, אזי לא משנה איך היא בחרה את <math>s</math>, רק אחד משני הערכים יהיה נכון. כלומר או <math>s</math> או <math>ys</math> יהיו מספר ריבועי מודלו <math>N</math> אבל לא שניהם. כלומר לפגי יש סיכויים של 50% לשקר אם היא לא באמת יודעת מהם הגורמים הראשוניים של <math>N</math>. מכאן נובע שהיא תכשל באתגר בודד של ויקטור במחצית הפעמים במקרה הממוצע, כיוון שאם האתגרים הם רצף סיביות אקראיות הרי שבמחצית מן המקרים בממוצע (כאשר סיבית האתגר היא אפס) היא נדרשת להוכיח ש-<math>s</math> ריבועי מודולו <math>N</math> ומחצית מן המקרים היא נדרשת להוכיח ש-<math>ys</math> ריבועי. כך שאם <math>y</math> אינו ריבועי הסיכויים שפגי תספק מענה נכון בכל <math>n</math> הסבבים הם <math>2^{-n}</math>. אם היא הצליחה לשלוח 80 תגובות נכונות לאתגרים של ויקטור הרי שהוא יכול בהחלט להיות סמוך ובטוח שאכן <math>y</math> הוא ריבועי מודולו <math>N</math> כי ההסתברות שהיא תצליח לרמותו היא <math>2^{-80}</math> שהיא סבירות זניחה מאוד במונחים של ימינו.

 

 

להמחשה. לאחר שויקטור סיים את תהליך ההוכחה עם פגי נותרו בידו <math>n</math> שלשות ערכים <math>(s_1,\beta_1,z_1), (s_2,\beta_2,z_2),..., (s_n,\beta_n,z_n)</math> כשכל אחד מהם מקיים: