123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132 |
- #!/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]
|