Big Number Calculator

Big Number Calculator Applet

by Arnold Reinhold, diceware.com, Rev 0.9

This Applet requires a Java enabled browser (Java version 1.1 or later).

This Java applet looks like an ordinary calculator, but it permits operations with integers of arbitrarily long length, limited only by the memory available to your browser. The calculator uses the BigInteger package that is included in Java release 1.1 and later. It should work fine with most new browsers. We've tested it on IE on Windows XP, MRJ 2.2.3 AppletRunner on the Macintosh under OS 9 and Safari on OS X, Konqurer on Linux. It does not run on the iPhone, which does not support Java at all. Please send reports, good or bad, about what runs on other platforms.

The calculator works just like an ordinary desk calculator. To compute 2+3 you click the 2 button, then the + button, then the 3 button and finally the = button.

There are three display windows. The top window is the X display and shows the final result. The second window is the Y display and shows the value that you are entering. You can also paste numbers into the Y display (but not the X display). In general the calculator uses infix notation for most operations. Enter a number in Y, press an operation (e.g. * or "gcd"), enter another number in Y, then press "=". To do work mod N, enter N in Y , press "=" and then press "setmod". Do a setmod of zero to clear the modulus and work in the group of integers.

The bottom window shows information about the number in the X window, including:

its length in bits
whether or not it is a prime
the number base it is displayed in
the master modulus
the current operation
its value as a decimal floating point number
its tag

The tag is an six character hashcode tag that is displayed for very large numbers. This value is handy when exchanging large values or rechecking calculations. A tag is also show instead of the modulus when the modulus is longer than 9 digits. (The tag vaule is the high order 30 bits of the SHA1 hash of the number, shown in base-32.)

Primality is determined by a probabilistic test that is built into the Java BigInteger package. The likelihood that a number is indicated to be a prime but isn't, is theoretically 2**(-100). Verification of large primes can take a while. You can stop the check by clicking Clear.

When copying and pasting big numbers, make sure you select the entire number, no just the part that is visible in the text window. Your browser's Edit -> Select All command can be handy for this.

Button

Function

!

Calculates the factorial function: 1*2*3*...*n.

xCy

Calculates the binomial coefficient (x y). Read as "x choose y."

x<->y

Exchanges the values of the X and Y-registers.

SetMod

Sets the master modulus. All calculations are performed modulo this number. If the master modulus is set to zero, all calculations are performed as ordinary integers.

SetBase

Sets the base for calculations. Any base between 2 and 36 is permitted. The value of the X-register is converted to the new base. Clicking 0 and then SetBase will restore decimal. So will clicking 10 and then SetBase. Other values entered will be in the current base.

log2, ln, log 10

Computes the logarithm of the absolute value and displays it as a floating point value in the status window. The X-register is set to the integer part of the logarithm. Log2 is base 2, ln is base e=2.71828..., log10 is base 10.

GetMod

Retrieves the current master modulus and places it in the X-register. (Note: If you then press =, the X display will show 0. This is because N = 0 mod N. You can first change the base or press Store to save the modulus.)

SHA1

Caculates a 160-bit hash value using the NIST Secure Hash Algorithm.

+/-

Changes the sign of the X-register.

Set Bit, Clear Bit

Changes the bit position indicated in the Y-register.

Next p

Calculates the next odd prime number. The likelihood that the number selected isn't prime is theoretically 2**(-100).

Random

Calculates a random integer with the number of bits indicated. Random uses Java's SecureRandom class to create a random quantity and this can take half a minute or so to complete the first time it is used.

Rand p

Calculates a random prime number with the number of bits indicated. Rand p uses Java's SecureRandom class to create a random quantity and this process can take half a minute or so to complete the first time it is used. Primality testing is probabilistic. The likelihood that a number selected isn't prime is theoretically 2**(-100).

*

Multiplication (x times y)

x**y

Exponentiation (x to the y power)

gcd

Calculates the greatest common divisor of x and y

1/x

Calculates the multiplicative inverse. This is mostly useful in modular arithmetic. For integer division, the result will be zero if x > 1. The fractional value is shown in the status display.

/

Performs integer division. The fractional value is shown in the status display.

All buttons have a keyboard equivalent.

Known Issues

You can type numbers and operators on your keyboard, however you may have to press Clear (or some other button) first.
Checking for primality on large numbers can take a while if the number is, in fact, prime. This is done every time you press =. You can usually stop the checking by clicking Clear.
Scrolling your browser's display window while the caclulator is running can mess up the display. Scrolling off the calculator and then restoring it will usually fix this.
While the calculator can handle very large numbers, it isn't hard to come up with a calculation that will exceed your computer's memory capacity, or the capacity of any computer that can fit in the known physical universe. Doing this can cause your browser to hang or appear to hang.

Applications

Here are some experements you can try using this calculator:

Number patterns

