Large integers

Jesse Welton jwelton at pacific.mps.ohio-state.edu
Thu Aug 3 15:24:20 UTC 2000


Wouter Gazendam wrote:
> 
> Hi All,
> 
> I'm trying to build a RSA implementation in Squeak, and I came across the
> following problem:
> RSA works with incredibly large numbers (sometimes up to 10^1000),
> PrintIt-ing the next line takes about 8 secs to run:
> 
> (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

    | e e2 er product products |

    exponent isInteger ifFalse:
        [self error: 'exponent must be an integer'].
    exponent strictlyPositive ifFalse:
        [self error: 'exponent must be strictly positive'].

    product := self.
    products := OrderedCollection new.
    e := 1.
    [ e2 := e*2. e2 <= exponent ] whileTrue: [
        products addLast: product.
        product := product*product \\ modulus.
        e := e2. ].
    er := exponent - e.
    [ er > 0 ] whileTrue: [
        e := e/2.
        (e <= er)
            ifTrue: [
                er := er - e.
                product := product*(products removeLast) \\ modulus. ]
            ifFalse: [ products removeLast ].
        ].
    ^product


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


-Jesse





More information about the Squeak-dev mailing list