At 11:24 03.08.2000 -0400, Jesse Welton wrote:
>Wouter Gazendam had written:
> > (855 raisedTo: 2753) \\ 3233
> >
> > Any ideas how to speed this up?
>
>Sure.  I believe even with the LargeIntegers plugin, you can greatly
>improve the speed of such calculations by using a specialized
>exponentiation routine that performs all calculations within the given
>modulus.  I just whipped this up, and I think it's correct, but be
>warned that it may have faults.  Method Integer>>raisedTo:modulo:
>
>raisedTo: exponent modulo: modulus
>[snip]
>On my 2.8beta system, I get these times:
>
>[100 timesRepeat: [(855 raisedTo: 2753) \\ 3233]] timeToRun    --> 5995
>[100 timesRepeat: [855 raisedTo: 2753 modulo: 3233]] timeToRun --> 12

Excellent!  And there's also DigitalSignatureAlgorithm>>raise:to:mod: 
already in the image. To make it work for SmallIntegers, one has to promote 
the \\\ method from LargePositiveInteger to Integer (no harm done 
AFAICT).  Then:

[100 timesRepeat: [(855 raisedTo: 2753) \\ 3233]] timeToRun --> 9944
[100 timesRepeat: [855 raisedTo: 2753 modulo: 3233]] timeToRun --> 20
[100 timesRepeat: [DigitalSignatureAlgorithm new raise: 855 to: 2753 mod: 
3233]] timeToRun --> 90

Great, three ways to skin the cat.  Now for the real, large integers:

DigitalSignatureAlgorithm timeDecode: 20  -->
20  verify msgLen = 18 took 5,548 ms
20  verify msgLen = 27 took 5,548 ms
20  verify msgLen = 117 took 5,618 ms
20  verify msgLen = 1017 took 5,708 ms
20  verify msgLen = 10017 took 5,698 ms
20  verify msgLen = 100017 took 6,730 ms

Quickly replaced all sends of #raise:to:mod: with #raisedTo:modulo:

DigitalSignatureAlgorithm timeDecode: 20  -->
20  verify msgLen = 18 took 8,863 ms
20  verify msgLen = 27 took 9,043 ms
20  verify msgLen = 117 took 8,773 ms
20  verify msgLen = 1017 took 9,053 ms
20  verify msgLen = 10017 took 9,213 ms
20  verify msgLen = 100017 took 9,974 ms

This is not what I expected.  I'd have to examine the algorithms more 
closely, but maybe RAA or JM know what's going on.  (I thought that, given 
the LI plugin, we might drop the special-case LI arithmetic in DSA, but the 
simple replacement does not seem desirable.)

Wondering,
Helge