1

Essentially what I am asking is if there is some kind of correlation between a number such as √385 and it's factorization (which is 5,7,11).

Is it possible to use a number's (especially very large ones) square root to help in finding out it's prime factorization?

Jessiah Burgess
  • 25
  • 4
  • 1
    One relation I can think of is that if you use the trial division algorithm you need to check until $\sqrt{n}$ – Brian Cheung Jul 15 '15 at 17:14
  • Do you mean, if you knew $\sqrt{385} \doteq 19.6214168703485834685\ldots$ to arbitrary precision, would it help you factor the number? I'm not aware of any result where that helps significantly. (Irrational number approximation theorems may help to some tiny degree.) – Brian Tung Jul 15 '15 at 17:15
  • Fermat's factorization method (https://en.wikipedia.org/wiki/Fermat%27s_factorization_method) starts an iteration process at $\left\lceil \sqrt{n} \right\rceil$ – paw88789 Jul 15 '15 at 17:19
  • If $n=2^{i_1}3^{i_2}5^{i_3}\dots$, then $\sqrt{n}=2^{i_1/2}3^{i_2/2}5^{i_3/2}\dots$ so for large numbers that are square, you can compute the factorisation of its squareroot and then double all exponents. – xavierm02 Jul 15 '15 at 17:45

2 Answers2

2

The relevant fact here is

If $n$ is not prime then $n$ has a prime factor $p$ with $p \le \sqrt n$.

So, if you search for prime factors of $n$ and haven't found one when you reach $\sqrt n$, then you know that $n$ is prime.

If you do find a prime factor $p$, then repeat the process with $n/p$ and so. (You can start at $p$ instead of at $2$.) This will find the prime factorization of $n$.

In your example, since $\sqrt{385} < 20$, you only need to try to factor $385$ with primes less than $20$. The first factor is $5$ and the quotient is $77$. The first factor of $77$ is $7$ and the quotient is $11$. Since $11$ is prime, you're done: $385 = 5 \cdot 7 \cdot 11$.

Joel
  • 16,256
lhf
  • 216,483
1

For a single integer $n > 1$, it's sufficient to iterate in order over the integers $2 \leq k \leq \sqrt{n}$ checking for divisibility. When you find a number that divides $n$, it will be prime (This is trivial to observe). You'd then divide out the instances of that prime from $n$ until it is no longer divisible by it.

This is not a good solution for a large set of integers however.

Computationally speaking, if you're working over a range like $(1, 10^9)$, a sieve is feasible. Not only would you sieve the primes up to $N$, you'd also sieve a sequence of the smallest prime factors for every integer up to $N$, which takes space linear in the value of $N$. The sieve would take $O(N\log\log N)$ time. Factorization would then be a sequence of divisions by the smallest prime factor of $n$ until you reach $1$. This gives you constant time per prime factor for an integer $n$.

Another method that uses sieves to make the first trivial division solution better is to sieve the primes up to the square root of the maximum value in your queries. This way, when performing trial division, you can directly iterate over the primes to check for divisibility.

If you're working over a very sparse set of integers, you'd need more sophisticated algorithms like Pollard's Rho Algorithm. A sieve is more useful when your range is sufficiently small and you want to work with a sufficient part of it.

When I first read your question, I thought of the Fermat Factorization trick. That is, I wasn't sure whether you expected a more computational answer or not. This trick works well with integers that have factors close to their square root.

Consider the integer $8051$ for instance. It's square root is $\approx 90$. It can be rewritten as $8100 - 49$. This is the difference of two squares: $$8100 - 49 = (90 - 7) \times (90 + 7) = 83\times 97$$

Besides naive trial division and this trick, there isn't much you can do with the knowledge of the square root of an integer to get the factorization.

user123
  • 1,202