20211014, 05:08  #1 
Apr 2012
Gracie on lookout.
427_{10} Posts 
GNFS linear equation
Using, as a partial resource base, https://www.mersenneforum.org/showthread.php?t=26984 and https://www.ams.org/journals/mcom/20...06018709.pdf, the GNFS is basically centered around the difference of squares and utilizes two monic equations of which one is linear. There are additional references to the genesis of the GNFS many of which I am aware and others I'm ignorant of. Regarding my question, I'm assessing perspective. Is there a unique interpretation and derivation or are there other facets of this association (the two equations).
What is the theoretical derivation* and justification of the linear equation? *Are there other pathways of developing this linear equation that do not rehash what already exists in the extant literature. Last fiddled with by jwaltos on 20211014 at 05:11 
20211014, 08:37  #2 
Dec 2012
The Netherlands
3×587 Posts 
Have you read the Lenstra book on this?
https://link.springer.com/book/10.1007/BFb0091534 
20211014, 14:37  #4 
Apr 2020
599 Posts 
It is not an equation. It is a polynomial. An equation implies that two things are being equated. A polynomial does not contain an equals sign.
I'm not sure what you're asking. The linear polynomial on its own doesn't have much relevance; it takes on meaning when combined with the higherdegree (algebraic) polynomial. GNFS does not require that one of the polynomials be linear, but the best known methods for finding polynomial pairs use one linear and one higherdegree polynomial (neither are monic; see the Kleinjung paper you linked to). 
20211015, 01:46  #5 
Apr 2012
Gracie on lookout.
427_{10} Posts 
@Nick: Yes. Borrowed it from the UWaterloo library a couple of times.
@Dr. Sardonicus: Yes. I had accessed both theses a while ago. Here is a relatively recent paper on the same subject matter from David and Zimmermann: https://hal.inria.fr/hal02151093v4/document @charybdis: Thanks for the extended response. I should have stated univariate rather than monic. I also agree that both polynomials act in unison. What I'm trying to elicit is the "why" and the "how" of the origin of these polynomials, specifically the linear one. Anytime I see something which requires some handwaving and hocus pocus to explain (heuristic reasoning) I delve into (and try to develop) the simplest foundations that support such conceptual structures. Most of what is presented in the available literature is technically straightforward, that is, I can follow the chain of reasoning but there seems to be leaks in this tire which requires more than just patching up (ie. additional bells and whistles). Thanks for the feedback. Last fiddled with by jwaltos on 20211015 at 01:48 
20211015, 02:31  #6 
Feb 2017
Nowhere
2×2,687 Posts 
I suggest rereading the early part of Murphy's thesis; in particular, the outline in Chapter 2, and specifically the sentence beginning with "The key point" on Page 16.

20211015, 15:23  #7 
Sep 2009
8B0_{16} Posts 
Is it possible to have a SNFS poly with degree > 1 on both sides? I'm particularly interested in large quartics where the rational norm is much larger than the algebraic norm if it's monic, so using a quadratic for the rational side should make it a much easier job.
If this is possible how would I find it? 
20211015, 16:30  #8  
Apr 2020
599 Posts 
Quote:
There are some obscure cases where the only way to run SNFS is to use two nonlinear polynomials (see here). 

20211015, 23:59  #9  
Apr 2012
Gracie on lookout.
7·61 Posts 
Quote:
The key point is that starting with polynomials which.." Thanks Sardonicus. I've approached the question of integer factorization from a different perspective and have come upon similar considerations but within a different mathematical environment. Faced with certain values such as a square, there are many different ways that such values occur and I've had to think about these options long and critically. Last fiddled with by jwaltos on 20211015 at 23:59 

20211016, 11:36  #10 
"刀比日"
May 2018
13·19 Posts 
More on the topic can be found here, https://eprint.iacr.org/2011/292.

20211016, 15:21  #11 
Apr 2012
Gracie on lookout.
7·61 Posts 
Dzekuje Dobri, I wasn't aware of this paper.
I'm going to post a couple of thing in the blog subforum which will provide some background on why I asked this question. Going through some of the bibliographic references in the above and other papers has helped. Last fiddled with by jwaltos on 20211016 at 15:26 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
An integer equation  enzocreti  enzocreti  6  20190106 05:58 
A nonlinear differential equation  Random Poster  Math  2  20100718 22:31 
An Equation to Solve  davar55  Puzzles  3  20081009 00:35 
Solve this equation  davar55  Puzzles  52  20070626 21:41 
Cuberoot Equation  koal  Puzzles  3  20030703 11:58 