space complexity of common algorithms?

[ixfd64]

Does anyone know the space complexity of the following algorithms?

• Lucas-Lehmer test
• Pollard's rho
• GNFS
• SNFS
• Quadratic sieve

Thanks.

I can only seem to find the time complexity for those equations, but not space.

I *think* that the space complexity of the quadratic sieve is very similar to that of its time complexity, but I could be wrong.

[xilman]

Originally Posted by ixfd64

Does anyone know the space complexity of the following algorithms?

• Lucas-Lehmer test
• Pollard's rho
• GNFS
• SNFS
• Quadratic sieve

Thanks.

I can only seem to find the time complexity for those equations, but not space.

I *think* that the space complexity of the quadratic sieve is very similar to that of its time complexity, but I could be wrong.

L-L and rho are linear A constant number of values, each of size linear in the number of bits in the integer being tested/factored, is used for each algorithm.

The other 3 each have space complexity the same as their time complexity --- L(1/2) for QS and L(1/3) for NFS.


Paul

[ixfd64]

Thanks for the reply. I did expect similar values for the algorithms in question, but I wanted verification from someone with much more knowledge on this subject. :)

- Danny

edit: I added the information to Wikipedia (QS, GNFS, SNFS) and the GIMPS wiki (QS). If I added any inaccurate information, please let me know! :)

[R.D. Silverman]

Originally Posted by xilman

L-L and rho are linear A constant number of values, each of size linear in the number of bits in the integer being tested/factored, is used for each algorithm.

The other 3 each have space complexity the same as their time complexity --- L(1/2) for QS and L(1/3) for NFS.


Paul

Uh, no. The space requirements grow with the square root of the time for
the latter three algorithms.

[xilman]

Originally Posted by R.D. Silverman

Uh, no. The space requirements grow with the square root of the time for the latter three algorithms.

Oops!

I'm trying to work out why I should have made such a silly mistake, other than by postulating incipient Alzheimer's.

The best I can come up with is that the sieving and matrix phases each take equal time (asymptotically) and that for some bizarre reason I forgot that the best available matrix solving algorithms take time proportional to the square of the matrix dimensions (again, asymptotically).


Paul