Calculate the square of 11111111111111111111111111111111111111111111111111111
(It doesn't matter exactly how long the string of ones is.)

Can you explain the resulting pattern?

Verify factoring

RSA Security Inc. periodically issues challenges to see if anyone can break their codes. This involves factoring a large number. One such challenge was recently broken by a team of mathematicians ancd computer scientists. Here is the begining of the team's announcement. You can check their result!

Subject: Factorization of RSA-140 with the Number Field Sieve
From: herman@cwi.nl (Herman J.J. te Riele)
Date: 02/04/1999 04:52 AM Eastern Standard Time
 
On February 2, 1999, we found that
 
RSA-140 =
2129024631825875754749788201627151749780670396327721627823338321538194\
9984056495911366573853021918316783107387995317230889569230873441936471
 
can be written as the product of two 70-digit primes:
 
3398717423028438554530123627613875835633986495969597423490929302771479
*
6264200187401285096151654948264442219302037178623509019111660653946049

Mersenne Primes

Mersenne primes are prime numbers of the form 2**n - 1. There are closely related to "perfect" numbers, which are equal to the sum of their divisors. You can learn more about Mersenne primes at http://www.utm.edu/research/primes/mersenne.shtml

Exchanging Secret Keys

Let's say you want to exchange a secret key with your friend Fran. You might arrange to meet someplace and hand Fran a slip of paper with the key written on it. But suppose meeting is impractical. You could send the key by e-mail, but anyone who intercepts that message could learn the key. Supprisingly, there is a way for you and Fran to exchange a key using insecure e-mail: the Diffie_Helman key exchange protocol. This protocol is easy to cary out using this calculator. Here is how to do it.

Set the calculator to Hexadecimal by pressing 16 and then Set Base.
You and Fran will need to agree on a large prime number, p, at least 1000 bits long. You can use the Rand p key to create one and send it to Fran in an open e-mail (the prime number need not be a secret). Alterntely you can both just use this prime from an Internet IPSec protocol draft: "a4788e2184b8d68bfe02690e4dbe485b17a80bc5f21d680f1a8413139734f7f2b0db4e253750018aad9e86d49b6004bbbcf051f52fcb66d0c5fca63fbfe634173485bbbf7642e9df9c74b85b6855e94213b8c2d89162abeff43424350e96be41edd42de99a6961638c1dac598bc90da069b50c414d8eb8652adcff4a270d567f"The tag for this number is "b58 sp8". (This prime is a "perfect prime" which means that (p-1)/2 is also a prime. You can easily check this on the calculator.)
Paste p into the Y register and press SetMod. Make sure the tag matches.
Pick a 128-bit random number, S, by pressing "128" and then Random.
Save the number S by copying it from the X register and pasting it into a word processing document. This is your secret key.
Compute R = 5**S and send R to Fran. It's a good idea to send her the tag for R as well so she can check if she enters it properly.
Tell Fran to do the same steps. Call her secret key S' and her value from the previous step R'. Fran will send you the value R' and its tag, but she must not send S'.
You compute K = R'**S. Fran will compute K' = R**S'. Both K and K' will be equal if you did everything right.
K will be your joint secret key. For example, you can use the last 16 hex digits of K as a 128-bit key. For extra credit, you both can agree to calculate the SHA1 hash of K first, and use that value as the key.

Calculating Square Roots

BigNumCalc does not have a square root key. I'd suggest you use the Newton-Raphson-Babylonian method: Call your number N. Then starting with a guess, x0, generate a series of approximations x1, x2, ,,, to sqrt(N) as follows:

x[n+1] = (x[n] +N/x[n])/2

For x0, take the decimal floating point aproximation to N displayed in the bottom box and calculate its square root using an ordinary calculator. Then enter it into the BigNumber calculator (to enter say 8.198273964555629E19 you'd enter 819827396455562 and multiply by 10^5).

Since your guess will be quite close, this should converge rapidly (I believe the number of digits of accuracy doubles with each step).

This algorithm only works for ordinary (not modular) arithmetic. If you find a good algorithm for calculating square roots mod p, be sure to let me know.

Source Code

Java source code is availalbe under GPL license, as described below, at:

http://world.std.com/~reinhold/BigNumCalcSource/BNCApplet.java

http://world.std.com/~reinhold/BigNumCalcSource/BigNumCalc.java

Feedback please

We'd like to hear from you. Please send any problems, suggestions and comments to: reinhold(at)world.std.com.

WARRANTY DISCLAMER and Copyright Notice

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version, with two additional restrictions:

1. You may not redistribute versions modified to create "malware," such as versions that deliberately produce inaccurate or misleading results or that surreptitiously capture data entered by the user or that produce random values that are predictable or guessable.

2. You may not redistribute this program in ways that violate the export control laws of the United States.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You can find a copy of the GNU General Public License at http://www.gnu.org/copyleft/gpl.html , or write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

The current version of the program is developmental ("Beta") software and is likely, nay certain, to contain bugs. Please address comments, source requests and bug reports to reinhold@world.std.com