Name

number_factor — Factors a number.

Calling Sequence

   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 )
   
   

Parameters

n :

a 1x1 matrix of floating point integers

method :

a 1x1 matrix of strings, the method to use (default "fasttrialdivision"). Available are method = "fasttrialdivision", "trialdivision", "memorylesstd", "fermat", "pollard-rho".

imax :

a 1-by-1 matrix of floating point integers, the number of steps in the loop (default imax=10000)

verbose :

a 1-by-1 matrix of booleans, set to true to display messages (default verbose=%f)

pollardseeds :

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].

result :

a row matrix containing the divisors

status :

%t if the factorization is a sucecss, %f if the factorization is a failure

Description

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.

method="trialdivision"

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.

method="fasttrialdivision"

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.

method="memorylesstd"

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, ...

method="fermat"

Uses the Fermat's method, without sieve.

method="pollard-rho"

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.

Examples

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

   

Bibliography

"The Art of Computer Programming", Volume 2, Seminumerical Algorithms, Donald Knuth, Addison-Wesley

Authors

Copyright (C) 2009 - 2010 - DIGITEO - Michael Baudin
Copyright (C) INRIA - Farid BELAHCENE