What information about the factors of a big number can be gained in a couple of minutes?

Question

Given a number with some hundreds of decimal figures, it's possible to check

• if it is a prime number
• if there are small factors
• if there are factors close to the square root.

But what else? Are there other information, relevant for factoring, that can be obtained fast with a personal computer?

Answer 1

If the number is not too big, the best current known algorithm is the quadratic sieve. Numbers upto about $120$ digits can be factored this way (With some more effort upto about $150$ digits).

To find factors upto about $30-40$ digits, the elliptic curve method (ECM) is best and does not depend on the size of the number.

In rare cases, the $p-1$-method gives large factors.

Primality checking can be done much more efficient. Very good tests include the Miller-Rabin and the BPSW-test. If we want to prove the primality , this is also routine upto about $1\ 000$ digits.