mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Homework Help

Reply
 
Thread Tools
Old 2021-10-14, 05:08   #1
jwaltos
 
jwaltos's Avatar
 
Apr 2012
Gracie on alert.

34·5 Posts
Default 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
jwaltos is offline   Reply With Quote
Old 2021-10-14, 08:37   #2
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

2×3×293 Posts
Default

Have you read the Lenstra book on this?
https://link.springer.com/book/10.1007/BFb0091534
Nick is offline   Reply With Quote
Old 2021-10-14, 12:13   #3
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

10100000001012 Posts
Default

Have you read Murphy's thesis? link provided in this post.
Dr Sardonicus is offline   Reply With Quote
Old 2021-10-14, 14:37   #4
charybdis
 
charybdis's Avatar
 
Apr 2020

2×3×7×13 Posts
Default

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).
charybdis is offline   Reply With Quote
Old 2021-10-15, 01:46   #5
jwaltos
 
jwaltos's Avatar
 
Apr 2012
Gracie on alert.

19516 Posts
Default

@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
jwaltos is offline   Reply With Quote
Old 2021-10-15, 02:31   #6
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

120058 Posts
Default

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.
Dr Sardonicus is offline   Reply With Quote
Old 2021-10-15, 15:23   #7
chris2be8
 
chris2be8's Avatar
 
Sep 2009

133 Posts
Default

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?
chris2be8 is offline   Reply With Quote
Old 2021-10-15, 16:30   #8
charybdis
 
charybdis's Avatar
 
Apr 2020

2×3×7×13 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
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).
charybdis is offline   Reply With Quote
Old 2021-10-15, 23:59   #9
jwaltos
 
jwaltos's Avatar
 
Apr 2012
Gracie on alert.

19516 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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
jwaltos is offline   Reply With Quote
Old 2021-10-16, 11:36   #10
Dobri
 
"刀-比-日"
May 2018

2·7·17 Posts
Default

More on the topic can be found here, https://eprint.iacr.org/2011/292.
Dobri is offline   Reply With Quote
Old 2021-10-16, 15:21   #11
jwaltos
 
jwaltos's Avatar
 
Apr 2012
Gracie on alert.

34·5 Posts
Default

Quote:
Originally Posted by Dobri View Post
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
jwaltos is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
An integer equation enzocreti enzocreti 6 2019-01-06 05:58
A non-linear differential equation Random Poster Math 2 2010-07-18 22:31
An Equation to Solve davar55 Puzzles 3 2008-10-09 00:35
Solve this equation davar55 Puzzles 52 2007-06-26 21:41
Cuberoot Equation koal Puzzles 3 2003-07-03 11:58

All times are UTC. The time now is 07:11.


Wed Dec 1 07:11:21 UTC 2021 up 131 days, 1:40, 1 user, load averages: 1.60, 1.41, 1.35

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.