From A student: After looking at all the info I could get about NFS, I still have some questions that are unsolved:
First of all: If someone found an algorithm that has a worst case running time of N*Log(N) to factor an integer n into his divisors, would it be quicker or slower then the number field sieve algorithm?
secondly, what exactly is the time complexity of the Number Field Sieve algorithm, if I would factor an integer n? Answered by Claude Tardif.
I'm having trouble factoring expressions that aren't monic. I can do things like
x2-9x+8, but problems like 12x2+5x-3 have me stumped.
I also have a question about factoring out common factors. In a problem like
x2-18x+81, wouldn't you divide by 9? But what happens to the x2, is it x2/9?