sidef-scripts/Math/congruence_of_powers_factorization_method.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 05 July 2019
# https://github.com/trizen

# A simple factorization method, based on congruences of powers.

# Given a composite integer `n`, if we find:
#
#   a^k == b^k (mod n)
#
# for some k >= 2, then gcd(a-b, n) may be a non-trivial factor of n.

# See also:
#   https://trizenx.blogspot.com/2019/08/special-purpose-factorization-algorithms.html

define MIN_FACTOR = 1e6  # ignore small factors

func cgpow_factor (n) {

    var params = []
    var orig = n

    var range = (2 .. min(n.ilog2, 15) -> flip)

    func process_congruence(root, e) {
        for j in (-1, 0, 1) {

            var k = (root + j)
            var u = powmod(k, e, n)

            for z in (u, n-u) {
                if (is_power(z)) {
                    var t = perfect_power(z)

                    var r1 = z.iroot(t)
                    var r2 = z.iroot(e)

                    params << [r1, t, k, e]
                    params << [r2, e, k, e]
                }
            }
        }
    }

    range.each {|e|
        var root = n.iroot(e)
        process_congruence(root, e)
    }

    range.each {|root|
        var e = n.ilog(root)
        process_congruence(root, e)
    }

    var f = func (r, e1, k, e2) {

        var factors = Set()

        var d1 = e1.divisors.map {|d| r**d }
        var d2 = e2.divisors.map {|d| k**d }

        for x in (d1), y in (d2) {
            for j in (-1, 1) {

                var t = (x - j*y)
                var g = gcd(t, n)

                if (g>MIN_FACTOR && g<n) {
                    factors << g
                }
            }
        }

        factors.to_a
    }

    var factors = []
    var divisors = params.uniq.map { f(_...) }.flat.sort.uniq

    divisors.each {|d|
        var g = gcd(n, d)

        if (g>MIN_FACTOR && g<n) {
            while (n%g == 0) {
                n /= g
                factors << g
            }
        }
    }

    factors << (orig / factors.prod)
    factors.sort
}

if (ARGV) {
    say cgpow_factor(Num(ARGV[0]))
    return 1
}

say cgpow_factor(ipow(2,  256) - 1)
say cgpow_factor(ipow(10, 120) + 1)
say cgpow_factor(ipow(10, 120) - 1)
say cgpow_factor(ipow(10, 120) - 25)
say cgpow_factor(ipow(10, 105) - 1)
say cgpow_factor(ipow(10, 105) + 1)
say cgpow_factor(ipow(10, 120) - ipow(2134, 2))
say cgpow_factor((ipow(2, 128) - 1) * (ipow(2, 256) - 1))
say cgpow_factor(ipow(ipow(4, 64) - 1, 3) - 1)

say cgpow_factor((2**128 - 1) * (3**128 - 1))
say cgpow_factor((5**48 + 1) * (3**120 + 1))
say cgpow_factor((5**48 + 1) * (3**120 - 1))
say cgpow_factor((5**48 - 1) * (3**120 + 1))
say cgpow_factor((45**120 + 35**420))

__END__
[4294967295, 4294967297, 18446744073709551617, 340282366920938463463374607431768211457]
[100000001, 9999999900000001, 99999999000000009999999900000001, 10000000099999999999999989999999899999999000000000000000100000001]
[1000001, 1202981, 1587789, 2906161, 99009901, 1000000000001, 10989010989011, 165573604901641, 9999000099990001, 100009999999899989999000000010001]
[999999999999999999999999999999999999999999999999999999999995, 1000000000000000000000000000000000000000000000000000000000005]
[1111111, 8392599, 119152601, 900900990991, 900009090090909909099991, 1109988789001111109989898989900111110998878900111]
[1478477, 4734601891, 156985855573, 999990000099999000009999900001, 910009191000909089989898989899909091000919100091]
[999999999999999999999999999999999999999999999999999999997866, 1000000000000000000000000000000000000000000000000000000002134]
[4294836225, 4294967297, 4294967297, 4295098369, 18446744073709551617, 18446744073709551617, 340282366920938463463374607431768211457]
[340282366920938463463374607431768211454, 115792089237316195423570985008687907852929702298719625575994209400481361428481]
[41, 1048560, 1979408, 5570645, 6700417, 43046722, 926510094425921, 18446744073709551617, 1716841910146256242328924544641]
[1273028, 43040161, 76293945313, 1852737802355521, 240031591394168814433, 3434207167913380326433387290241]
[1013824, 1801025, 2828617, 16068403, 47763361, 1743392201, 76293945313, 50446744628921761, 240031591394168814433]
[1889856, 3390842, 43040161, 61132969, 1852737802355521, 59509277587890001, 3434207167913380326433387290241]