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
|