Talk:General number field sieve

From Wikipedia, the free encyclopedia

You have new messages (last change).

[edit] Big-O?

The current article states that the Big-O notation for GNFS is

O\left(\exp\left(\left(\begin{matrix}\frac{64}{9}\end{matrix} n\right)^{1\over3} (\log n)^{2\over3}\right)\right)

However, at this location it states that the Big-O notation is actually

O\left(\exp\left(\left(\begin{matrix}\frac{64}{9}\end{matrix} n\right)^{1\over3} \log (\log n)^{2\over3}\right)\right)

Nicholasink 02:57, 20 November 2006 (UTC)

  • Upon seeing a later comment in this page, I am accordingly modifying the Big-O, as the article clearly is inaccurate. Nicholasink 03:01, 20 November 2006 (UTC)


Not sure about this (deep maths is not a major point for me), but is "nonrational" a word. Would irrational be more correct, or do these two have different meanings?

The effort of the method (sentence 2) seems wrong. I guess that both "n" should be "log n"?! Alternatively, the number should be an n-bit number. Gerd Kunert

In mathematics, irrational is usually synonymous with not rational. But in other fields, nonrational means something different from irrational. A lunatic is irrational, but a snail, lacking the ability to discuss philosophy, etc., is nonrational. Michael Hardy 02:45, 30 Oct 2003 (UTC)

Could we get some examples, please? 4.65.244.206 18:12, 23 Mar 2004 (UTC)~

It's weird that MathWorld has the same formula for the complexity, but n is replaced with log n. Did I miss anything? --Pt 23:47, 8 Sep 2004 (UTC)

The wikipedia article explains that n refers to the number of digits the number has, while the MathWorld article seems to imply that n is the number to be factored itself. 192.160.6.252 18:16, 6 March 2006 (UTC)
Regarding this, I think we should change this to the mathworld version of the formula. If you think about it, it's much more accurate. This formula implies that it takes the same amount of time to factor any number with n digits, i.e. 10000 and 99999 for n=5. Obviously, this is not the case, and it's a much more continuous/monotonous function. This formula is almost.. inaccurate. Yeah, if you know nothing about the number but the number of digits, it's a useful approximation, but if you have the number itself.. Caveat: if you use log(n) as the "number of digits", then these formulas are the same.. But people always mean the discrete number in this case.

Also, what in the world is a constant doing inside a "big-O" notation? By convention, no constants are included inside the O. I will remove it, unless someone has am objection that makes sense.

n never should refer to the number of digits (see Big O notation, although it would be good to clarify in the article that the number of digits can be computed from b^n where b is the base and n is the number of digits in the base. Nicholasink


[edit] Update and Example

This page hasn't been updated in a while. I'm trying to figure out how this works and it would be great if there were some sort of toy example to go through and figure it out. Thanks a lot! Horndude77 05:49, 23 July 2005 (UTC)

This isn't the type of algorithm for which you can have a "toy" example. Any way you look at it, it's a very deep, involved algorithm. This is an introduction to GNFS that's about as basic as it can get. I have only a general idea of how the algorithm works, without knowing the little intricacies, and it's already complicated enough. You can try, though. I don't think an example is a good proposition, though - it would get too unwieldy for a Wikipedia page. --Decrypt3 00:07, July 25, 2005 (UTC)
I will create a simple example, with a five digit number or so, off site and link it to the article. The algorithm really isn't all that complicated, but an example would probably take up a bit too much room on the page. Once I get it done, if I find it's not too big I'll merge it into the article. --V. Alex Brennen Wed Nov 16 17:26:58 EST 2005
This paper contains a chapter explaining an example at some length. But it's a fairly technical paper and requires quite a bit of math background. Deco 19:45, 4 July 2006 (UTC)

[edit] Consistency in running time notation between GNFS and SNFS

The formulae for the running times of GNFS and SNFS are now inconsistent. The former uses n as the number of digits of the number to be factored, while the latter uses n as the number to be factored itself. To be consistent, I'll change the GNFS running time to the SNFS way. The current formula for GNFS needs to be corrected anyway since it is wrong in both context. Warut 22:07, 21 November 2006 (UTC)

Retrieved from "http://en.wikipedia.org../../../g/e/n/Talk%7EGeneral_number_field_sieve_452c.html"