הצפנת בלום-גולדווסר – הבדלי גרסאות

הצפנת בלום גולדווסר יעילה מבחינה חישובית כיוון שהטקסט המוצפן המתקבל אינו גדול משמעותית מטקסט המקור, אלא במספר קבוע של סיביות (כגודל השלם <math>\ x_{t+1}</math> בסיביות). תהליך ההצפנה יעיל ודורש רק הכפלה מודולרית (מודולו <math>\ n</math>) אחת כדי להצפין <math>\ h</math> סיביות, כלומר עבור מודולוס בגודל <math>\ k</math> סיביות ומסר בגודל <math>\ l</math> סיביות תהליך ההצפנה לוקח <math>\ O(\frac{lk^2}{\mbox{log}\ k})</math> פעולות בסיסיות. לעומת RSA למשל שדורשת העלאה בחזקה מודולרית מלאה במידה והמעריך נבחר אקראית. ללא אופטימיזציה העלאה בחזקה מודולרית מלאה דורשת בממוצע <math>\ 3k/2</math> פעולות כפל מודולריות כאשר <math>\ k</math> שווה ללוגריתם בבסיס 2 של המודולוס. כמו כן תהליך הפענוח של אלגוריתם בלום גולדווסר דורש (בנוסף בשלב ההכנה) רק שלוש העלאות בחזקה מודולריות ללא תלות באורך המסר, יתר הפעולות דומות להצפנה, כלומר בסה"כ <math>\textstyle O(k^3)+O(\frac{lk^2}{\mbox{log}\ k})</math>. מה שאומר שעבור מסרים גדולים, שיטת בלום גולדווסר יעילה יותר מ-RSA.