Dixon 's Factorization Method with implementation | Python 3 implementation of Dixon factorization algo ; Function to find the factors of a number using the Dixon Factorization Algorithm ; Factor base for the given number ; Starting from the ceil of the root of the given number N ; Storing the related squares ; For every number from the square root Till N ; Finding the related squares ; If the two numbers are the related squares , then append them to the array ; For every pair in the array , compute the GCD such that ; If we find a factor other than 1 , then appending it to the final factor array ; Driver Code
from math import sqrt , gcd NEW_LINE import numpy as np NEW_LINE def factor ( n ) : NEW_LINE INDENT base = [ 2 , 3 , 5 , 7 ] NEW_LINE start = int ( sqrt ( n ) ) NEW_LINE pairs = [ ] NEW_LINE for i in range ( start , n ) : NEW_LINE INDENT for j in range ( len ( base ) ) : NEW_LINE INDENT lhs = i ** 2 % n NEW_LINE rhs = base [ j ] ** 2 % n NEW_LINE if ( lhs == rhs ) : NEW_LINE INDENT pairs . append ( [ i , base [ j ] ] ) NEW_LINE DEDENT DEDENT DEDENT new = [ ] NEW_LINE for i in range ( len ( pairs ) ) : NEW_LINE INDENT factor = gcd ( pairs [ i ] [ 0 ] - pairs [ i ] [ 1 ] , n ) NEW_LINE if ( factor != 1 ) : NEW_LINE INDENT new . append ( factor ) NEW_LINE DEDENT DEDENT x = np . array ( new ) NEW_LINE return ( np . unique ( x ) ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT print ( factor ( 23449 ) ) NEW_LINE DEDENT