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:
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.
Here are some experements you can try using this calculator:
Calculate the square of
11111111111111111111111111111111111111111111111111111
(It doesn't matter exactly how long the string of ones is.)
Can you explain the resulting pattern?
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 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
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.
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.
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
We'd like to hear from you. Please send any problems, suggestions and comments to: reinhold(at)world.std.com.
Copyright © 2000 Arnold G. Reinhold, Cambridge, MA, USA
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