12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061 |
- #!/usr/bin/ruby
- # Author: Daniel "Trizen" Șuteu
- # Date: 04 May 2019
- # https://github.com/trizen
- # A simple factorization method, using the binary search algorithm, for numbers of the form:
- #
- # n = x * Prod_{k=1..r} ((x±1)*a_k ± 1)
- #
- # for `r` relatively small.
- # Many Carmichael numbers and Lucas pseudoprimes are of this form and can be factorized relatively fast by this method.
- # See also:
- # https://en.wikipedia.org/wiki/Binary_search_algorithm
- func carmichael_factorization(n, k=3, l=2, h=6) {
- var blocks = [
- {|x,params|
- params.map {|k|
- ((x-1)*k + 1)
- }
- },
- {|x,params|
- params.map {|k|
- ((x+1)*k - 1)
- }
- },
- ]
- @(l..h).combinations(k-1, {|*params|
- for block in blocks {
- var r = bsearch_le(n.iroot(k), {|x| block(x, params).prod*x <=> n })
- var g = gcd(r, n)
- if (g > 1) {
- var f = [r, block(r, params)...].grep { .divides(n) }
- return (f ? f : g)
- }
- }
- })
- return 1
- }
- say carmichael_factorization(7520940423059310542039581, k:3) #=> 79443853
- say carmichael_factorization(570115866940668362539466801338334994649, k:3) #=> 4563211789627
- say carmichael_factorization(8325544586081174440728309072452661246289, k:3) #=> 11153738721817
- say carmichael_factorization(1169586052690021349455126348204184925097724507, k:3, l:11, h:23) #=> 166585508879747
- say carmichael_factorization(61881629277526932459093227009982733523969186747, k:3, l:3, h:11) #=> 1233150073853267
- say carmichael_factorization(173315617708997561998574166143524347111328490824959334367069087, k:3, l:3, h:11) #=> 173823271649325368927
- # Works even with larger numbers
- say carmichael_factorization(131754870930495356465893439278330079857810087607720627102926770417203664110488210785830750894645370240615968198960237761, k:4) #=> 245960883729518060519840003581
|