Project Nayuki


Factorize Gaussian integer (JavaScript)

Program

Factorization:  

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| < 226. 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 code is available for viewing.

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

List of all Gaussian primes up to norm 1000 (with symmetries removed): (1 + 1i), (2 + 1i), (3 + 0i), (3 + 2i), (4 + 1i), (5 + 2i), (6 + 1i), (5 + 4i), (7 + 0i), (7 + 2i), (6 + 5i), (8 + 3i), (8 + 5i), (9 + 4i), (10 + 1i), (10 + 3i), (8 + 7i), (11 + 0i), (11 + 4i), (10 + 7i), (11 + 6i), (13 + 2i), (10 + 9i), (12 + 7i), (14 + 1i), (15 + 2i), (13 + 8i), (15 + 4i), (16 + 1i), (13 + 10i), (14 + 9i), (16 + 5i), (17 + 2i), (13 + 12i), (14 + 11i), (16 + 9i), (18 + 5i), (17 + 8i), (19 + 0i), (18 + 7i), (17 + 10i), (19 + 6i), (20 + 1i), (20 + 3i), (15 + 14i), (17 + 12i), (20 + 7i), (21 + 4i), (19 + 10i), (22 + 5i), (20 + 11i), (23 + 0i), (21 + 10i), (19 + 14i), (20 + 13i), (24 + 1i), (23 + 8i), (24 + 5i), (18 + 17i), (19 + 16i), (25 + 4i), (22 + 13i), (25 + 6i), (23 + 12i), (26 + 1i), (26 + 5i), (22 + 15i), (27 + 2i), (26 + 9i), (20 + 19i), (25 + 12i), (22 + 17i), (26 + 11i), (28 + 5i), (25 + 14i), (27 + 10i), (23 + 18i), (29 + 4i), (29 + 6i), (25 + 16i), (23 + 20i), (24 + 19i), (29 + 10i), (28 + 13i), (31 + 0i), (31 + 4i), (31 + 6i).

This list is included for reference because there doesn’t seem to exist a similar list elsewhere on the web. All these primes a + bi are in the first quadrant (i.e. a > 0 and b ≥ 0) and have ab. They are listed in order of ascending norm, then ascending argument. (“Norm” means squared absolute value.)

For each prime, a set of symmetrical primes have been excluded from the list: If z = a + bi is prime, then so are −z, iz, −iz, z (conjugate), −z, iz, −iz, and b + ai (equal to iz). For example, 3 is prime, therefore so are −3, 3i, and −3i. For example, 5 + 2i is prime, therefore so are 5 − 2i, −5 + 2i, −5 − 2i, 2 + 5i, 2 − 5i, −2 + 5i, and −2 − 5i.

More info