mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Aliquot Sequences

Reply
 
Thread Tools
Old 2021-09-02, 15:51   #507
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

10011110100112 Posts
Default

Quote:
Originally Posted by charybdis View Post
The best solution is to make CADO oversieve a bit to reduce the matrix size; you can do this by adding tasks.filter.required_excess = 0.05 to the params file (experiment with different values to see what's best for your system).
I use 0.05 for C140-C160 to reduce matrix time when running all jobs on a single machine; I think EdH (who sieves on a "farm" of a dozen or more smaller machines) uses 0.08 or 0.10. The number is a percentage of total relations, so 0.05 asks CADO to make sure there are 5% more relations than strictly necessary for filtering; this "extra" yields a usefully smaller matrix. There are diminishing returns- do not expect a setting of 0.20 to make a 30-minute matrix!

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.
VBCurtis is online now   Reply With Quote
Old 2021-09-02, 17:07   #508
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

2·29·71 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
. . . I think EdH (who sieves on a "farm" of a dozen or more smaller machines) uses 0.08 or 0.10. . .
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 CADO-NFS finish. I prefer one filtering run and if I've exceeded the minimum required, it's a bonus.
EdH is offline   Reply With Quote
Old 2021-09-02, 17:54   #509
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

1101010002 Posts
Default

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 10M-11M with nq=5^6. Is incr=420 good for that range?
bur is online now   Reply With Quote
Old 2021-09-02, 17:55   #510
charybdis
 
charybdis's Avatar
 
Apr 2020

22416 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
The number is a percentage of total relations, so 0.05 asks CADO to make sure there are 5% more relations than strictly necessary for filtering...
This is a decent first approximation to what required_excess does in practice, but strictly this isn't quite correct. It's not a proportion of total relations, but rather the number of relations after the first singleton removal step, which must be at least 5% more than the number of ideals remaining at that stage. This will probably require slightly more than 5% additional raw relations.

Edit: just saw bur's post. I'm seeing about 700k thread-seconds 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 2021-09-02 at 18:03
charybdis is offline   Reply With Quote
Old 2021-09-02, 18:18   #511
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

6508 Posts
Default

Slightly off-topic, 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?
bur is online now   Reply With Quote
Old 2021-09-02, 18:58   #512
charybdis
 
charybdis's Avatar
 
Apr 2020

22×137 Posts
Default

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 2021-09-02 at 19:14
charybdis is offline   Reply With Quote
Old 2021-09-03, 01:57   #513
charybdis
 
charybdis's Avatar
 
Apr 2020

22·137 Posts
Default

Quote:
Originally Posted by charybdis View Post
I'll do 0-5M with P=5M, nq=15625, incr=420, sopteffort=10, ropteffort=100.
Best was 4.02e-15 which doesn't even beat the c202 record. I'll try the same range with P=10M; not expecting it to be better but I'd like to see how the performance compares.
charybdis is offline   Reply With Quote
Old 2021-09-03, 17:39   #514
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

1A816 Posts
Default

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?
bur is online now   Reply With Quote
Old 2021-09-03, 20:22   #515
charybdis
 
charybdis's Avatar
 
Apr 2020

22×137 Posts
Default

Yes: technically on the algebraic side we're looking at factorizations of (non-prime) 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.
charybdis is offline   Reply With Quote
Old 2021-09-04, 01:22   #516
charybdis
 
charybdis's Avatar
 
Apr 2020

22416 Posts
Default

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
Score 4.807e-15. Nothing else above 4.2 so this was a lucky hit.
charybdis is offline   Reply With Quote
Old 2021-09-04, 02:18   #517
swellman
 
swellman's Avatar
 
Jun 2012

3,253 Posts
Default

Nice one! Finishing my search Sunday then I’m done regardless of the results.
swellman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Primes in n-fibonacci sequence and n-step fibonacci sequence sweety439 And now for something completely different 17 2017-06-13 03:49
Team sieve #41: C165 from 3366:i2098 RichD Aliquot Sequences 36 2013-11-29 07:03
80M to 64 bits ... but not really reserved petrw1 Lone Mersenne Hunters 82 2010-01-11 01:57
What's the next in the sequence? roger Puzzles 16 2006-10-18 19:52
Sequence Citrix Puzzles 5 2005-09-14 23:33

All times are UTC. The time now is 06:37.


Wed Dec 8 06:37:32 UTC 2021 up 138 days, 1:06, 1 user, load averages: 0.89, 1.12, 1.13

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.