1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768 |
- #!/usr/bin/ruby
- # Author: Trizen
- # Date: 09 May 2022
- # https://github.com/trizen
- # Find the factors of a Gaussian integer.
- # See also:
- # https://www.alpertron.com.ar/GAUSSIAN.HTM
- # https://en.wikipedia.org/wiki/Table_of_Gaussian_integer_factorizations
- func gaussian_factors(Gauss z) {
- var Z = z
- var n = z.norm
- var factors = []
- for p,e in (n.factor_exp) {
- if (p == 2) {
- var t = Gauss(1,1)
- while (z % t == 0) {
- factors << t
- z /= t
- }
- }
- elsif (p % 4 == 3) {
- var t = Gauss(p)
- while (z % t == 0) {
- factors << t
- z /= t
- }
- }
- else {
- for a,b in (sum_of_squares(p)) {
- var t1 = Gauss(a,b)
- var t2 = Gauss(b,a)
- while (z % t1 == 0) {
- factors << t1
- z /= t1
- }
- while (z % t2 == 0) {
- factors << t2
- z /= t2
- }
- }
- }
- }
- if (z != Gauss(1,0)) {
- factors << z
- }
- assert_eq(factors.prod.abs, Z.abs)
- assert_eq(factors.prod.norm, n)
- return factors.sort.run_length
- }
- var z = Gauss(440, -55)
- var factors = gaussian_factors(z)
- say factors #=> [[Gauss(-1, 0), 1], [Gauss(1, 2), 1], [Gauss(2, 1), 2], [Gauss(2, 3), 1], [Gauss(11, 0), 1]]
- say factors.prod_2d {|p,e| p**e } #=> Gauss(440, -55)
|