Talk:General number field sieve

Discrete logarithms

various other wikipedia articles link to nfs to say that it can be used to compute the discrete logarithm, yet this page doesn't talk about it. At least it should tell that there are some significant differences (e.g. Anna Godusova "Number Field Sieve for Discrete Logarithm") — Preceding unsigned comment added by 193.8.68.100 (talk) 10:40, 6 February 2019 (UTC)

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 \over 3}(\log n)^{2 \over 3}\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 \over 3}\log(\log n)^{2 \over 3}\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)

Nonrational

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)

In mathematics, irrational specifically refers to real (or complex) numbers which are not ratios of integers. Non-rational is rare, but if used it means not rational. This includes the former situation, but is more general. For example, a function on an algebraic variety can fail to be a rational function; it will be non-rational but not irrational.

Examples

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

Big-O

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

Which fields

Thanks alot to whoever wrote the page. I'm reading up and can do it myself soon, but in the mean time can you make it clear which fields we're in throughout the process. The irreducible polynomials for example. I know it's obvious you mean irreducible in Q but it never hurts to get rid of all ambiguity when you're reading it for the first time.--Gtg207u 23:25, 5 November 2007 (UTC)

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)

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)

Finding square root

How to find square root of product of algebraic numbers ? —Preceding unsigned comment added by 59.93.211.167 (talk) 10:53, 4 November 2007 (UTC)

Constant c and the logarithm's base

The current formula uses the notation $\log n$. I usually interpret this to be the natural logarithm (i.e. the base e logarithm whose derivative is $1/n$), however other parts of the text say that n consists of $\log n$ bits, which implicitly means that the $\log n$ notation indicates a base two logarithm. As I understand it, the base of the logarithm (i.e. 2 or e) affects the constant c in the main complexity formula. According to the Handbook of Applied Cryptography, Example 2.61 and Section 3.2.7, the logarithm is a base e logarithm and the constant c is $(64/9)^{1/3}\approx 1.923$. I assume that this is correct. So, I suggest that the article be edited

• to state explicitly the value of the constant c, as above,
• to state that the base of the logarithm is e,
• to update text about the bit length of n to say that is $1+\lfloor \log _{2}n\rfloor$ and that $\log _{2}n=(\log n)/(\log 2)$

Unless somebody objects to this, or somebody else volunteers to make these changes, I may make these changes. DRLB (talk) 14:47, 26 May 2008 (UTC)

My recommendation is to remove the mention of the number of bits of n, mention that the logarithm is base e and cite the value of c which you state. Please tell me what you think. Skippydo (talk) 18:47, 26 May 2008 (UTC)

I've changed the logarithm notation to ln because it is also used for the L-notation and it is the ISO standard, see Logarithm. Henridv (talk) 17:10, 6 June 2012 (UTC)

Merge with SNFS

How about merging this article with Special number field sieve to form a single article simply entitled Number field sieve? Gremagor (talk) 05:06, 8 January 2010 (UTC)

That would make more sense to me. I started adding info about the NFSNET project, but it seems more particular to the specialized cases. W Nowicki (talk) 20:34, 9 August 2011 (UTC)

No, this would not make sense. The algorithms, motivations and approaches are quite distinct and should be reflected as such by distinct articles. DrBurningBunny (talk) 03:20, 21 April 2018 (UTC)

GNFS fastest algorithm for computing discrete logs

The article should somewhere state that the GNFS is also the (exponentially) fastest known algorithm for computing discrete logarithms over GF(p) (p prime). Some more background on that would be desirable, too. Cheers, Nageh (talk) 18:23, 27 January 2010 (UTC)

special hardware

Article should mention parallel approaches based on Bernstein's proposals for NFS circuits. I might try to add something but I haven't kept up with current developments. 67.117.130.143 (talk) 22:25, 3 December 2010 (UTC)

classical vs modern algorithm

The quadratic sieve is described as modern by its article and the number field sieve is described as classical. The invention of the quadratic sieve predates the number field sieve. shouldn't the number field sieve be a modern algorithm? 112.204.119.66 (talk)

It could mean classical in the quantum sense. Regardless, I'll remove both these terms. Skippydo (talk) 04:53, 24 February 2012 (UTC)

On second though, it does mean classical in the quantum sense and this should likely be stated in the intro. I'll remove modern from quadratic sieve and leave classical in this article. Skippydo (talk) 04:56, 24 February 2012 (UTC)

Ghost variable/function/thingy o(1)

The complexity formula contains the expression "o(1)", there article contains no explanation of an o function, thus the collective expression is, within the article, incomprehensible. This either needs to be explained, or rewritten to basic maths. As far as I can tell, o(1) must be 0 to give the numbers commonly cited around the internet, so why is it there at all?

EBusiness (talk) 18:47, 30 May 2019 (UTC)

References