Elliptic Curves Basics Possible Bug
Back to General discussions forum
I have just had three tries at submitting a solution for this problem. In each case the solution was rejected, despite the fact that the solution agreed with the one supplied by the checker. However, the solution supplied by the checker (in each case) began with a spurious integer value which was not part of the solution. In other words the number of integers given is one more than the required number.
There are also two very minor issues with the problem description.
The first example uses p = 11. This is then followed by a diagram showing points which are clearly not for p = 11. It soon becomes apparent that these are points for p = 19 but it would be helpful to make this clear at an earlier position in the text.
The final example, just before the problem description, finds a result of R = (17,5). The final flip is incorrect. The value of R is actually (17,7) when p = 19.
The problem itself is another really interesting one. I'm sure that the glitch will be easy to fix.
Hello Clive! Thanks for coming to help and test :)
Very sorry for this mistake, hopefully it is fixed now. Initial version of problem suggested to calculate first the "order of the curve" (a kind of self-check), this number was remnant of it (probably, halved or something like this. I forgot to remove it from the code...
Thanks for careful review - I'll go now and take care of the mistakes you've shown in the description!
Rodion, thanks for fixing the bug. However, I have just spotted something else. When I looked more closely at the test data I noticed that, out of 17 sets of data, only one set had two different points. All of the others had a repeated point. I have checked several other sets of test data. Some were entirely made up of repeated points. Two of them had only 1 instance of 2 distinct points. Something appears to be wrong with the part of the problem setter which decides whether to use a single point or two separate points.
Clive, yes, there is such "skew" in data - I noticed it yesterday and haven't yet found good way to fix it.
It seems to be related to the properties of the curves and points.
The code for generation is like this:
if (random value between 1 and 17) mod 3 is 0 then
pick single point and request to "double it"
else
pick a pair of points and request to add them
now execute calculations for result
if result is single point then
add it to test-cases
otherwise
retry
So it looks like many random pairs of points fail to produce single result. I haven't yet understood this fact clearly.
Shall see about amending this. BTW this leads to couple of questions I don't have good understanding about:
- what are cases when adding points produces zero or more than one results (one I suppose when there is a couple of equal roots in the equation)
- in case of point "multiplication" (iteratively adding
P+P+P...) this seemingly is doomed to end sooner or later but how to understand when exactly
Most probably this all is explained somewhere just more googling will help me, though it may happen my math won't be enough to understand explanations :)
UPD: for now to improve data-diversity manually tested several ps which seemingly yield better results on average
and made random pick among them.
(noticed sometimes curve contains points with Y=0, not sure if calculations are correct/unambigous in this case)
Rodion, Given the small size of the values of p in the data sets, another approach could be to take all pairs of points and store the pairs which do give rise to a third point. The problem setter can then pick the required number of pairs (at random) from this list. This should enable you to extend the number of p values that are available (possibly all of them, assuming that you are sticking to prime values of p). This should be well within the 1 second limit for the problem setter since there are typically fewer than 40,000 pairs of points.
Clive, thanks for advice - somehow it didn't occurred to me! Just completed the change you suggested and found that it allowed to avoid couple of related troubles (pairs / points repetition and cases when there are no pairs at all)! Hopefully it works :)
Well, this embarrasses. I think yes, but I don't remember for sure. Will the field work (in relation to inversion particularly) if its size is composite? Checker uses primes, that's true.
I was hinting that p is not always prime in the test cases, e.g. 119 = 7x17 is sometimes used.
Thank you :) this was seemingly too subtle hint for my slowpokish mind :) Now 119 is removed, sorry for inconvenience.