Introduction |
---|

Since there are still JVMs available which come to you with some missing packages or classes (e.g. Netscape on MAC), there was a need for some classes to be coded (again). One of these classes is the java.math.BigInteger.class, which is required for RSA computations.

But it's not enough to implement some kind of a solution, it's a must to compete with existing solutions!

This article compares the own solution to 3 different JVMs.

Design |
---|

The design of the implementation is very simple:

- For performance issues the largest possible word size was chosen: The type int, which allows to handle int overflows with the type long.
- To reduce overhead by copying data, all basic function implementations are using int arrays instead of BigIntegers.
- So BigInteger API functions are often only wrapper functions for the real implementation.
- The implementation should require no other (helper) classes.

Implementation |
---|

This lead to this internal representation:

private int [] data; // data for BigInteger private int len; // used range in data private boolean positive; // sign of current numberTo explain the mathematics with int and long, the next fragment should explain enough: An int value is easily converted into an long by masking it with the long value 0x00000000ffffffffL.

/** * Internal function to perform an addition on big integer arrays. * Pseudeo: res = a + b * @param res int array for the result. This array must be large enough to keep the result (al+1). * @param a int array of first operand. * @param al length of first operand. Regard: al >= bl. * @param b int array of second operand. * @param bl length of second operand. */ private static int add(int [] res, int [] a, int al, int[]b, int bl) { long carry = 0; int i; for(i = 0; i < bl; ++i) { carry += a[i] & 0xffffffffL; carry += b[i] & 0xffffffffL; res[i] = (int)carry; carry >>= 32; } for(; carry != 0 && i < al; ++i) { carry += a[i] & 0xffffffffL; res[i] = (int)carry; carry >>= 32; } if (res != a) for(; i < al; ++i) res[i] = a[i]; if (carry != 0) res[al++] = 1; return al; }Using this technique, all functions were implemented.

Montgomery transformation |
---|

A special focus lies on the modPow function, which uses the Montgomery transformation to increase its speed. Let's regard the basic algorithm of modPow:

given a, e, m => res = a**e mod m res = 1 for b = each bit in e, from highest to lowest bit do res = res * res mod m if b == 1 then res = res * a mod m odMontgomery's basic idea is: Instead of calculating the modulo to m, which can be any number, the input numbers are transformed that m' = 2**n, which makes modulo and division computations very easy and fast, since you either shift right or you omitt leading bits. The normal multiplication is then completed by an reduction algorithm, which also does the back transformation for the result.

given a, e, m => res = a**e mod m res = 1 a' = 2**n * a mod m r' = 2**n * res mod m for b = each bit in e, from highest to lowest bit do r' = montgomery(r' * r') if b == 1 then r' = montgomery(r' * a') od res = montgomery(r')Since the montgomery function is much faster than the previous modulo computation, a big speedup is the reward! For further information have a look to http://security.ece.orst.edu/publications.html

Measurement |
---|

After completion (and some testing) a set of test functions was written to verify the identity of the results and measure the speed of different computations:

- addition
- subtraction
- multiplication
- modulo
- modPow

Copyright (C) Microsoft Corp 1996-2000. Alle Rechte vorbehalten.

Implementation | add | subtract | multiply | mod | modPow | size |
---|---|---|---|---|---|---|

Bebbo's | 90 | 80 | 3535 | 5628 | 7631 | 12209 |

JVM | 301 | 350 | 1202 | 1392 | 1873 | 15013 |

Copyright (C) 1996-99 Symantec Corporation

Implementation | add | subtract | multiply | mod | modPow | size |
---|---|---|---|---|---|---|

Bebbo's | 160 | 150 | 4106 | 6549 | 6660 | 12209 |

JVM | 391 | 491 | 4987 | 6780 | 8312 | 24087 |

Java(TM) 2 Runtime Environment, Standard Edition (build 1.3.0-C)

Java HotSpot(TM) Client VM (build 1.3.0-C, mixed mode)

Copyright © 1995-2000 Sun Microsystems, Inc.

Implementation | add | subtract | multiply | mod | modPow | size |
---|---|---|---|---|---|---|

Bebbo's | 131 | 110 | 6099 | 9043 | 12007 | 12209 |

JVM | 150 | 110 | 6349 | 9023 | 11267 | 37979 |

Explaining the results |
---|

As you notice addition and subtraction are performing at the same speed.
The first surprise is that Microsofts and Symantecs JVM is faster than my implementation at all other operations,
while addition and subtraction - which are much easier to implement - are much slower. The solution: ** Microsoft and Symantec JVM are using native functions!**

The Sun implementation with the Sun JVM performs nearly as fast as my implementation, but its size is 3 times larger.

Conclusion |
---|

- Good native implementations, gain speed by factor 3. (Microsoft native functions)
- Normal native implementations can't compete to Java! (Symantec native functions)
- It's worth to verify the implementations of all big vendors, there is still gain in speed and size.
- The Microsoft JIT and the Symantec JIT are similar in speed. The gap in addition and subtraction is probably based on slower function calls in Symantec.
- The Sun JIT performs about 50% slower than Symantec or Microsoft JIT for the measured functions.

Verify it |
---|

Download the implementation de.bb.math.BigInteger.class and the test program and test it with your JVM. The values used above are for the last pass with 2048 on Windows 2000 with a Duron 650MHZ. For questions and submissions contact the author.

Copyright © 1999/2000 F.Fischell / S. Franke

last update 19.11.2000