PHP-OpenID-0.0.8.3 released

[Dan Libby]

Hi, below is a patch that works with PHP 4.x bcmath ( without bcpowmod()
).  It is based on Carl's function below.  However, I find that it is
still very slow, taking 5-10 seconds where built-in functions ( or an
external call to python ) take < 1 second.   Can anyone suggest a way to
make it faster?  Or better yet, working sample code......

One issue is that in PHP I can't do the "exp & 1" trick, because we are
dealing with strings, so had to use "exp % 2".

thanks,

Dan Libby


         else if( function_exists( 'bcpowmod' ) ) {
             return bcpowmod( $base, $exponent, $modulus );
         }
+        else if( function_exists( 'bcpow' ) && function_exists( 'bcmod'
) ) {
+            // Note that this is very slow.  In practice, it would be
faster
+            // to call perl or python ( below ). Possibly our _bcpowmod
func
+            // could be improved.
+            return oidUtilPhpBigInt::_bcpowmod($base, $exponent, $modulus);
+        }
         // Warning: here we give up on php and call python or perl to
help us out.
         // I'd like to replace this with native php code. Anyone know of
         // a good/fast implementation of powmod in php?
@@ -367,6 +373,19 @@
         }
         trigger_error("powmod: unsupported or non-integer argument",
E_USER_ERROR);
     }
+
+    function _bcpowmod($base, $exp, $mod) {
+        $square = bcmod($base, $mod);
+        $result = '1';
+        while( bccomp( $exp, 0 ) > 0 ) {
+            if (bcmod($exp, 2)) {
+                $result = bcmod(bcmul($result, $square), $mod);
+            }
+            $square = bcmod(bcmul($square, $square), $mod);
+            $exp = bcdiv($exp, 2);
+        }
+        return $result;
+    }

     // static
     function random( $minval ) {



Carl Howells wrote:

> Eww.  Don't do that.  That isn't just slow...  That's SLOW, SLOW, SLOW.
>
> I don't know PHP, so here's a function in python:
>
> def powmod(base, exp, mod):
>     square = base % mod
>     result = 1
>     while exp > 0:
>         if exp & 1:
>             result = (result * square) % mod
>         square = (square * square) % mod
>         exp /= 2
>
>     return result
>
> For any kind of large exponent (which Diffie-Hellman definitely
> qualifies as using), that function will be FAR faster than just:
>
> def powmod(base, exp, mod):
>     return (base ** exp) % mod
>
> It's far faster because it keeps the number of digits involved in the
> exponentiation under control.
>
> Use an equivalent of the first form, instead of an equivalent of the
> second form.  The performance difference is phenomenal.
>
> Carl
>