Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

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

5 views
Skip to first unread message

Robert Maas, http://tinyurl.com/uh3t

unread,
Feb 26, 2009, 9:49:46 PM2/26/09
to
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...)

C. (http://symcbean.blogspot.com/)

unread,
Feb 27, 2009, 10:45:00 AM2/27/09
to
On 26 Feb, 21:49, seeWebInst...@rem.intarweb.org (Robert Maas,

BC which is part of the std PHP distribution?

http://uk2.php.net/manual/en/intro.bc.php

C.

Erwin Moller

unread,
Feb 27, 2009, 10:47:04 AM2/27/09
to
Robert Maas, http://tinyurl.com/uh3t schreef:

http://nl.php.net/manual/en/book.bc.php

Regards,
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

Robert Maas, http://tinyurl.com/uh3t

unread,
Mar 7, 2009, 10:52:27 PM3/7/09
to
> > Does anybody know of a PHP library that emulates bigIntegers in
> > order to perform modular arithmetic (such as multiplication and
> > exponentiation) on them?
> From: "C. (http://symcbean.blogspot.com/)" <colin.mckin...@gmail.com>

> BC which is part of the std PHP distribution?
> http://uk2.php.net/manual/en/intro.bc.php

Ah, thanks very much? Any idea why the PHP implementation of
BigDecimal is called BC instead of BD?? It's supposed to mean
Binary Calculator, but it's not binary at all, it's decimal so it
should be DC i.e. Decimal Calculator. Maybe because Java calls it
BigDecimalInteger, and that name was rejected by the PHP community
because it was Not Invented Here? Anyway, I wrote a test of it:
<http://rem.intarweb.org/test1.php> (Click on the source link to
have it show its own source.) It seems to work!! Thanks much!!
That's one less major package I'll need to write myself 1 out of 4
total. Now I need to find the PHP/MySQL stuff I was doing a year or
two ago and remind myself how I did it, and write a generic
SGML/XML->DOM parser the way I want it done, and teach myself how
to do TCP sockets from CMUCL, and then I'll have the pieces needed
to start serious work on NewEco:
<http://TinyURL.Com/NewEco> #lowurg
<http://www.rawbw.com/~rem/Pub/EcoWeb/newInterNetCooperative.html#lowurg>
It'll be a true distributed system, with gateway/spamProtection
written in PHP (running on machine in the UK), communicating with
main application written in Common Lisp (running on machine in
California) over public-key-secure channel, with each talking (PKSC
again) to a simple PHP/MySQL utility for user accounts and
datastore (possibly with backup via MySQL databases in multiple
locations).

Note that I'm a novice at PHP, but not absolute beginner any more.
It was only a few days ago when I got to the point where I felt
"comfortable" programming straight-out in PHP, after becoming
comfortable with Lisp about 35 years ago and with Java about four
years ago.
(Before Lisp, and between Lisp and Java, I got comfortable with
several other programming languages, but I haven't used Fortran
or SAIL or MacSyma or assembly language in 1620/360/6502/8080/68000
for many years, so I no longer count them as "currently comfortable".)
See twitter.com/CalRobert, back a few days, for the moment when I
formally announced my comfort in PHP.

Robert Maas, http://tinyurl.com/uh3t

unread,
Jul 29, 2010, 6:57:10 PM7/29/10
to
> > Does anybody know of a PHP library that emulates bigIntegers in
> > order to perform modular arithmetic (such as multiplication and
> > exponentiation) on them?
> BC which is part of the std PHP distribution?
> http://uk2.php.net/manual/en/intro.bc.php

php -a
<?php
$bigval = "0";
$v1 = bcmul("256",$bigval,0);
PHP Fatal error: Call to undefined function bcmul() ...

php --version
PHP 5.2.6 with Suhosin-Patch 0.9.6.2 (cli) (built: Oct 24 2008 22:29:11)
Copyright (c) 1997-2008 The PHP Group
Zend Engine v2.2.0, Copyright (c) 1998-2008 Zend Technologies

So how can I make BC available within PHP 5.2.6?
Or what alternative way is there to perform big-integer arithmetic in PHP?

Erwin Moller

unread,
Jul 30, 2010, 5:42:55 AM7/30/10
to
Robert Maas, http://tinyurl.com/uh3t schreef:

Hi,

You mentioned:
http://uk2.php.net/manual/en/intro.bc.php

if you click on 'installation' you will see on this page:
http://uk2.php.net/manual/en/bc.installation.php

*************************************************
Installation

These functions are only available if PHP was configured with
--enable-bcmath.

The Windows version of PHP has built-in support for this extension. You
do not need to load any additional extensions in order to use these
functions.
*************************************************

So I think the conclusion is that your version
(PHP 5.2.6 with Suhosin-Patch 0.9.6.2 (cli) (built: Oct 24 2008 22:29:11) )
wasn't compiled with the config option --enable-bcmath

Solution?
Compile it again yourself WITH that option.
Or download a version that was compiled with bc enabled.

Robert Maas, http://tinyurl.com/uh3t

unread,
Jul 30, 2010, 7:41:38 PM7/30/10
to
> > php -a
> > <?php
> > $bigval = "0";
> > $v1 = bcmul("256",$bigval,0);
> > PHP Fatal error: Call to undefined function bcmul() ...
> >
> > php --version
> > PHP 5.2.6 with Suhosin-Patch 0.9.6.2 (cli) (built: Oct 24 2008 22:29:11)
> > Copyright (c) 1997-2008 The PHP Group
> > Zend Engine v2.2.0, Copyright (c) 1998-2008 Zend Technologies
> >
> > So how can I make BC available within PHP 5.2.6?
> > Or what alternative way is there to perform big-integer arithmetic in PHP?
> From: Erwin Moller <Since_humans_read_this_I_am_spammed_too_m...@spamyourself.com>

> You mentioned:
> http://uk2.php.net/manual/en/intro.bc.php
> if you click on 'installation' you will see on this page:
> http://uk2.php.net/manual/en/bc.installation.php
> These functions are only available if PHP was configured with
> --enable-bcmath.
> So I think the conclusion is that your version
> (PHP 5.2.6 with Suhosin-Patch 0.9.6.2 (cli) (built: Oct 24 2008 22:29:11) )
> wasn't compiled with the config option --enable-bcmath
> Solution?
> Compile it again yourself WITH that option.
> Or download a version that was compiled with bc enabled.

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:

<?php
echo function_exists("bcmul")+0,"\n";
?>

http://www.rawbw.com/~rem/MySQL/trybc.php
=> prints 0 i.e. function not defined there either.

http://www.rawbw.com/~rem/HelloPlus/phpinfo.php
=> 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:
http://calrobert.netii.net/trybc.php
=> prints 1, i.e. presumably bcmath is installed there.
http://calrobert.netii.net/phpinfo.php
=> Configure Command './configure' ... '--enable-bcmath' ...

Quick check of my backup/debug hosting sites:
http://calrobert.hostaim.com/phpinfo.php
=> Configure Command './configure' ... '--enable-bcmath' ...
http://calrobert.blackapplehost.com/phpinfo.php
=> 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?

Robert Maas, http://tinyurl.com/uh3t

unread,
Aug 1, 2010, 6:57:09 PM8/1/10
to
(Snipped remarks about tick-sub-processing a different version of
PHP or Lisp from inside the non-BCMATH HTTP PHP server.)

> 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!!

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).

