1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071 |
- #!/usr/bin/perl
- # Daniel "Trizen" Șuteu
- # Date: 23 January 2020
- # https://github.com/trizen
- # A simple factorization method, using the Chebyshev T_n(x) polynomials, based on the identity:
- # T_{m n}(x) = T_m(T_n(x))
- # where:
- # T_n(x) = (1/2) * V_n(2x, 1)
- # where V_n(P, Q) is the Lucas V sequence.
- # See also:
- # https://oeis.org/A001075
- # https://en.wikipedia.org/wiki/Lucas_sequence
- # https://en.wikipedia.org/wiki/Iterated_function
- # https://en.wikipedia.org/wiki/Chebyshev_polynomials
- use 5.020;
- use warnings;
- use experimental qw(signatures);
- use ntheory qw(prime_iterator sqrtint primes logint);
- use Math::AnyNum qw(:overload lucasVmod gcd invmod mulmod is_coprime);
- sub chebyshev_factorization ($n, $B = logint($n, 2)**2, $a = 127) {
- my $x = $a;
- my $G = $B * $B;
- my $i = invmod(2, $n);
- my sub chebyshevTmod ($a, $x) {
- mulmod(lucasVmod(2 * $x, 1, $a, $n), $i, $n);
- }
- foreach my $p (@{primes(2, sqrtint($B))}) {
- for (1 .. logint($G, $p)) {
- $x = chebyshevTmod($p, $x); # T_k(x) (mod n)
- }
- }
- my $it = prime_iterator(sqrtint($B) + 1);
- for (my $p = $it->() ; $p <= $B ; $p = $it->()) {
- $x = chebyshevTmod($p, $x); # T_k(x) (mod n)
- is_coprime($x - 1, $n) || return gcd($x - 1, $n);
- }
- return gcd($x - 1, $n);
- }
- say chebyshev_factorization(2**64 + 1, 20); #=> 274177 (p-1 is 20-smooth)
- say chebyshev_factorization(257221 * 470783, 1000); #=> 470783 (p-1 is 1000-smooth)
- say chebyshev_factorization(1124075136413 * 3556516507813, 4000); #=> 1124075136413 (p+1 is 4000-smooth)
- say chebyshev_factorization(7553377229 * 588103349, 800); #=> 7553377229 (p+1 is 800-smooth)
- say '';
- say chebyshev_factorization(333732865481 * 1632480277613, 3000); #=> 333732865481 (p-1 is 3000-smooth)
- say chebyshev_factorization(15597344393 * 12388291753, 3000); #=> 15597344393 (p-1 is 3000-smooth)
- say chebyshev_factorization(43759958467 * 59037829639, 3200); #=> 43759958467 (p+1 is 3200-smooth)
- say chebyshev_factorization(112601635303 * 83979783007, 700); #=> 112601635303 (p-1 is 700-smooth)
- say chebyshev_factorization(228640480273 * 224774973299, 2000); #=> 228640480273 (p-1 is 2000-smooth)
- say '';
- say chebyshev_factorization(5140059121 * 8382882743, 2500); #=> 5140059121 (p-1 is 2500-smooth)
- say chebyshev_factorization(18114813019 * 17402508649, 6000); #=> 18114813019 (p+1 is 6000-smooth)
- say chebyshev_factorization(533091092393 * 440050095029, 300); #=> 533091092393 (p+1 is 300-smooth)
|