number_factor — Factors a number.
result = number_factor ( n ) [ result , status ] = number_factor ( n ) [ result , status ] = number_factor ( n , method ) [ result , status ] = number_factor ( n , method , imax ) [ result , status ] = number_factor ( n , method , imax , verbose ) [ result , status ] = number_factor ( n , method , imax , verbose , pollardseeds )
a 1x1 matrix of floating point integers
a 1x1 matrix of strings, the method to use (default "fasttrialdivision"). Available are method = "fasttrialdivision", "trialdivision", "memorylesstd", "fermat", "pollard-rho".
a 1-by-1 matrix of floating point integers, the number of steps in the loop (default imax=10000)
a 1-by-1 matrix of booleans, set to true to display messages (default verbose=%f)
a m-by-1 matrix of floating point integers, the seeds for Pollard's rho. Only for method="pollard-rho". Default pollardseeds = [-3 1 3 5].
a row matrix containing the divisors
%t if the factorization is a sucecss, %f if the factorization is a failure
Returns the prime factors of n, as a row matrix. If n=0, 1, 2 or 3, then returns result=n and status = %t.
In case of success, all factors are returned in the result row matrix, and success = %t.
In case of failure, if there is one output argument, an error is generated. In case of failure, if there are two output arguments, success = %f and the factor which were found are returned in result. This feature allows to retrieve the factors which could be found (partial success), even if, globally, the algorithm failed.
Any input argument equal to the empty matrix is replaced by its default value.
The list of available methods is the following.
Uses the Trial Division method, which is known as the simplest, and the least efficient method. This is Algorithm A, "Factoring by division", section 4.5.4 in Knuth's TAO.
Uses a vectorized trial division algorithm.
Uses an array with size sqrt(n)
,
which implies that
it may fail for large integers.
This implementation is due to F. Belahcene.
Uses the Trial Division method, without any list of primes. This is Algorithm A, "Factoring by division", section 4.5.4 in Knuth's TAO. We divide by prime until the remainder is not zero. The following primes are tested in order: 2 3 5 7 11 13 17 ... After the prime p=5 has been used, we add 2, then 4, then 2, ...
Uses the Fermat's method, without sieve.
Uses the Pollard-rho method with the collection of offsets
associated with the "-pollardoffsets" option.
The c
integers in the "-pollardoffsets"
are all used ( in order ) in the pseudo-random number generator
x^2-c
.
This algorithm uses the grand function to generate random integers (option "uin").
With Pollard's rho method, failure is obtained either when the number is prime or composite (i.e. failure is not a mark for primality or compositeness, it is just a failure). In that case, running the algorithm again, one or more time, may produce additionnal factors.
number_factor ( 2^2-1 ) // 3 number_factor ( 2^3-1 ) // 7 number_factor ( 2^4-1 ) // [3 5] number_factor ( 2^5-1 ) // 31 // With a negative integer n to factor, the first factor is negative. number_factor ( -12 ) // [-2 2 3] // A difficult number of fasttrialdivision stacksize("max"); number_factor ( 2^42-1 , "fasttrialdivision" ) // Two loops are not sufficient: an error is generated number_factor ( 2^42-1 , "fasttrialdivision" , 2 ) // Two loops are not sufficient: the status is false (and not error is generated) [result,status]=number_factor ( 2^42-1 , "fasttrialdivision" , 2 ) // See the details of the steps number_factor ( 2^42-1 , "fasttrialdivision" , [] , %t ) // // Use various seeds for Pollard's rho. // This succeeds grand("setsd",0); [result,status] = number_factor(2^20-1,"pollard-rho",[],[],[1 3 5]) // This fails grand("setsd",0); [result,status] = number_factor(2^20-1,"pollard-rho",[],[],-1); // Factor Mersenne numbers algos = [ "fasttrialdivision" "trialdivision" "memorylesstd" "fermat" "pollard-rho" ]; for n = [2^7-1 2^8-1 2^9-1 2^11-1 2^12-1 2^13-1 2^14-1 2^15-1] mprintf("n=%d :\n",n); for method = algos' f = number_factor(n,method); mprintf(" %20s : %s\n",method,sci2exp(f)); end end