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)

General Number Field Sieving is Quadratic Number Field Sieving

Although the exact definition of what General Number really is is not well-understood and not well-defined, the real examples are basically almost always quadratic number fields. You can safely define General Number as Quadratic Number in practice.

By definition, this algorithm always uses 2D sampling,which has a very sparse density for cubic fields and high-dimension fields. The effect of this sparse density is not explained very well, even if it is a very important (and almost fatal) geometric difference. It would be useful to explicitly distinguish quadratic fields,cubic fields, and so on.Aquahabitant (talk)

The most general definition of (Quadratic) Number Field Sieving is

Norm(ω-r)=0 mod pq
Norm(aω-b)=Poly(a,b,ω)
Poly(a,b,ω)-Poly(a,b,r)=0 mod (ω-r)
∏Poly(a,b,ω)=x² , ∏(aω-b)=ξ² ( Norm(ξ²)=x² )
∏Poly(a,b,r)=y² , ∏(ar-b)=η²  
ξ²-η²=0 mod (ω-r)
Norm(ξ²-η²)=0=x²-y²=0 mod pq

Practically, the General Number Field Sieaving is the Quadratic Number Field Sieving.

The square root ξ is undefined, because it's not a principal ideal, which means you have to resort to a minimal abstraction, such as

Norm(aω+b)=Poly(ω)
δ=Poly(ω)-Poly(r)=0 mod (ω-r)
(σ-1)δ=0 , σ∈Gal(K/k)
δ=0 mod Norm(ω-r)

In spite of this algorithm being intended to be most general, such a relation can't be generalized to most high-dimension fields, because you can't sample high-dimension ideals.

The norm valuation must satisfy the simple rational monotony

Norm(1)<Norm(1.5)<Norm(2)<Norm(3).....

and the simple Abelian relation

log Norm(L/k)=((dim L)/(dim K))log Norm(K/k)
(dim L/dim K)=(#Gal(L/K)-δ)

which is isometric to the universal absoute valuator

log Norm(∞,ω)=(log Norm(L/K,ω))/(dim L)

Both x² and y² must be squares, which means the minimal sampling cost is strictly larger than squaring (xy)

z²=(xy)²=∏(Poly(ω)Poly(r))=∏Quad(a,b)
{Quad(a,b)}={a²-Db²,a²-(rb)²}

which is a very simple 2D rational Quadratic Sieving with Quad(a,b). The geometry of this 2D algorithm is completely different from the well-known normal 1D rational Quadratic Sieving.

You can easily understand that the sampling cost of the General NumberField Sieving is always larger than this simple large 2D rational Quadratic Sieving cost with a very small B.

To summarize, the sampling cost of a small General Number Filed Sieving is always larger than this quadratically large 2D rational Quadratic Sieving, which directly shows this algorithm can never be faster than a very simple large 2D rational Quadratic Sieving algorithm.

Recall the multiplicative Abelan group structure of two ideal groups aω-b,ar-b are independent

For example, when you say 7=4=1 mod 3, the structure of 7 and the structure of 4=2x2 are independent. The rest of the algorithm is (basically) exactly the same as the classical sieving.

Intuitively, the norm operator is a very simple Helmholtz-type geometrical projector, which extracts the height of something (in this case they are ideal lattices,)which in this case is identical to the Minkowski volume.

Many irrational numbers satisfy

|log Norm(∞,ω)-log|ω||>0

Because this algorithm is a 2D search in the 2D field, it's an exhaustive search for all the principal ideals (aω+b).

If you want to use this algorithm with a high-dimension field, you can't have a 2D sampling and an exhaustive sampling at the same time. You always have to exclusively choose which sampling to use.

This is just one of the many simple examples why a high-dimension field sieving is absurd.

The sampling cost of this 2D/exhaustive principal-ideal search is quadratic.

In order to sample the largest primes <B, if ω is a real number

ω²=D
B < Norm(aω+b) < A
B < |aω+b|²< C
|aω-b|<|aω+ib|<|aω+b|
|aω-b|²<Norm(aω+b)<|aω+ib|²

If ω is a real number,this algorithm is a very simple Pell equation for each (c,G).

b²-Da²=Gc²

If ω is not a real number, the sampling is on the elliptic orbit

b²+Da²=Gc²

which is a well-known sparse sampling.

If ω is not a real number, all the samples are in the upper-half plane.

Im(a+bω) > 0

Norm(a+ω)=Norm(a-ω)=|a+ω|²

(ω,Norm(ω))⊂(ω)

Im(α)>0
Im(β)>0
Im(α+β)>0

This algorithm has a basic geometric cost structure that is very similar to rational quadratic sieving. The small (granule) ideal filtering cost is governed by the fundamental monotonic Legendre symbol density, which decays exponentially fast as the prime string-length decreases, and the sample density is restricted by the well-known exponentially sparse Dirichlet unit density.

The total sample density of 1D quadratic sieving is very sparse, because

Sample density = Dirichlet unit group density x Legendre symbol density <(1/p)(4/2ⁿ)

The 2D quadratic sieving usually has an extra squaring ζ(2) factor for the divisor c²

ζ(2)=1+1/4+1/9+....

— Preceding unsigned comment added by Aquahabitant (talk • contribs) 06:55, 29 May 2021 (UTC)

The elliptic identity

a²+ Db² = α² + Dβ²

is directly rewritten as the hyperbolic identitiy

a² - Dβ² = α² - Db²

which means they are geomerically correlated.

The Dirichlet hyperbolic unit group corresponds to the elliptic spiral. For simplicity, the 3rd divisors c²,γ² were omitted.

(aγ)²-D(βс)²=(αс)²-D(bγ)²=-G(cγ)²+((aγ)²+(αс)²)

They are geometrically unified as the orthogonal lattice

[1,iω]

with the linear correlation

|x+iωy|<|x+ωy|

|(a+bω)(с+dω)| ~ 2|(a+bωi)(c+dωi)|    i²=(-1)