Enter (or paste) a positive decimal integer into the top text box (the one above the "Is N Prime", "Factor N", and "Is N Safe Prime" buttons). Then push one of the buttons to discover whether it is prime or Safe Prime, factor it, or find the next lower or higher prime or Safe Prime. Keep clicking "Lower" or "Higher" to find additional primes. You can also paste numbers directly into the Prime or Safe Prime text boxes.

FACTOR AND PRIME CALCULATOR CAUTION Calculations with large numbers could take a very long time. To terminate "runaway" processes by force-quitting your browser: Mac: Command-Option-Escape.   Windows: Control-Alt-Delete. Corresponding    Sophie Germain Prime

Sophie Germain Primes
Sophie Germain Primes were named for Marie-Sophie Germain (1776-1831), the famous French woman mathematician, who first did research on them. A Sophie Germain Prime P is a prime for which 2P+1 is also prime.

Safe Primes
A "Safe Prime" is a prime P for which (P-1)/2 is also prime. Note that this means that (P-1)/2 is a Sophie Germain Prime.

Safe Primes are important in cryptography because the modulus of a Diffie-Hellman Key Exchange MUST be a Safe Prime. The modulus of an RSA Public Key Pair MUST be the product of two primes, but some standards require that the modulus for an RSA key pair must be the product of a pair of Safe Primes.

STRONG CAUTIONS:

Due to JavaScript limitations, operation is not reliable with numbers larger than 15 digits. Be patient with large numbers! In particular, it can take quite a while to find the next Safe Prime, as this requires finding lots of primes which are then rejected due to (P-1)/2 not being prime.

If you are going to research primes larger than 12 digits or Safe Primes larger than 10 digits, make sure you know how to "force-quit" your browser, as calculations with large Safe Primes could take longer than you are willing to wait, depending on your browser and computer.

Enjoy!

This page implements a JavaScript that factors numbers that you provide: referred to here as the Dividend. (Remember grade-school math? The Dividend divided by the Divisor is equal to the Quotient.) If the Dividend is prime (has no factors except one and itself), this is noted as the output. Otherwise, the factors are given in the order that they were discovered - that is from smallest to largest. By definition, 1 is not considered prime, and neither is zero. Also, negative and imaginary numbers cannot be prime, and this page strips out all characters other than decimal digits before doing any math. So you can enter Tommy Tutone's (or your) phone number with the hyphens and it will be evaluated as a positive integer.

This page also has JavaScripts that find primes and Safe Primes (primes P where (P-1)/2 is also prime).

The algorithm used here for factoring and prime testing is trial division by two, then by succeeding odd numbers: 3, 5, 7... Each divisor that is found is checked to see whether it might be a multiple factor. For example, 16 has four factors of two.

This is not an efficient algorithm, because it tries to divide by odd numbers that are products of smaller primes. These trial divisors add nothing new because their prime factors have already been tried. The first instance of this is when it tries to divide by 9 (3*3), the next is 15 (3*5). Nevertheless, this algorithm is simple and always works. The speed of modern computers makes the extra complexity of more efficient algorithms not worth while for numbers up to about 15 decimal digits. With integers having more than 15 decimal digits JavaScript itself would need patches to avoid roundoff errors, as most implementations treat numbers as IEEE Double Precision Floating Point. When represented this way only integers up to 2⁵¹ or about 10¹⁵ can be handled without roundoff errors.

When factoring a number, it is only necessary to search factors up to its square root. This is because no number, by definition, can have two factors larger than its square root, and this algorithm finds the smallest ones first.

This is even easier for composite (non-prime) numbers. When a factor is found, the quotient remaining can be either composite or prime, but it cannot have any prime factors smaller than the most recent trial divisor (otherwise they would have already been found). So the same logic as to the largest possible remaining factors can be used on this new quotient, and the limit of the search for factors is reduced to the square root of the newly found quotient. This logic is used iteratively as more factors are found.

Eventually, the trial divisor is larger than the limit for whatever number is being factored at that point. This number is guaranteed to be prime and is output as the last factor.

If the original Dividend were really prime, the limit would be its square root, and would never be reduced, which is why with this particular algorithm it takes a lot longer to prove that a prime number is really prime than to factor a composite number. Primality tests other than trying successive trial divisors do exist, and are stupendously faster when large numbers are involved. For extremely large numbers (hundreds or thousands of digits) it is far easier to find out whether a number is prime than it would be to factor it. That reality is part of the mathematical basis of the "trap door" function used in the RSA system of public key cryptography.

The "Is This Prime?" button is provided because most large composite numbers have at least one small prime factor, and stopping after finding the first factor (at which point you know the number is not prime) can take a lot less time than continuing on to find the large factors.

The simplified function connected with the "Is This Prime?" button is also used by the "Next Lower Prime" and "Next Higher Prime" buttons. The algorithm here begins by checking if the number in the box is even or odd. If even, it starts its search one above or below where it is. If the number is odd, it starts two above or below. Once started, it keeps stepping in the chosen direction by two until it finds a prime. Naturally, this takes a while because you have to search a fairly large number of candidates to find another prime.

Searching for "Safe Primes" requires finding a prime P, then testing whether (P-1)/2 is prime, and moving on if it isn't. Thus finding Safe Primes is much more compute intensive than finding regular primes.

Some academic and government work (some of it secret, apparently) is going on in the area of factoring composite numbers consisting of the product of two large primes. If you could do this easily, you could invalidate the security of cryptographic systems that use the RSA system of Public Keys. Examples include secure web site certificates, and most forms of encrypted EMAIL. Some groups (e.g., the CIA and the Pentagon) would like to have this ability to do this at least for "emergency" purposes, and this apparently fuels research expenditures. Unfortunately for these efforts, factoring large composites is known to be an "NP complete" problem, which means that if you could do this easily, at least in principle, you could solve any mathematical problem easily. Quantum computing offers the possibility of doing this essentially by "brute force".

Another, entirely different, approach to factorization is use of " Quantum Computers".

Stay tuned...

That means that although it is copyrighted, it is intended for you to use for education or entertainment. You may use it yourself, copy and redistribute it, or even put it on your own website. I ask only that you not make any changes. If you reuse any of the code, make sure to list me as one of your sources.

My only reward for writing this is the 15 milliseconds of fame I receive from having my name here. Don't deprive me of that.

You can copy this page by simply doing a "Save As" in your browser and putting it somewhere on your hard drive (or your web site). If you stop there the background will be gone. To preserve the background, copy the following file into this same folder, without changing its name, by again using your browser's "Save As". The next time you refresh the page, the background should be restored: