The Dixon algorithm factorizes an integer.
Factoring: Dixon Algorithm |
Method
The method uses the finding of congruence of squares modulo the integer \(N\). Within it, we use Fermat's factorization method to find a congruence. This is done with a random or pseudo-random values (\(x\)) and matching to:
\(x^{2} \equiv y^{2} \pmod N\)
The method is:
We first pick a random value of \(x\) amd then compute \(z=x^2 \pmod N\). We then test the value of \(z\) for S-smooth (and which are the prime numbers up to a value of S).
Code
An outline of the code used is [code]:
# https://asecuritysite.com/encryption/dixon?Length=10 from math import gcd import sys def test_pair(a_pair, n, p_list): n1, n2 = a_pair result = True n1_padded = padded_possible(n1 * n1 % n, p_list) n2_padded = padded_possible(n2 * n2 % n, p_list) for i in range(len(p_list)): if (n1_padded[i][1] + n2_padded[i][1]) & 1: result = False break return result def is_possible(n, p_list): result = False for a_prime in p_list: d, r = divmod(n, a_prime) while r == 0: if d == 1: result = True break n = d d, r = divmod(n, a_prime) if result == True: break return result def get_factors(a_pair, n, p_list): n1, n2 = a_pair d1 = n1 * n2 % n n1_padded = padded_possible(n1 * n1 % n, p_list) n2_padded = padded_possible(n2 * n2 % n, p_list) comb = [(n1_padded[i][0], (n1_padded[i][1] + n2_padded[i][1]) // 2) for i in range(len(p_list))] d2 = 1 for a_pair_2 in comb: d2 *= a_pair_2[0]**a_pair_2[1] f1 = gcd(d1 + d2, n) f2 = n // f1 return f1, f2 def padded_possible(n, p_list): result = [] for a_prime in p_list: count = 0 d, r = divmod(n, a_prime) while r == 0: count += 1 n = d d, r = divmod(n, a_prime) result.append((a_prime, count)) return result def dixon_algorithm(n, starting_number, count): p_list, possibles, test_num, i = (2, 3, 5, 7), [], starting_number, 0 while i < count: temp = (test_num * test_num) % n if is_possible(temp, p_list): possibles.append(test_num) i += 1 test_num += 1 pairs = [(possibles[i], possibles[j]) for i in range(1, count) for j in range(i)] goods = [a_pair for a_pair in pairs if test_pair(a_pair, n, p_list)] goods_keepers =[a_good for a_good in goods if get_factors(a_good, n, p_list)[0] != 1 and get_factors(a_good, n, p_list)[0] != n] if len(goods_keepers) == 0: result = 'No solution' else: result = get_factors(goods_keepers[0], n, p_list) return result val=999 if (len(sys.argv)>1): val=int(sys.argv[1]) print ("Val=",val," Factors: ",dixon_algorithm(val,2,4))