12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152 |
- #!/usr/bin/ruby
- # Daniel "Trizen" Șuteu
- # Date: 22 December 2017
- # https://github.com/trizen
- # Simple implementation of Fermat's factorization method.
- # See also:
- # https://en.wikipedia.org/wiki/Fermat%27s_factorization_method
- func fermat_factorization(n) {
- # Check for primes and negative numbers
- return [] if (n <= 1)
- return [n] if n.is_prime
- # Check for divisibility by 2
- if (n.is_even) {
- var v = n.valuation(2)
- return (v.of(2) + __FUNC__(n >> v))
- }
- var p = n.isqrt
- var q = (p*p - n)
- while (!q.is_square) {
- q += ((p++ << 1) + 1)
- }
- var s = q.isqrt
- var f1 = (p + s)
- var f2 = (p - s)
- __FUNC__(f1) +
- __FUNC__(f2) -> sort
- }
- for n in ([160587846247027, 5040, 65127835124, 6469693230]) {
- var factors = fermat_factorization(n)
- say "#{factors.join(' * ')} = #{n}"
- assert(factors.all { .is_prime })
- assert_eq(factors.prod, n)
- }
- __END__
- 12672269 * 12672383 = 160587846247027
- 2 * 2 * 2 * 2 * 3 * 3 * 5 * 7 = 5040
- 2 * 2 * 11 * 19 * 6359 * 12251 = 65127835124
- 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 = 6469693230
|