1. 1

    Why would brute force only be associated with Caesar cipher, as the diagram implies?

    1. 1

      “Brute Force” can be applied to everything, absolutely everything, with varying degrees of success. As such, having it associated with everything carries no information.

      However, in the case of the Shift Cipher it’s practical and successful (and parallelisable). In other cases it is only successful once other techniques are applied to reduce the computation needed.

      Similarly “Frequency Analysis” isn’t used only in the case of the Substitution Cipher, but that’s where we first meet it, and then it’s a tool we can use repeatedly elsewhere.

    1. 1

      Ack those graphs have various classes of concepts as nodes which really bothers me (systems/attacks/people)

      1. 2

        The nodes are “things to discuss”, and everything you mention there fall into that category.

        But it’s interesting that you say that - I’m developing a larger version of this diagram where the different types of nodes are distinguished, and the nature of the relationship is made explicit. I share your disquiet, and it’s part of what’s driving the design.

        1.  

          Makes sense. Thanks for engaging with the comment - I appreciate that.

          Internal to my research lab (although hopefully someday more openly) we’re working on a graph strictly of crypto concepts, particularly those which are sufficient for/imply the existence of one another. E.g. nodes might be “Random Oracle” or “Zero-Knowledge Sigma Protocol” which both might point to “Fiat-Shamir Heuristic” which might be one node pointing into “Non-Interactive Zero Knowledge” in that they are sufficient for its construction. We also want to encode black-box impossibility results similarly.

      1. 3

        The article advocates asking “why?” instead of merely “how?” (and “what?”), but doesn’t answer any of these questions. I thought I’d at least see an image.

        1. 2

          Added in edit: I’m getting a lot of mis-understanding, and I really don’t know what to do to ask the question differently. But the down-votes (off-topic) are clear, so I’ll go away and re-think this. I still believe the question I’m trying to ask is relevant and on-topic, so perhaps I’m just not being clear about what the question is.

          The response has given me much to think about. In particular, I guess I need to read more here to try to work out what the audience is. It would seem that thought-experiments of this type aren’t welcome. Fair enough.


          I don’t understand your criticism.

          Yes, the article is asking why. The point is that this is a question that requires either thought or experiment. To provide an answer in the article, or an image of the result, defeats the entire purpose of the question. If you want to know what the result is you can either follow the link in the article, or you can do the experiment.

          But some people might choose to think about this for themselves, and giving the answer would prevent that.

          And the question is about the why. Everyone I ever ask seems simply to do the experiment, look up the answer, or tell me how a photocopier works. I was hoping someone would be able to reason out the why you get the result you do, not simply tell me how the copier achieves the result it does.

          Clearly I’m just not asking the question correctly - only one person has ever understood what I’m trying to ask, and I don’t understand why that’s the case.

          Deeply frustrating - I was hoping for more from the Lobsters community. But I see now that there are two downvotes, marking this as “off-topic”. I thought this was sufficiently intellectually engaging, but I guess I’ve misjudged the audience.

          1. 3

            I found the title misleading. If it had read “Don’t just ask how — ask why”, and then used the mirror photocopy question as an example, that would be one thing. But when I see a headline asking a question, I expect the article to answer it, and this case I was left disappointed.

            1. 1

              That’s really interesting. When I see an article asking a question I expect it to be discussed and not necessarily answered. I wouldn’t have expected people to expect articles always to answer the questions in their titles.

              Useful to see the different perspective. Thank you.

              Edit: In case an article intends to pose a question without answering it, how should it be entitled?

            2. 2

              The question you are asking absolutely requires knowing how a photocopier or scanner works. There’s no deeper philosophical question involved.

              1. 1

                The entire point about this question is that I disagree with you here. I believe it is possible to deduce the result without knowing how a copier works, only by knowing its desired behaviour. That is the point of the thought-experiment, and obviously I’ve not made that clear enough.

                So let me say this: knowing only what a copier is intended to do, and without knowing anything about how it works, can you, through various thought-experiments, deduce what you must get if you copy a mirror?

                I believe it’s possible.

                1. 1

                  You get whatever that mirror was reflecting at the time. In this case, some part of the inside of the photocopier.

                  If there is a deeper point beyond that, it’s lost on me.

                  1. 1

                    You get whatever that mirror was reflecting at the time.

                    That turns out not to be the case, and I believe that even knowing nothing more than what a copier is supposed to accomplish, it’s possible via thought-experiments to deduce that. The reasoning is quite tricky, in places subtle, and I’m not convinced my argument is completely water-tight, and that’s why I believe this question is deeper than most people think.

                    1. 1

                      The only subtlety is that the lighsource is angled. My first guess would have been a white mirror surface because I though the light source was parallell to the surface, but of course that would have prevented the CCD from being on the same axis.

                      In any case, it devolves into the technical details on how to implement a photocopier. Mildly interesting, I learned something today.

                      1. 1

                        Certainly it does lead to the question of how to implement a photocopier, but there is still more going on before that. If you implement a good photocopier, is it an unavoidable consequence that they all give the same result when you copy a mirror?

                      2. 1

                        Eh, that is the case, it just happens to be that because of how the picture is pieced together over time, that reflection is always away from the light.

                        I think the reflective nature of graphite plays a role here as a forcing function in copier design

                        I’m now actually curious to see what chain of reasoning you’ve applied to this.

                        1. 1

                          You have a message.

                2. 2

                  It’s very much off-topic as it has nothing to do with computing.

                  1. 1

                    Not directly, no, I agree, and I admit that I didn’t realise that this site is so specifically focussed only on computing. Having said that, my colleagues were intrigued by my approach to this problem. As mentioned in another comment, it’s not actually anything to do with how a photocopier works. It’s about deducing behaviour in an unknown context purely from knowing the overall desired behaviour of a system.

                    As such I’d’ve thought it was squarely in the realm of the sort of thing programmers would occasionally have to do, and hence of interest.

                    The options are (a) I was wrong, or (b) I’ve still not figured out how to ask the question in a way that makes it clear what the real question is, or (c) something else.

              1. 4

                Wait, you’re Colin Wright? As in “the inventor of siteswap” Colin Wright? Well, this is amazing :D

                1. 2

                  Er, yes? Well, I was in one of the groups, but yes, I was involved in that.

                  Hello …

                1. 3

                  Is this only for PhD students? I’d join but the signup requires an academic email, and I haven’t had one since I finished my PhD. I can possibly point to other credentials to prove I’m not a crank.

                  1. 1

                    Absolutely not meant to be a PhD club. You can email hsx at hessix dot com and will get an account right away.

                    1. 4

                      Then you need to change this - from the “User Guide”:

                      Where am I?

                      • A platform for PhDs in math and stat to discuss research.

                      Why do I need to verify my academic email address?

                      • An algorithm uses it to determine if you are a genuine PhD candidate in math/stat.

                      This sounds like it’s specifically and only for PhD candidates.

                      1. 1

                        It’s now open to everyone with an email address

                        1. 2

                          The “guide” document says:

                          • Why do I need to verify my email address?

                            • To reduce spam. If you are a math/stats PhD, please use your academic email so that your username is highlighted as PhD. The email address is only used in the account creation stage.

                          There are people with math PhDs who do not have an academic email address, so it’s not clear what you’re doing, or why you’re doing it.

                          I’m not complaining, this isn’t a criticism, I’m just asking what you’re trying to accomplish, how you’re trying to accomplish it, and what happens in other cases. The document, as it stands, isn’t clear.

                          Are you intending to highlight those who have a PhD in math but do not work at an academic institution? Are you then intending to verify them, and if so, how?

                          1. 1

                            Any PhD candidate, holder who still works in academia, or holder who doesn’t work in academia can submit proof of their PhD status during account creation (e.g. link to PhD thesis, university-hosted online profile, etc.) to facilitate verification. Once verified, these users are highlighted on the platform as PhDs. Registering with an academic email makes the verification faster and easier, otherwise it’s not required. I’ll clarify the user guide.

                  1. 3

                    One error that leapt out at me - it says:

                    “The symbol for showing that one set is a member of another set is ⊂”

                    That’s wrong. That’s the subset symbol, and I suspect it’s the symbol that’s right, and the English that’s wrong.

                    The example is right: P ⊂ N ⊂ Z ⊂ Q

                    But these are not members of each other, they are subsets.

                    1. 2

                      Previously with the HN juice: https://lobste.rs/s/dzpi3p/spikey_spheres

                      1. 1

                        Hah - I hadn’t seen that someone had cross-posted it. Sorry.

                      1. 11

                        In truth, the actual math problem has nothing to do with pizza.

                        Warmup:

                        Dissect a square into congruent pieces that all touch the center point. This is a classical dissection, and yes, you can think of it as slicing up a square with scissors. In how many ways can you do this? Hint: probably more than you think. How many pieces can you use? There are probably fewer options than you think.

                        Next: Dissect a square into congruent pieces that do not all touch the center point. Again, i how many ways can you do this? The answer might be smaller than you think.

                        Next: Dissect a square so that the center point is in the interior of a piece. Again, not hard. Again, in how many ways can you do this?

                        Moving on - replace “square” with “triangle”. Then “pentagon”. All three options are still possible, and again counting families and characterising solutions is an interesting exercise.

                        And now we’re ready for the real problem.

                        Dissect a circle into congruent pieces that do not all touch the center point. I know of two infinite families, one consisting of infinitely many uncountable members. That’s a lot.

                        But this is an open question:

                        Can you dissect a circle into congruent pieces such that the center point is in the interior of one of the pieces?

                        This isn’t especially new - I wrote[0][1] about it 5 years ago, and worked on it with Joel (one of the authors).

                        [0] http://www.solipsys.co.uk/new/DissectingASquare.html?L_20160108

                        [1] https://lobste.rs/s/1rmdpy/dissecting_a_square_-_the_prelude_to_the_pizza_slicing_paper

                        1. 3

                          In truth, the actual math problem has nothing to do with pizza.

                          That’s why I get really annoyed when I’m getting maths news from general sites. I don’t know where else to get the news, though. It’s been a while since I’ve been in academia, so where is the news sites for mathematics people?

                          1. 4

                            I don’t know of any single source - these days it seems unlikely that there can be. However, there are several sources that talk about math in general, and they usually pick up on major stories curiosities such as this. Included are:

                            They, in turn, list others. I write about this sort of stuff, but I’m not qualified to write about real advances in serious math.

                            In short, I don’t think there is a “math news” site that writes things “properly” without trying to make it “relevant” for ordinary people.

                            1. 1

                              Excellent question. Upvoted in hope of an answer.

                          1. 1

                            Actual error bound?

                            1. 3

                              Someone else has taken the title literally and computed the error when you divide by 3000 instead of (54x53). However, that’s not the point of the article.

                              You can get a handle on the error in the article by identifying all the approximations and estimating from there. I’ll be doing that in a follow-up, but the main error comes from using e ~ 2.7. It’s closer to 2.72. That error is about 0.7%. When we raise to the power of 54 that gives an error of about 40% to 50%.

                              But that is offset by the approximation that 2^10 ~ 10^3, and raising that to the power of 5. It’s an interesting and useful exercise to refine the original by chasing down estimate of the errors. I might do that in a follow-up post.

                              1. 2

                                By the definition of factorial as 1×2×…×n, you can get 52! exactly if you divide 54! by 53×54=2862. If you divide by the approximation 3000 instead of 2862, the result is exactly 95.4% of 52!.

                                1. 3

                                  There’s a great deal more approximation being done than just 3000 ~ 2862. The calculation of 54! is itself very approximate.

                                  Anyway, now that I’m back at my laptop: (10^68 - 52!) / 52! ~ 0.24.

                                  1. 2

                                    I really hope you understand that that’s not the point of the article.

                                1. 2

                                  I’m Rider of Giraffes, and my details are in my profile.

                                  You can get access to the user list via the “About” link at the bottom of the page, and from there you can see the profiles people have chosen to put up. I haven’t time now, but it would be interesting to see if people gave details here, and yet have nothing in their profiles. I wonder if that would say anything about them?

                                  1. 2

                                    Suggestion to the lobste.rs developers: when new users accept their invitations, lobste.rs should prompt them to fill in their profiles with the same link that they put in their invitation requests (or edit if they prefer).