mersenneforum.org GNFS linear equation
 Register FAQ Search Today's Posts Mark Forums Read

 2021-10-14, 05:08 #1 jwaltos     Apr 2012 Gracie on lookout. 23×53 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...06-01870-9.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 2021-10-14 at 05:11
 2021-10-14, 08:37 #2 Nick     Dec 2012 The Netherlands 110111000012 Posts Have you read the Lenstra book on this? https://link.springer.com/book/10.1007/BFb0091534
 2021-10-14, 12:13 #3 Dr Sardonicus     Feb 2017 Nowhere 14FB16 Posts Have you read Murphy's thesis? link provided in this post.
 2021-10-14, 14:37 #4 charybdis     Apr 2020 593 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 higher-degree (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 higher-degree polynomial (neither are monic; see the Kleinjung paper you linked to).
 2021-10-15, 01:46 #5 jwaltos     Apr 2012 Gracie on lookout. 23·53 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/hal-02151093v4/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 hand-waving 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 2021-10-15 at 01:48
 2021-10-15, 02:31 #6 Dr Sardonicus     Feb 2017 Nowhere 41×131 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.
 2021-10-15, 15:23 #7 chris2be8     Sep 2009 222410 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?
2021-10-15, 16:30   #8
charybdis

Apr 2020

593 Posts

Quote:
 Originally Posted by chris2be8 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.
I can't think of any cases where this would be useful for the numbers that we usually run SNFS on. You can't just switch out the linear polynomial for a quadratic one. The solution (as far as it is one) is to switch to octics, maybe somewhere between difficulty 270 and 290.

There are some obscure cases where the only way to run SNFS is to use two non-linear polynomials (see here).

2021-10-15, 23:59   #9
jwaltos

Apr 2012
Gracie on lookout.

6508 Posts

Quote:
 Originally Posted by Dr Sardonicus 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.
"
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 2021-10-15 at 23:59

 2021-10-16, 11:36 #10 Dobri   "刀-比-日" May 2018 13×19 Posts More on the topic can be found here, https://eprint.iacr.org/2011/292.
2021-10-16, 15:21   #11
jwaltos

Apr 2012
Gracie on lookout.

23×53 Posts

Quote:
 Originally Posted by Dobri More on the topic can be found here..
Dzekuje Dobri, I wasn't aware of this paper.

I'm going to post a couple of thing in the blog sub-forum 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 2021-10-16 at 15:26

 Similar Threads Thread Thread Starter Forum Replies Last Post enzocreti enzocreti 6 2019-01-06 05:58 Random Poster Math 2 2010-07-18 22:31 davar55 Puzzles 3 2008-10-09 00:35 davar55 Puzzles 52 2007-06-26 21:41 koal Puzzles 3 2003-07-03 11:58

All times are UTC. The time now is 21:10.

Tue Jan 25 21:10:38 UTC 2022 up 186 days, 15:39, 0 users, load averages: 1.45, 1.37, 1.38