Looking for PHP modular expt, i.e. pwrmod, library

Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

Threaded View
Does anybody know of a PHP library that emulates bigIntegers in
order to perform modular arithmetic (such as multiplication and
exponentiation) on them?

(The name "expt" in the Subject field comes from Lisp,
 where (expt b n) computes the Nth power of the base,
 as opposed to (exp n) which computes the Nth power of e = 2.718...)

Re: Looking for PHP modular expt, i.e. pwrmod, library

On 26 Feb, 21:49, seeWebInst...@rem.intarweb.org (Robert Maas,
http://tinyurl.com/uh3t ) wrote:
Quoted text here. Click to load it

BC which is part of the std PHP distribution?



Re: Looking for PHP modular expt, i.e. pwrmod, library

Quoted text here. Click to load it

That would allow me to interactively debug scripts from the stdio
shell application, but won't allow me to run the same scripts from
my ISP's HTTP server, unless it by chance *was* built with
--enable-bcmath. Let me build a HTTP-executable test script and see:

  echo function_exists("bcmul")+0,"\n";

=> prints 0 i.e. function not defined there either.

=> no mention of bcmath anywhere there.
   Additional Modules section is empty.

Now I could install my own version of the stdio application on my
shell account, and call it from the HTTP PHP server via tickmarks,
but then it'd have to start up the stdio application every time I
run my script, defeating the whole idea of using PHP (resident in
HTTP server) instead of regular CGI (starts up separate
script/application each time script is run).

Now let me FTP the test script to my gigabyte PHP-only hosting
account to see whether bcmath is installed there, because on those
systems there is *no* option of running tick commands and/or
installing my own stdio applications:
=> prints 1, i.e. presumably bcmath is installed there.
=> Configure Command './configure' ... '--enable-bcmath' ...

Quick check of my backup/debug hosting sites:
=> Configure Command './configure' ... '--enable-bcmath' ...
=> Configure Command './configure' ... '--enable-bcmath' ...

So in theory I could write completely different bcmath code for my
Unix shell account vs those free PHP-only hosting services, calling
bcmath functions directly on free-hosting, but doing a very
complicated tick-command interface on shell account, maybe using
XML to communicate parameters to bcmath functions and get the
results back, restarting the tick-sub-php each time I want to do a
little bit of bcmath in the main script. NOT WORTH THE TROUBLE!!

Or alternately not even using the PHP service available within the
HTTP server, using regular CGI instead to run the entire PHP script
within the stdio-PHP application. UGH!

I think it would be less trouble to re-invent the wheel, writing my
own alternative bcmath library and using it whereever bcmath itself
isn't available. But that would be a lot of effort too!!

But if there's a way I can just load bcmath into an existing php
session if it's not already installed, one of line of code at the
top of any script that will need bcmath, and then all the rest of
the code would directly call bcmath functions in either case, that
would be much better. Ditto if gmp could be loaded into an
already-running PHP script. Or if there's some *other* big-integer
arithmetic library which *can* be loaded into an already-running
PHP script per my original posting that started this thread?

Re: Looking for PHP modular expt, i.e. pwrmod, library

(Snipped remarks about tick-sub-processing a different version of
 PHP or Lisp from inside the non-BCMATH HTTP PHP server.)

Quoted text here. Click to load it

As reported on Twitter.Com/CalRobert, I've finished writing my own
version of big-decimal-string arithmetic, including modular powers
needed for public-key cryptosystems. With a 60-digit number for
each of exponent and modulus, b ^ e (mod m) takes about 1.5 seconds
in PHP using my wheel-reinvent alternate-to-bcmath, compared to
0.006 seconds in Common Lisp using its built-in big-integers
(binary-number chunks, not strings of decimal digits).

Re: Looking for PHP modular expt, i.e. pwrmod, library

Robert Maas, http://tinyurl.com/uh3t wrote:
Quoted text here. Click to load it

Wow.  Talk about inefficient...

Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.

Re: Looking for PHP modular expt, i.e. pwrmod, library

On Sun, 01 Aug 2010 15:19:11 -0400, Jerry Stuckle wrote:
Quoted text here. Click to load it

I suspect that that was rather the point. As in "It sucks; don't rewrite
stuff that you need that's already done properly. Change hosts instead."

90. I will not design my Main Control Room so that every workstation is
    facing away from the door.
    --Peter Anspach's list of things to do as an Evil Overlord

Re: Looking for PHP modular expt, i.e. pwrmod, library

Peter H. Coffin wrote:
Quoted text here. Click to load it

Peter, look at the author - then search some of his previous posts.

I really don't think that was the point.

Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.

Re: Looking for PHP modular expt, i.e. pwrmod, library

Quoted text here. Click to load it

Are you referring to my most recent implemented&available public
service http://TinyURL.Com/VTAorg which allows people to select and
display desired sections of public-transit (bus and light rail)
schedules on their cell-phones?

Or my still-in-development software to allow people to edit images
on a cell-phone, crop the unwanted parts of the image so that the
wanted part fills the one-inch screen? And the other part of the
same project which runs a Google image search and optimally fills
the screen with tiny versions of the found images and then lets the
user select one of them to expand to fill the width of the screen?
(Those two parts haven't yet been fitted together.)

Or something else I've been working on that is implemented mostly

Re: Looking for PHP modular expt, i.e. pwrmod, library

Quoted text here. Click to load it

Changing hosts is not an option. I don't know of any Unix shell
host that provides PHP service with bcmath and also provides
MacPPP-TELNET service for only $20/month, with free dialup in my
local area and also free local phone call for customer support. I
also don't know of any Unix or Linux host accessible by TELNET or
SSH from my current Unix shell account which is available to me at
no additional cost and also provides PHP with bcmath. Two years ago
one such host, in the UK, was briefly available, but the guy who
gave me the free account died and so the computer was shut down.

Regarding my post: I wasn't making a value judgement one way of the
other. I was just posting a progress report, updating from what I
had posted previously when I said I might re-invent the wheel but
it'd be a lot of work. I overestimated the work. It was only two
days of work, so it wasn't really a lot of work after all.

And for some purposes, 1.5 seconds to process a public-key signed
packet isn't actually too long, so whereas before I had no way
whatsoever to decrypt a public-key message in PHP on my shell
account, now I do. So I've made some practical progress, although
we all agree something an order of magnitude faster would be
better, and my timing of tick-command to start CMUCL to do the math
inside CMUCL instead of PHP shows it is definitely feasible if I
decide to go that route.

Quoted text here. Click to load it

Hmm, that's another curious remark that would be a good teaser for
a silly-essay contest to include in http://TinyURL.Com/NewEco

Re: Looking for PHP modular expt, i.e. pwrmod, library

Quoted text here. Click to load it

Well, given that I'm doing all arithmetic directly in strings of
US-ASCII characters representing decimal digits, and that it's my
very first working draft version, not optimized in any way, of
course it's going to be a lot less efficient than Common Lisp which
uses machine-level unsigned-integer arithmetic fine-tuned over

After I posted, I timed bcmath itself: bcpowmod("5",$e,$m,0) where
$e and $m are each 60 digits took 0.018 second on netii, compared
to 0.006 second for the same exact calculation using Common LIsp on
my shell account. So I'm guessing that bcmath doesn't decimal
arithmetic internally. Most likely it converts decimal-string
parameters to machine 64-bit unsigned-integer arrays, does all the
actual arithmetic with those, programmed in machine language or
equivalent (C most likely), then converts the final result back to
decimal-digit strings to pass back to the PHP caller. Do you happen
to know whether that's true? Note those times aren't directly
comparable because the CPU on my shell machine might be a different
speed from the speed on netii. Since netii doesn't allow me to run
anything except PHP, and my shell ISP doesn't provide bemath, I
can't run both bcmath and CMUCL on the same machine to directly
compare the two programs. However I did try running my new
decimal-string program on netii, whereby I'm running identical code
on both machines, thus can effectively compare CPU speeds:
 1.5  seconds on rawbw (my Unix shell account)
 2.95 seconds on netii (free PHP-only hosting service)
thus it appears the PHP service on rawbw runs about twice as fast
as it does on netii.

So what could I do next? I timed back-tick calls:
0.03  sec - just to start up php from back-tick and do simple test
0.1   sec - just to start up cmucl from back-tick and immediately exit
Now if the CPU is really twice as fast on my shell account compared
to netii, then a single call to bcpowmod which took 0.018 second on
netii should take 0.009 seconds on rawbw. So I could either install
a version of PHP on my shell account with bcmath enabled and call
that from the regular HTTP-PHP service, or likewise call CMUCL from
HTTP-PHP, with backticks either way, with these predicted times:
0.03  + 0.009 = 0.039 seconds to call PHP+bcpowmod
0.1   + 0.006 = 0.106 seconds to call CMUCL+pwrmod
That's if I do only a single block of encrypted data, with only
signature or encryption. But I'll have the sender always sign and
encrypt the data, so the receiver always decrypts and unsigns, and
most SOAP messages will take more than one block of data. Assuming
5 blocks of data, that means 10 modular-power calculations. The
slower startup of CMUCL is nearly offset by the faster arithmetic
compared to bcmath. The timings would then be:
0.03  + 0.09 = 0.12 seconds to call PHP + ten bcpowmods
0.1   + 0.06 = 0.16 seconds to call CMUCL + ten pwrmods
Given the trouble it would take to re-build PHP with bcmath on my
private directory, and the extra disk space it'll consume, the
slight speed-up of PHP compared to CMUCL is not worth it. It'll be
fast enough (for my purposes) either way.

Still, having the main PHP script pack all encrypted data into a
block of data to pass to CMUCL and get the block of decrypted
results back, would be a bit awkward, so there are two others ideas
I m might try first:

Ask the sysadmin to please re-build our Apache+PHP server with
bcmath enabled, and take the whole system down briefly to switch
the server, inconveniencing several hundred other users during the
outage. The system has been brought down only twice in the past two
years, once to upgrade to a new version of FreeBSD, and once when
the system hung for no known reason on Jul.17, so I sorta doubt the
admin will be willing to bring the system down again just to
install a PHP module requested by just one user who is paying only
$20/month for VT100-TELNET-PPP + shell + 500 megabytes disk (100 MB
for MySQL database, 400 MB for regular files). But I should at
least ask and see what he says. I might get lucky.

Write an alternate version of modular power which does all
arithmetic in PHP integers (up to about 18 digits long based on a
test I conducted), maintaining big integers as arrays of such
integers rather than strings of US-ASCII digit-characters,
converting from/to US-ASCII decimal-digit strings only on toplevel
call from regular PHP script, and see if it's "fast enough". Since
it only took me about 2 days to write the first version of
big-digit-string arithmetic, it should only take me another 2 or so
days to re-do the algorithms using arrays of nearly-64-bit
integers. Anybody want to predict how long it'll take to
compute n ^ <60DigitInteger> (mod <60DigitInteger>) by that method?

Re: Looking for PHP modular expt, i.e. pwrmod, library

Robert Maas, http://tinyurl.com/uh3t schreef:
Quoted text here. Click to load it


Erwin Moller

"There are two ways of constructing a software design: One way is to
make it so simple that there are obviously no deficiencies, and the
other way is to make it so complicated that there are no obvious
deficiencies. The first method is far more difficult."
-- C.A.R. Hoare

Site Timeline