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

במקרה ההפוך, אם <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>\textstyle \frac{1}{2}\cdot \frac{1}{2}\cdot \frac{1}{2}\cdots</math> בסך הכול <math>n</math> פעמים או בקיצור <math>2^{-n}</math>. אם היא הצליחה לשלוח 80 תגובות נכונות לאתגרים של ויקטור הרי שהוא יכול בהחלט להיות סמוך ובטוח שאכן <math>y</math> הוא ריבועי מודולו <math>N</math> כי ההסתברות שהיא תצליח לרמותו היא <math>2^{-80}</math> שהיא סבירות זניחה מאוד.