|
| | IntFactorization (const Int &x) |
| | Integer \(x\) is the number whose "prime" factors decomposition is kept in this object. More...
|
| |
| | IntFactorization (const char *fname=0) |
| | Integer number and its prime factors will be read from file fname by calling method read below. More...
|
| |
| | IntFactorization (const IntFactorization &f) |
| | Copy constructor. More...
|
| |
| | ~IntFactorization () |
| | Destructor. More...
|
| |
| void | addFactor (const Int &p, int mult=1, LatticeTester::PrimeType st=LatticeTester::UNKNOWN) |
| | Adds factor \(p\) with multiplicity mult and prime status st to this object. More...
|
| |
| void | calcInvFactors () |
| | Given the list of prime factors \(p\) of number, fills the list of inverse factors with the values number/ \(p\). More...
|
| |
| bool | checkProduct () const |
| | Checks that the number is equal to the product of its factors. More...
|
| |
| void | clear () |
| | Empties the lists of primes factors and set this number to 0. More...
|
| |
| void | factorize () |
| | Tries to find all the prime factors of this number. More...
|
| |
| const std::list< LatticeTester::IntFactor< Int > > & | getFactorList () const |
| | Returns a non-mutable list of the factors. More...
|
| |
| const std::vector< Int > & | getInvFactorList () const |
| | Returns a non-mutable list of the inverse factors. More...
|
| |
| Int | getNumber () const |
| | Returns the value of this number. More...
|
| |
| LatticeTester::PrimeType | getStatus () const |
| | Returns the status of this number. More...
|
| |
| IntFactorization & | operator= (const IntFactorization &f) |
| | Assignment operator. More...
|
| |
| void | read (const char *f) |
| | Reads the list of (possibly) prime factors of a number from file f. More...
|
| |
| void | setNumber (const Int &x) |
| | Sets the value of this number to \(x\). More...
|
| |
| void | setStatus (LatticeTester::PrimeType s) |
| | Sets the status of this number to \(s\). More...
|
| |
| std::string | toString () const |
| | Returns the list of (possibly) prime factors of this object in the same format as described in method read above. More...
|
| |
| void | unique () |
| | Replaces repeated equal factors in factorList by one factor with its multiplicity. More...
|
| |
template<typename Int>
class LatMRG::IntFactorization< Int >
The class IntFactorization implements the decomposition of integers in factors, preferably prime (see class IntFactor).
It contains functions to factorize an integer in prime factors, to sort and print the list of its factors. IntFactorization Integers are factorized by calling the MIRACL software [34], which uses many different methods in succession to effect the factorization.
Given any natural integer \(n\), there is a unique decomposition in prime factors of the form
\[ n = p_1^{\nu_1}p_2^{\nu_2}\cdots p_s^{\nu_s} \]
where \(p_i\) is a prime integer with \(\nu_i\) its multiplicity, and where the factors are sorted in increasing order. In the case of very large integers, it may not be possible to find all the prime factors within a reasonable amount of time. In that case, a similar decomposition to the above may be used with some of the factors composite.
Reads the list of (possibly) prime factors of a number from file f.
The first line contains the number itself. The following lines contain one factor per line: the factor (first field) with its multiplicity (second field) and its status (third field). The status field is written as P if the factor is known to be prime, Q if the factor is probably prime, C if the factor is composite, and U if its status is unknown or unimportant. For example, given the number \(120= 2^3*3*5\), then the file must be
Given the list of prime factors \(p\) of number, invFactorList contains all the sorted values number/ \(p\) (indexing starts at 0).
However, one must have called the function calcInvFactors beforehand. For example, if number = 24, its prime factors decomposition is \(24 = 2^3\cdot3\), and invfactorList = \([8, 12]\).
1.8.15