20210902, 15:51  #507  
"Curtis"
Feb 2005
Riverside, CA
5069_{10} Posts 
Quote:
A setting of 0.04 or 0.05 also reliably (?) produces enough relations for msieve filtering to work, useful if you're using that combination of CADO sievers and msieve postprocessing. 

20210902, 17:07  #508 
"Ed Hall"
Dec 2009
Adirondack Mtns
10013_{8} Posts 
Actually, I've left that alone and have adjusted rels_wanted such that future runs exceed multiple filtering and Msieve will probably build a matrix, for >c130. c130 and less, I usually just let CADONFS finish. I prefer one filtering run and if I've exceeded the minimum required, it's a bonus.

20210902, 17:54  #509 
Aug 2020
79*6581e4;3*2539e3
419 Posts 
Then I'll use P=5M as well, seems like a good middleground between 3M(c195) and 10M(c220). CADO documentation says a large P generally results in better polys, but fewer. Ambiguous as most parameters seem to be...
I'll do 10M11M with nq=5^6. Is incr=420 good for that range? 
20210902, 17:55  #510  
Apr 2020
546_{10} Posts 
Quote:
Edit: just saw bur's post. I'm seeing about 700k threadseconds per 1M range, or about 0.1% of what I estimate the sieving time ought to be on the same hardware. So 10M is still a "low" leading coefficient in this search and I'd stick with incr=420. If the returns above 10M aren't good then we can consider switching to larger incr. Last fiddled with by charybdis on 20210902 at 18:03 

20210902, 18:18  #511 
Aug 2020
79*6581e4;3*2539e3
419 Posts 
Slightly offtopic, but I'll take the chance to ask: what are singletons and ideals?
In another thread you explained it as "...ideals are essentially the variables that our equations are in." Is it possible to explain it differently? Maybe it's a language problem, but how is an equation in a variable? 
20210902, 18:58  #512 
Apr 2020
2×3×7×13 Posts 
An ideal is a subset of a ring that forms an additive subgroup and is closed under multiplication by arbitrary elements of the ring. But I don't think that's what you wanted
We have an algebraic polynomial f(x), which in this case will be degree 5, and rational polynomial g(x). Our relations are (a,b) pairs for which the algebraic norm b^5*f(a/b) and rational norm b*g(a/b) are both smooth with respect to the chosen bounds. The aim is to find a set of relations for which the products of the algebraic and rational norms are both squares; we therefore need each prime to appear an even number of times in this set on each side. (0 is even of course.) There is a further complication which is that on the algebraic side two copies of the same prime p count as different if they correspond to different roots of the algebraic polynomial mod p; I think I explained this before. But why is this necessary? The answer is that the algebraic norms are actually being used to represent complex numbers in a certain number field, and it's the product of these numbers that needs to be square. The (prime, root) pairs correspond to *ideals* (in fact prime ideals) of a particular ring inside this number field. The same is true on the rational side, but the mathematics is much easier because the number field in question is the rational numbers  hence "rational side"  and the ring is the integers. For each prime p, there is a prime ideal of the integers consisting of the multiples of p, and all prime ideals of the integers are of this form. So on the rational side there is no complication with roots; each prime corresponds to a single ideal. Finding the required set of relations is equivalent to solving a huge system of linear equations mod 2 (i.e. finding linear dependencies of a huge matrix), since we need each ideal to appear an even number of times in our set. The unknowns/variables are "is this relation in the set", which can be either 0 (no) or 1 (yes). There is one equation for each ideal that appears in the relations. Say a particular ideal appears in relations 337, 590 and 4449, and no others. Then the equation will be "is rel 337 in the set" + "is rel 590 in the set" + "is rel 4449 in the set" = 0 (mod 2). The smaller the matrix, the easier it will be to solve. If an ideal only appears once as a factor in the entire dataset, then the relation it's in can't possibly be part of any set that contains each ideal an even number of times. This relation is called a singleton, and can be removed in filtering (we don't want to get rid of it forever, because if we sieve some more we might find another relation containing the given ideal). After all the singletons have been removed, we will have created new singletons, so we repeat this process until none are left. At this stage, we need there to be more relations (unknowns) than ideals (equations), else we won't be able to solve our system of equations. tasks.filter.required_excess = 0.05 means that CADO will only proceed with filtering if there are 5% more relations than ideals left at this stage. This is useful because if we have a large excess, we can afford to throw out some more (carefully chosen) relations in order to obtain a smaller matrix. ...and of course even this is an oversimplification as I haven't mentioned merging, cycles or quadratic characters. But it should hopefully give some idea of what's going on. Last fiddled with by charybdis on 20210902 at 19:14 
20210903, 01:57  #513 
Apr 2020
2·3·7·13 Posts 

20210903, 17:39  #514 
Aug 2020
79*6581e4;3*2539e3
419 Posts 
Thanks, that's very helpful again. So we are not looking directly at the prime factors of a and b to create the squares but at the ideals?

20210903, 20:22  #515 
Apr 2020
1000100010_{2} Posts 
Yes: technically on the algebraic side we're looking at factorizations of (nonprime) ideals rather than of numbers. The product of two ideals is the set of all the finite sums of products of elements of the two ideals (we'd like it to be just the set of products of the elements, but that might not be an ideal). In number fields we don't usually have a direct equivalent of unique prime factorization: for example, in \(\mathbb{Q}[\sqrt{5}]\), we have \(6 = (2)(3) = (1+\sqrt{5})(1\sqrt{5})\) which is not unique  and yes, all those factors are indeed prime in the required sense. However, if instead we look at factorizing ideals into prime ideals, we do have unique factorization, or at least something close enough.
The reason that NFS is feasible is that for the ideals we're interested in, there is a direct correspondence between the factorization of the ideal into prime ideals and the prime factorization of an integer called the norm of the ideal. This is the (prime, root) <> (prime ideal) correspondence I mentioned in the previous post. The norm is the number b^d*f(a/b) that you're familiar with by now. 
20210904, 01:22  #516 
Apr 2020
222_{16} Posts 
That's more like it:
Code:
n: 131059381160969890473184300494609882864431978456309837392557442177052630795870868382351497139096300267026719895523089453234540027837272339241326353564822104741922921032481193771448768282517397405699723 skew: 272726903.707 c0: 3419281390608846968778268338419370567158813629362 c1: 258854464423997783647767547760287821024753 c2: 767236135068739573740612500186036 c3: 3287457778282621690365713 c4: 10211483437143594 c5: 12458880 Y0: 575476667446322731628680355694195898900 Y1: 2846500471772809349499599 
20210904, 02:18  #517 
Jun 2012
2×1,621 Posts 
Nice one! Finishing my search Sunday then I’m done regardless of the results.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Primes in nfibonacci sequence and nstep fibonacci sequence  sweety439  And now for something completely different  17  20170613 03:49 
Team sieve #41: C165 from 3366:i2098  RichD  Aliquot Sequences  36  20131129 07:03 
80M to 64 bits ... but not really reserved  petrw1  Lone Mersenne Hunters  82  20100111 01:57 
What's the next in the sequence?  roger  Puzzles  16  20061018 19:52 
Sequence  Citrix  Puzzles  5  20050914 23:33 