Wikipedia:Reference desk/Archives/Mathematics/2019 September 25

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

September 25

Fast verification that elliptic-curve point multiplication gives (0,0)

I'm trying to write a program that verifies AGKM primality certificates, but on a platform where elliptic curve point multiplication isn't feasible because division (which I need for the modular multiplicative inverse) is so slow that it isn't implemented for the big-integer type I'm using. Is there a faster way to simplify verify that the multiplication comes to the identity point (0,0)? I can have a handful of other precomputed values passed in as well, but they'll also need verification. NeonMerlin 02:45, 25 September 2019 (UTC)

Maybe if you include the code that is slow we can suggest ways to speed it up ? SinisterLefty (talk) 22:27, 26 September 2019 (UTC)

Normally you implement the modular multiplicative inverse with the extended Euclidean algorithm. Your language or bignum library might have a routine for that. If not, it is just a few lines of code. I don't see an obvious way to tell whether two points are inverses of each other, other than by multiplying them. There is a book "Guide to Elliptic Curve Cryptography" by Menezes, Vanstone, and some other authors that has a lot of info about optimizing elliptic curve arithmetic in software, if you think that might be of any help. 173.228.123.207 (talk) 21:15, 1 October 2019 (UTC)

If you had a small set of possible points, a look-up table could work. But this rapidly becomes worse than multiplying as the number of possible points increases. SinisterLefty (talk) 21:24, 1 October 2019 (UTC)

Smallest grid with four orientation and every possible 2x2 combination in it.

Assume square tiles with an arrow pointing North on them, they can be rotated so that it points East, South or West. How large of a grid of these tiles do you need for *every* possible foursquare to be present somewhere in the grid (they can overlap)?Naraht (talk) 12:12, 25 September 2019 (UTC)

This sounds like homework, so I won't do it, but maybe I could put an upper limit on it. With 4 possibilities per square a 2x2 grid should have 4⁴ = 256 possible combos. Here I assume that rotations and mirror images do count as a different grid. In the big grid, each interior square could be in up to 4 different 2x2 grids, each edge square in up to 2, and each corner square is in only one 2x2 grid. So, if the large grid is LxH, we get LH squares, and from that a count of { 4(L-2)(H-2) + 2(2)(L-2) + 2(2)(H-2) + 1(4) } / 4 or (L-2)(H-2) + (L-2) + (H-2) + 1 of the 2x2 grids. From that it looks like an 17x17 grid should have enough potential 2x2 grids. However, whether it's possible to get 100% efficiency or we need a larger grid to account for duplicate 2x2 grids, I can't say. SinisterLefty (talk) 14:35, 25 September 2019 (UTC)

• NOT* Homework. I'm 25 years out of college *with* a math degree and a quilter. This was an effort to determine how many squares are needed to cover all of the possibilities for curved piecing (https://www.youtube.com/watch?v=ELd6Gvp0TGk&feature=youtu.be&t=374) there are. NOte, while a single grid may have to by 17 by 17, there is of course the possibility that if done torodially, it would only take 256 squares. I'd also like to find out how smaller it would be if only those four squares with some level of symmetry (so all four combinations quarter circle cutouts with three going northwest and one going northeast don't count.)Naraht (talk) 15:52, 25 September 2019 (UTC)

OK, so the goal is to create a pattern from which every possible 2x2 square could be cut ? If so:

• Yes, a torus (or a sphere) would reduce it to a 16x16 grid, but the difficulty in storing such a shape without putting folds in it and/or stretching it out makes this unwise. It would also be more difficult to make and to use.

• For this application, rotations should be fine, and possibly mirror images, if we are dealing with a fabric with 2 right sides. If it has a right side and a wrong side, then mirroring would not work, although most (possibly all ?) of those 2x2 cases which could be handled by mirroring could also be handled by rotations.

• Assuming you want repeating patterns as in the vid, you would need many copies of the selected 2x2 grid, and hence many copies of the large grid. Seems highly inefficient in terms of wasted material. Selling a single square with an arrow and then allowing the quilter to sew those into 2x2 grids first would be more efficient, although considerably more work for the quilter.

• You would need to define what you meant by only wanting those with "some degree of symmetry".

• Your use of NW and NE confuses me. Have we switched from a 4-point compass rose to 8-point ? If so, then my suggested method of selling individual squares would require two types, one with the arrow pointing toward the edge, and one with it pointing toward the corner. SinisterLefty (talk) 16:59, 25 September 2019 (UTC)

• This seems to be a classic tiling the plane problem (aka Tessellation), a common geometry problem. I don't know the answer, but if you wanted to do some research to find the answer, that would be a good place to start. --Jayron32 17:29, 25 September 2019 (UTC)

Burnside's lemma can be used to find the number of grids; up to rotation I get (4⁴ + 1⋅4²+ 2⋅4¹)/4 = 70 possible. A 9x9 squares has only 64 2x2 subsquares so a lower bound is 10x10. This only has 81 2x2 subsquares which doesn't allow much room to spare, but I'm guessing that 11x11 will be enough, though finding an actual configuration is a different matter. If reflections are allowed then I get (4⁴ + 3⋅4² + 2⋅4¹)/8 = 39 which would make 8x8 a hard lower bound and 9x9 a reasonable guess. The video doesn't seem to match the original problem though since an arrow pointing north has different symmetry than a square with a quarter circle in a corner. This would change the computations somewhat and I don't think the solutions would correspond either.--RDBury (talk) 01:03, 26 September 2019 (UTC)

Restatement of problem

• I am looking at the quarter circles in the video, and as such, the "compass rose" has four points, NE, NW, SE, SW.
• The torus was a suggestion to keep from having to double on the edges, but let's leave that alone for now.
• The backing will be of a completely different color and is not see through.
• Some degree of symmetry as a subproblem is four square with the color circles (ignoring color other than the quarter circles being black and the outside being white) that have any symmetry at all, rotational, or mirrored on any axis (vertical, horizontal or a diagonal)Naraht (talk) 14:05, 26 September 2019 (UTC)

• That degree of symmetry will greatly reduce the number of combos, especially when eliminating the rotations. I suggest you just draw the patterns you want and work out the best layout (overlaps) from there. SinisterLefty (talk) 13:01, 27 September 2019 (UTC)