Ben Bacarisse said:

Richard Heathfield <rj*@see.sig.invalidwrites:

<snip>

>Knuth demonstrates that this is not *always* the fastest way to

calculate an integer power. He points out, for example, that x**15

requires six multiplications using the binary technique:

a = x * x

b = x * a

c = x * b * b

d = x * c * c

but only five if you do this:

a = x * x * x

b = a * a

c = a * b * b

and that for n=33 the factor method takes more multiplications than

the binary one.

Right. Observing that 33 = 2**k + 1, whereas 15 = 2**k - 1 (where, in

each case, k is some integer), I find myself wondering whether the

binary technique's efficiency is respectively maximal and minimal in

those cases.

[1]

>
>If I understand him correctly, he suggests reducing n to its prime

factors wherever possible - e.g. for n=63 you would do this:

<snip>

I suspect that in all practical situations (cryptography is the one

that I am familiar with) factorising the power is either impractical

or unproductive. In typical Knuth style, one does not end up with a

practical suggestion but one is much better informed!

Well, you might know the power in advance, in which case you can

pre-calculate its factors. Or you might even choose its factors in

advance! For example, if you're doing Diffie-Hellman, you need to raise

a public value by a secret value. You might reasonably choose a secret

value of a * b * c * d * e * f * g * h + i, so that Step 1 of the D-H

looks like this:

k1 = p1 ** (a * b * c * d * e * f * g * h + i) % p2

which would obviously make it very simple to use the factoring method

Knuth is recommending.

In typical Knuth style, one ends up with a practical suggestion if only

one is prepared to think a little. :-)

--

Richard Heathfield

"Usenet is a strange place" - dmr 29/7/1999

http://www.cpax.org.uk
email: rjh at the above domain, - www.