Comment Re:Can someone explain this to me? (Score 1) 192
The first time you encounter the concept of factoring (as per OP's question) is probably not the best time to introduce mathematics requiring groups and rings.
Granted.
And while the GNFS is indeed magnificently superior to naive searching, it is not sufficiently fast to make a significant difference to the cryptographic strength of a system based on the difficulty of finding large factors - hence, I judged it was not worth mentioning.
While the fact remains that you can make the number large enough for it to be impractical even with GNFS, I must disagree that it makes no significant difference. If the only thing we could do was trial division by primes, a 44 digit RSA composite would need at most ~200 quintillion divisions to find the factors. (see http://primes.utm.edu/howmany.shtml, there are ~200 quintillion primes below 10^22) More than sufficient for safe encryption. Even if you could do 1 billion per second, you'd need almost 6400 years to crack it.
But since there's GNFS, a 309 digit (1024 bit) number is currently the standard, and is being phased out.
In any case, you could've said something along the lines of "There are some more efficient ways, but they are still difficult for large numbers." instead of "There are some tricks you can use to speed it up, but that's essentially it."