Many places tell me that n=pq with p,q distinct and near to the square root of n is the worst case in terms or arithmetic operations needed to factorise n completely. Why is this?
There are lots of methods. Here are some :
- Trial division : try to divide $\displaystyle n$ by a number between $\displaystyle 2$ and $\displaystyle \sqrt{n}$. It is always a worst case since any number can be picked.
- Fermat's factorization algorithm : note that if you set $\displaystyle n = pq$ with $\displaystyle p = (a - b)$ and $\displaystyle q = (a + b)$, then it becomes $\displaystyle n = (a - b)(a + b)$ or $\displaystyle n = a^2 - b^2$. It becomes clear that the nearer a prime factor is from the square root of $\displaystyle n$, the easier the algorithm becomes. However, if a prime factor is very small, then this algorithm is possibly the worst ever.
- Linear sieve : start from $\displaystyle p = 2$, and try divisions by increasing $\displaystyle p$ by $\displaystyle 1$ each time. The worst case will be if $\displaystyle p = \sqrt{n}$. That must be your point.
There are lots of better methods, like the quadratic sieve or general number field sieve, but I'm not really good at explaining them so I will let Wikipedia do it
The worst case for factoring semiprimes in terms of arithmetic complexity really depends on the method used.
I was sure I'd put it in there - sorry about that. The method being used is trial division.
So you're saying n=pg with pq close together is the worst case since if you pick numbers randomly to try, you're unlikely to get within that ball park which will give you the right answer?
But then, why does this take longer than n=pqr for instance?
No, in trial division, the worst case is any number, since you are equally likely to pick the right number.
It takes longer than $\displaystyle n = pqr$ because in $\displaystyle n = pq$, there are two prime factors only, and in $\displaystyle n = pqr$, there are three, so you have a bit more chance of finding the right number.
-----------------------
In trial division, you are looking for $\displaystyle q = \frac{n}{p}$, with $\displaystyle p < q$. It is necessary that $\displaystyle p < \sqrt{n}$, thus.
Basically, you just pick random numbers between $\displaystyle 2$ and $\displaystyle \sqrt{n}$, until you fall on a number that divides $\displaystyle n$. At this moment, you know you found $\displaystyle p$, and you can find $\displaystyle q$ easily.
Hello, phillips101!
Many places tell me that $\displaystyle n=pq$ with $\displaystyle p,q$ distinct primes and near to $\displaystyle \sqrt{n}$
is the worst case in terms of arithmetic operations needed to factor $\displaystyle n$ completely.
Why is this?
If the two prime factors are both near to $\displaystyle \sqrt{n}$,
. . then the two factors are almost equal.
This makes our search much longer.
I'll illustrate with an example.
Find the factors of 2,108,303.
So we divide by consecutive primes to look for factors.
We divide by 2, 3, 5, 7, 11, 13, 17, 19, ... and none "come out even".
So we keep trying: 991, 997, 1009, 1013, 1019, 1021, 1031 . . . nope!
By now I'd suspect that the number is prime, but we keep going:
. . divide by 1033, 1039, 1049, 1061, ... 1447 . . . still no luck!
Then we find that: .$\displaystyle 2,\!108,\!303 \div 1451 \:=\:1453$
. . That is: .$\displaystyle 2,\!108,\!303 \;=\;1451\cdot 1453$ . . . There!
We found the factors, but it took us 230 divisions to find it.