123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960 |
- #!/usr/bin/ruby
- # Daniel "Trizen" Șuteu
- # Date: 07 January 2020
- # https://github.com/trizen
- # A simple factorization method, using the Lucas `U_n(P,Q)` sequences.
- # Inspired by the Miller-Rabin factorization method.
- # Works best on Lucas pseudoprimes.
- # See also:
- # https://en.wikipedia.org/wiki/Lucas_pseudoprime
- # https://en.wikipedia.org/wiki/Miller-Rabin_primality_test
- func lucas_miller_factor(n, j=1, k=100) {
- var D = n+j
- var s = D.valuation(2)
- var r = s-1
- var d = D>>s
- for (1..k) {
- var P = min(irand(1, 1e6), irand(1, n-1))
- var Q = min(irand(1, 1e6), irand(1, n-1))*[1,-1].rand
- next if is_square(P*P - 4*Q)
- var T = powmod(Q, d, n)
- var (U,V) = lucasUVmod(P, Q, d, n)
- for b in (0..r) {
- for g in (gcd(U,n), gcd(V,n), gcd(V-P,n)) {
- if (g.is_between(2, n-1)) {
- return g
- }
- }
- U = mulmod(U, V, n)
- V = mulmod(V, V, n)
- V = submod(V, 2*T, n)
- T = mulmod(T, T, n)
- }
- }
- return 1
- }
- say lucas_miller_factor(16641689036184776955112478816668559)
- say lucas_miller_factor(17350074279723825442829581112345759)
- say lucas_miller_factor(61881629277526932459093227009982733523969186747)
- say lucas_miller_factor(122738580838512721992324860157572874494433031849, -1)
- say lucas_miller_factor(181490268975016506576033519670430436718066889008242598463521)
- say lucas_miller_factor(173315617708997561998574166143524347111328490824959334367069087)
- say lucas_miller_factor(57981220983721718930050466285761618141354457135475808219583649146881)
- say lucas_miller_factor(2425361208749736840354501506901183117777758034612345610725789878400467)
- say lucas_miller_factor(131754870930495356465893439278330079857810087607720627102926770417203664110488210785830750894645370240615968198960237761)
|