Jerry Stuckle

unread,
Aug 1, 2010, 7:19:11 PM8/1/10
to

Wow. Talk about inefficient...

--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
jstu...@attglobal.net
==================

Peter H. Coffin

unread,
Aug 1, 2010, 8:25:03 PM8/1/10
to
On Sun, 01 Aug 2010 15:19:11 -0400, Jerry Stuckle wrote:
> Robert Maas, http://tinyurl.com/uh3t wrote:
>> 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).
>
> Wow. Talk about inefficient...

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

Jerry Stuckle

unread,
Aug 1, 2010, 8:31:46 PM8/1/10
to
Peter H. Coffin wrote:
> On Sun, 01 Aug 2010 15:19:11 -0400, Jerry Stuckle wrote:
>> Robert Maas, http://tinyurl.com/uh3t wrote:
>>> 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).
>> Wow. Talk about inefficient...
>
> 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."
>

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

I really don't think that was the point.

Robert Maas, http://tinyurl.com/uh3t

unread,
Aug 2, 2010, 9:05:26 PM8/2/10
to
> > 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).
> From: Jerry Stuckle <jstuck...@attglobal.net>
> Wow. Talk about inefficient...

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
decades.

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?

Robert Maas, http://tinyurl.com/uh3t

unread,
Aug 3, 2010, 3:40:21 AM8/3/10
to
> From: "Peter H. Coffin" <hell...@ninehells.com>

> >> 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).
> > Wow. Talk about inefficient...
> 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."

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.

> I will not design my Main Control Room so that every workstation
> is facing away from the door.

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

Robert Maas, http://tinyurl.com/uh3t

unread,
Aug 3, 2010, 3:51:57 AM8/3/10
to
> From: Jerry Stuckle <jstuck...@attglobal.net>

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

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
in PHP/MySQL?

0 new messages