factoring

[Sesquipedalian]

Is there a way to find the factors of a number with PHP? Like if you are given the number 6 it comes back with 1, 2, 3, 6.

 

The only way I can think of is by just checking to see if the number can be divided by numbers 1-100 without a remainder (using modulus), and if there is no remainder, the number is a factor. This seems somewhat tedious though. Is there an easier way?

[corbin]

You could apply some...  shortcuts on large numbers (although on small numbers, since strings would have to be parsed oddly, simple loops could be faster).  http://mathforum.org/k12/mathtips/division.tips.html  For example.

 

 

 

Also, since factors of a number are in practice a*b = c, where a and b are integers, and c is the original number, you only have to check up until the square root of c before you get repeats (well not repeats, but pairs).

 

 

For example, 100.  Factors, 1, 2, 4, 5, 10, 20, 25, 50, 100.

 

1 goes with 100,

2 goes with 50,

4 goes with 25,

10 goes with its self.

 

 

See what I mean?

 

All you have to do is find the factors less than the square root of c, and then divide c by the factors < the sqrt© and get the other half.

 

 

 

 

That can save some loop time.

 

 

Besides that, I can't think of any ninja shortcuts.

 

If you're continually processing large numbers, keeping a prime table could help, since primes are essentially the base factor of all factors.

 

For example:

2, 3, 5, 7

 

(Primes less than the sqrt(100)).

 

 

100 % 2 = 0

(2 is a factor)

100 / 2 = 50

50 % 2 = 0

(so you know 2*2 is a factor)

50 / 2 = 25

25 % 2 = 1

2 line ends here

 

100 % 3 = 1

 

100 % 5 = 0

(5 is a factor)

100 / 5 = 20

20 % 5 = 0

(5*5 is a factor)

20 / 5 = 4

4 % 5 = 4

5 line ends here

 

100 % 7 = 2

7 line ends here.

 

 

 

Wow, I just realized that that approach may have a flaw.  Numbers can be composed of more than 1 prime, such as 10, which is 2*5, so you would have to check each quotient as being divisible as all of the primes less than the divisor.

 

 

Gay.  That approach sucks.  Never mind.  lol

[Jeremysr]

The only real optimization is that you only have to loop through the numbers 1 to the square root of the number you are factoring. If there was an easier way, many encryption algorithms would be broken since they depend on the fact that it is impossible for a computer to factor huge numbers in a short time.

 

Here is a factoring function I wrote:

 

function factor($x) {
$factors = array();
$sqrt = sqrt($x);

for ($i = 1; $i <= $sqrt; $i++) {
	if ($x % $i == 0) {
		array_push($factors, $i);
		array_push($factors, $x / $i);
	}
}

$factors = array_unique($factors);
sort($factors);

return $factors;
}

[.josh]

Really? I mean, I admit that I don't really know a whole lot about encryption algorithms, but it seems logical to me for them not to rely on factoring large numbers, as that can be easily circumvented with rainbow tables... perhaps you are confusing factors with number of possibilities through factorials?  I could be totally talking out my ass, so feel free to correct me.

[Jeremysr]

Really? I mean, I admit that I don't really know a whole lot about encryption algorithms, but it seems logical to me for them not to rely on factoring large numbers, as that can be easily circumvented with rainbow tables... perhaps you are confusing factors with number of possibilities through factorials?  I could be totally talking out my ass, so feel free to correct me.

 

I don't know too much either, but I know that it involves choosing two very large prime numbers and multiplying them together to get a very huge number. This very huge number will only have two factors, since the two numbers chosen were prime. Then something is done (mathematically) to the two factors to create a private and public key.

 

These numbers are so huge that it would take billions of years for all the computers in the world to factor the number. (Or something like that... you get the idea.)

 

I think the RSA algorithm is what I've been describing so you can learn more at that link.

[corbin]

Wow....

 

I never knew that.  Makes sense I guess....