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 by a number between and . It is always a worst case since any number can be picked.
- Fermat's factorization algorithm : note that if you set with and , then it becomes or . It becomes clear that the nearer a prime factor is from the square root of , 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 , and try divisions by increasing by each time. The worst case will be if . 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.
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 because in , there are two prime factors only, and in , there are three, so you have a bit more chance of finding the right number.
In trial division, you are looking for , with . It is necessary that , thus.
Basically, you just pick random numbers between and , until you fall on a number that divides . At this moment, you know you found , and you can find easily.
Many places tell me that with distinct primes and near to
is the worst case in terms of arithmetic operations needed to factor completely.
Why is this?
If the two prime factors are both near to ,
. . 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: .
. . That is: . . . . There!
We found the factors, but it took us 230 divisions to find it.