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

הצפנת בלום גולדווסר יעילה מאוד מבחינה חישובית כיוון שהטקסט המוצפן המתקבל אינו גדול משמעותית מטקסט המקור, אלא במספר קבוע של סיביות (כגודל השלם <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>\יתר p</math>הפעולות דומות להצפנה, כלומר בסה"כ ו-<math>\ qO(k^3)+O(\frac{lk^2}{\mbox{log}\ k})</math> (שגודלם כמחצית סיביות המודולוס) כל היתר הם פעולות כפל. מה שאומר שעבור מסרים גדולים, שיטת בלום גולדווסר יעילה יותר מ-RSA.