123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384 |
- #!/usr/bin/perl
- # Daniel "Trizen" Șuteu
- # Date: 01 June 2022
- # https://github.com/trizen
- # Concept for an integer factorization method based on the Chinese Remainder Theorem (CRT).
- # Example:
- # n = 43*97
- # We have:
- # n == 1 mod 2
- # n == 1 mod 3
- # n == 1 mod 5
- # n == 6 mod 7
- # n == 2 mod 11
- # 43 = chinese(Mod(1,2), Mod(1,3), Mod(3,5), Mod(1,7))
- # 97 = chinese(Mod(1,2), Mod(1,3), Mod(2,5), Mod(6,7))
- # For some small primes p, we try to find pairs of a and b, such that:
- # a*b == n mod p
- # Then using either the `a` or the `b` values, we can construct a factor of n, using the CRT.
- use 5.020;
- use strict;
- use warnings;
- use ntheory qw(:all);
- use experimental qw(signatures);
- use Math::GMPz;
- sub CRT_factor ($n) {
- return $n if is_prime($n);
- my $congruences = [0];
- my $LCM = 1;
- my $limit = vecmin(sqrtint($n), 1e6);
- for (my $p = 2 ; $p <= $limit ; $p = next_prime($p)) {
- my $r = modint($n, $p);
- if ($r == 0) {
- return $p;
- }
- my @new_congruences;
- foreach my $c (@$congruences) {
- foreach my $d (1 .. $p - 1) {
- my $t = [$d, $p];
- my $z = chinese([$c, $LCM], $t);
- my $g = gcd($z, $n);
- if ($g > 1 and $g < $n) {
- return $g;
- }
- push @new_congruences, $z;
- }
- }
- $LCM = lcm($LCM, $p);
- $congruences = \@new_congruences;
- }
- return 1;
- }
- say CRT_factor(43 * 97); #=> 97
- say CRT_factor(503 * 863); #=> 863
- say CRT_factor(Math::GMPz->new(2)**32 + 1); #=> 641
- say CRT_factor(Math::GMPz->new(2)**64 + 1); #=> 274177
- say CRT_factor(Math::GMPz->new("273511610089")); #=> 377827
- say CRT_factor(Math::GMPz->new("24259337155997")); #=> 5944711
|