Factorize Gaussian integer (JavaScript)

Program

Description

This JavaScript program calculates the prime factorization of the given Gaussian integer. A Gaussian integer is a complex number of the form a + bi, where a and b are integers. This program has a limit of |a|, |b| < 2²⁶. If the number is large, the program may hang for a few seconds.

The factorization is put into the following canonical form:

• If the number is 0, 1, −1, i, or −i, then the factorization is the number itself.

• Otherwise the factorization begins with a factor of −1 or i or −i if necessary. The rest are primes listed in ascending order of absolute value, breaking ties by lowest argument (angle); each of these factors have absolute value > 1 and are in the first quadrant (0 ≤ argument < π/2).

The source TypeScript code and compiled JavaScript code are available for viewing. A Java version of the code is also available.

Examples

• −1 = (−1) (unit)
• 2 = (−i) (1 + i) (1 + i)
• 4 + i = (4 + i) (prime)
• 7 = (7) (prime)
• 5 + 9i = (1 + i) (7 + 2i)

Input format

• The real or imaginary component can be suppressed, and they can be in either order. The 1 can be suppressed for i. For example, all these are valid inputs: -0, 5i, 1+2i, -i-2

• Spaces are allowed anywhere in the Gaussian integer, except within a string of digits.

• To indicate negative numbers, the ASCII hyphen-minus (U+002D) and the minus sign (U+2212) are both acceptable. (The output properly uses the minus sign, though.)

• j is an acceptable synonym for i, for those electrical engineers out there.

List of Gaussian primes

Table of all Gaussian primes up to norm 1000, with symmetries removed:

All the prime numbers in the table above are located in the first octant – a number has the form a + bi and satisfies a > 0, b ≥ 0, and a ≥ b (thus the argument is between 0° and 45°). They are listed in order of ascending norm, with ties broken by ascending argument. (“Norm” means squared absolute value.)

For each prime, a set of up to seven symmetrical primes have been excluded from the list. This is because if z is prime, then so are −z, iz, −iz, z (conjugate), −z, iz, and −iz. In terms of components, if z = a + bi is prime, then respectively so are −a − bi, −b + ai, b − ai, a − bi, −a + bi, b + ai, and −b − ai.

For example, 3 is prime, therefore so are −3, 3i, and −3i. For example, 5 + 2i is prime, therefore so are −5 − 2i, −2 + 5i, 2 − 5i, 5 − 2i, −5 + 2i, 2 + 5i, and −2 − 5i..

More info

• Wikipedia: Table of Gaussian integer factorizations
• Stack Overflow: What’s a nice method to factor Gaussian integers?
• planetmath.org: examples of Gaussian primes