15. Factorization {VeryLargeIntegers}

Factorization of vli Objects

Description

factors returns all the prime factors of a given number.

Usage

factors(n, iter = 10, output = "print")

## Default S3 method:
factors(n, iter = 10, output = "print")

## S3 method for class 'numeric'
factors(n, iter = 10, output = "print")

## S3 method for class 'vli'
factors(n, iter = 10, output = "print")

Arguments

n

integer to be factorized; vli class object or 32 bits integer

iter

number of iterations for testing if the given number is prime; numeric

output

chosen way for objects being returned: 'list' to return the result as a list of vli objects or 'print' (by default) to simply display the result on the screen; character

Details

The implemented algorithm is based in a Monte Carlo method for integer factorization called Pollard's Rho Algorithm.

It determines if the given number is prime or composite by usign the Miller-Rabin Probabilistic Primality Test. If it is prime, it returns the number itself. If it is composite, it calls iteratively the divisor function until all the prime factors of the given number are found.

It is a Monte Carlo method, therefore it is not deterministic. The number of iterations is configurable, to set the desired accuracy. A too low number of iterations could cause an infinite loop because of being looking for a divisor of a prime number.

Value

list of objects of class vli or the result displayed on the screen, depending on the output argument

Author(s)

Javier Leiva Cuadrado

Examples

x <- as.vli("584843")
factors(x, iter = 100)