12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849 |
- #!/usr/bin/ruby
- # A new factorization algorithm for semiprimes, by estimating phi(n).
- # The algorithm is called "Phi-Finder" and is due to Kyle Kloster (2010), described in his thesis:
- # Factoring a semiprime n by estimating φ(n)
- func phi_factor(n) {
- return [] if (n <= 1)
- return [n] if n.is_prime
- if (n.is_square) {
- return 2.of(n.isqrt)
- }
- var E = (n - 2*n.isqrt + 1)
- var E0 = powmod(2, -E, n)
- var L = n.ilog2
- var i = 0
- while (E0 & (E0-1) != 0) {
- E0 <<= L
- E0 %= n
- ++i
- }
- var t = (0..L -> first_by {|k| powmod(2, k, n) == E0 })
- var phi = abs(i*L - E - t)
- var q = (n - phi + 1)
- var p = (q + isqrt(q*q - 4*n))>>1
- [n `idiv` p, p]
- }
- for k in (10..25) {
- var n = (random_nbit_prime(k) * random_nbit_prime(k))
- var f = phi_factor(n)
- say "#{n} = #{f.join(' * ')}"
- assert_eq(f.prod, n)
- assert(f.all{.is_prime})
- }
|