You are browsing as Guest
Click here for list of discussions
Click here to login





Discussion: G3C_and_factoring
You have read-only access
You may need to scroll to the right ...

Click here to view in strict time order
Click here to view in neighbourhood mode.

%3 N_20161204230627_NeilC    By NeilC 2016/12/04 @ 23:06:27 -------------------------------- Just read your nice blog post about 3 colouring and factoring. Nice to know that it's available to point people at when I tell them the Read and Wright paper story:-)        (select only this node)     N_20161204230828_CDW    By CDW 2016/12/04 @ 23:08:28 -------------------------------- Thank you.        (select only this node)     N_20161204230627_NeilC->N_20161204230828_CDW N_20161204230654_NeilC    By NeilC 2016/12/04 @ 23:06:54 -------------------------------- You might add a line about factoring 65 and how long it takes compared to multiplying 5x13        (select only this node)     N_20161204230627_NeilC->N_20161204230654_NeilC N_20161204230849_CDW    By CDW 2016/12/04 @ 23:08:49 -------------------------------- Where do you think such as addition might most comfortably fit?        (select only this node)     N_20161204230654_NeilC->N_20161204230849_CDW N_20161204230949_NeilC    By NeilC 2016/12/04 @ 23:09:49 -------------------------------- It might *also* be quite interesting to take some graphs for smooth numbers near the RSA challenges, and see how hard multiplication is on that size for smooth numbers, and how hard for products of large primes.        (select only this node)     N_20161204230654_NeilC->N_20161204230949_NeilC N_20161204230916_NeilC    By NeilC 2016/12/04 @ 23:09:16 -------------------------------- I thought it would fit immediately before the discussion of RSA graphs near the end of the paper.        (select only this node)     N_20161204230849_CDW->N_20161204230916_NeilC N_20161204231027_CDW    By CDW 2016/12/04 @ 23:10:27 -------------------------------- I might put that up as a different page and point at it.        (select only this node)     N_20161204230916_NeilC->N_20161204231027_CDW N_20161204231056_CDW    By CDW 2016/12/04 @ 23:10:56 -------------------------------- Are you suggesting having graphs for several numbers - some smooth and some semi-primes - and then giving times required to colour both for multiplication and for factoring?        (select only this node)     N_20161204230949_NeilC->N_20161204231056_CDW N_20161204231128_CDW    By CDW 2016/12/04 @ 23:11:28 -------------------------------- That would be interesting, but would take a few days to sort out. Do you think it would be worthwhile? Or were you thinking of something else?        (select only this node)     N_20161204231056_CDW->N_20161204231128_CDW N_20161204231241_NeilC    By NeilC 2016/12/04 @ 23:12:41 -------------------------------- That's sort of what I was thinking. I remember Ron Read being thrilled to discover that 5x13 was seriously simpler to compute than to factor 65.        (select only this node)     N_20161204231128_CDW->N_20161204231241_NeilC N_20161204231317_NeilC    By NeilC 2016/12/04 @ 23:13:17 -------------------------------- I also was wondering how long it would take to colour the multiplication graph for some bigger products (and whether it makes a difference whether the corresponding factor graph has many colourings or just one.        (select only this node)     N_20161204231241_NeilC->N_20161204231317_NeilC N_20161204231409_CDW    By CDW 2016/12/04 @ 23:14:09 -------------------------------- The thing is that the multiplication graph is effectively forced from top to bottom, and there need never be any back-tracking. That's why it's quick to multiply. When colouring a factoring graph there come points where there are no forced colours, so you have to guess. That then leads to back-tracking.        (select only this node)     N_20161204231317_NeilC->N_20161204231409_CDW N_20161204231525_NeilC    By NeilC 2016/12/04 @ 23:15:25 -------------------------------- Yes, I understand the forcing, but I'm more interested in whether the random algorithms (a la Dominic Welsh in the talk that inspired this whole thing in 1985!) are good on forced colourings, or whether they are still slow even then. Also, how far out such algorithms work in practice.        (select only this node)     N_20161204231409_CDW->N_20161204231525_NeilC N_20161204231442_CDW    By CDW 2016/12/04 @ 23:14:42 -------------------------------- Factoring smooth numbers is easier, because choices can be made that lead to different factorings, so you don't always have to back-track when making a decision. For some of the choices it won't matter, the different choices giving different factorisations.        (select only this node)     N_20161204231409_CDW->N_20161204231442_CDW N_20161204231557_CDW    By CDW 2016/12/04 @ 23:15:57 -------------------------------- I suspect that more factorings make it faster, but the obvious counting argument will give roughly the right amount of "easier".  The random algorithms don't work well unless you improve it by colouring the forced vertices as they turn up.        (select only this node)     N_20161204231525_NeilC->N_20161204231557_CDW N_20161204231617_CDW    By CDW 2016/12/04 @ 23:16:17 -------------------------------- The usual algorithm is to find a triangle, see if anything is forced, guess something, see if that forces anything, deduce what you can, repeat until coloured or a contradiction. Back-track if necessary.        (select only this node)     N_20161204231557_CDW->N_20161204231617_CDW N_20161204231635_CDW    By CDW 2016/12/04 @ 23:16:35 -------------------------------- The completely random "annealing" type algorithm is, in general, very bad, even on multiplication, unless the forced vxs are coloured as they get forced. The "local minimum" problem is a complete killer.        (select only this node)     N_20161204231617_CDW->N_20161204231635_CDW N_20161204231702_CDW    By CDW 2016/12/04 @ 23:17:02 -------------------------------- It might be interesting to implement the pure annealing algorithm a la Dominic and then see whether there is a difference, but I'm not sure what it would tell us. Thoughts?        (select only this node)     N_20161204231635_CDW->N_20161204231702_CDW N_20161204231721_NeilC    By NeilC 2016/12/04 @ 23:17:21 -------------------------------- Not sure. I think it might say something deep about the structure of the search space for hard colourings versus easy colourings. But this is purely a hunch.        (select only this node)     N_20161204231702_CDW->N_20161204231721_NeilC N_20161204231807_CDW    By CDW 2016/12/04 @ 23:18:07 -------------------------------- As I recall, DW's algorithm was to select a vx at random, choose a new colour for it. If it made the number of broken edges smaller, accept with probability nearly (if not exactly) 1. If it made the number of broken edges smaller, accept with small probability $p$. Make $p$ get smaller over time.        (select only this node)     N_20161204231721_NeilC->N_20161204231807_CDW N_20161204231916_CDW    By CDW 2016/12/04 @ 23:19:16 -------------------------------- I do have a theory about what makes a 3 colourable graph easy/difficult to colour, but while related, that's a different question.        (select only this node)     N_20161204231721_NeilC->N_20161204231916_CDW N_20161204231827_CDW    By CDW 2016/12/04 @ 23:18:27 -------------------------------- My recollection was that it really was simulated annealing. As such it seems to me it will just flail about without ever finding a legal colouring in a reasonable time.        (select only this node)     N_20161204231807_CDW->N_20161204231827_CDW N_20161204231845_CDW    By CDW 2016/12/04 @ 23:18:45 -------------------------------- It will be faster if there are more colourings, i.e. the number is smooth. It might be interesting to see if it's faster going in the multiply direction, but my hunch is that it will just continue to flail.        (select only this node)     N_20161204231827_CDW->N_20161204231845_CDW