Opened 12 years ago

Closed 12 years ago

#8505 closed defect (fixed)

random points on elliptic curve misses half the group

Reported by: robertwb Owned by: cremona
Priority: major Milestone: sage-4.4
Component: elliptic curves Keywords:
Cc: Merged in: sage-4.4.alpha1
Authors: Robert Bradshaw, John Cremona Reviewers: John Cremona, Robert Bradshaw
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

This is because it chooses only the first of the (usually) two possible lifts of a random x. Computing both is not more expensive, and this avoids the (expensive) exception creation and throwing as well.

May have a bit of fuzz with #8311.

Attachments (4)

8505-ell-finite-random.patch (2.8 KB) - added by robertwb 12 years ago.
trac_8505-review.patch (4.2 KB) - added by cremona 12 years ago.
replaces previous
trac_8505-review-post-8507.patch (3.0 KB) - added by robertwb 12 years ago.
8505-ell-finite-random-rebased.patch (3.0 KB) - added by robertwb 12 years ago.
Rebased on 4.4.alpha0

Download all attachments as: .zip

Change History (16)

Changed 12 years ago by robertwb

comment:1 Changed 12 years ago by robertwb

  • Status changed from new to needs_review

comment:2 Changed 12 years ago by cremona

Looks ok, will test and report back shortly. (Have to go prove the Mordell-Weil Theorem first....)

comment:3 Changed 12 years ago by cremona

I tested all sage/schemes/elliptic_curves with -long and had one failure:

jec@selmer%sage -t -long "sage/schemes/elliptic_curves/ell_finite_field.py"
**********************************************************************
File "/storage/jec/sage-4.3.4.alpha1/devel/sage-tests/sage/schemes/elliptic_curves/ell_finite_field.py", line 1269:
    sage: E.gens()
Expected:
    ((0 : 7 : 1),)
Got:
    ((0 : 4 : 1),)
**********************************************************************
File "/storage/jec/sage-4.3.4.alpha1/devel/sage-tests/sage/schemes/elliptic_curves/ell_finite_field.py", line 1423:
    sage: for p in prime_range(10000):           #long time (~20s)
          if p != Integer(389):
              G=E.change_ring(GF(p)).abelian_group()
Exception raised:
    Traceback (most recent call last):
      File "/home/jec/sage-current/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/jec/sage-current/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/jec/sage-current/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_24[17]>", line 3, in <module>
        G=E.change_ring(GF(p)).abelian_group()
      File "/home/jec/sage-current/local/lib/python/site-packages/sage/schemes/elliptic_curves/ell_finite_field.py", line 1512, in abelian_group
        Q = self.random_point()
      File "/home/jec/sage-current/local/lib/python/site-packages/sage/schemes/elliptic_curves/ell_finite_field.py", line 380, in random_element
        v = self.lift_x(k.random_element(), all=True)
      File "/home/jec/sage-current/local/lib/python/site-packages/sage/schemes/elliptic_curves/ell_generic.py", line 836, in lift_x
        return [self.point([x, (-b+d)/2, one], check=False) for d in D.sqrt(all=True)]
    TypeError: 'sage.rings.integer_mod.IntegerMod_int' object is not iterable
**********************************************************************
File "/storage/jec/sage-4.3.4.alpha1/devel/sage-tests/sage/schemes/elliptic_curves/ell_finite_field.py", line 336:
    sage: P = E.random_element(); P
Expected:
    (751 : 10581 : 1)
Got:
    (16740 : 12486 : 1)
**********************************************************************
File "/storage/jec/sage-4.3.4.alpha1/devel/sage-tests/sage/schemes/elliptic_curves/ell_finite_field.py", line 347:
    sage: P = E.random_element(); P
Expected:
    (a^3 + a + 5 : 5*a^4 + 6*a^3 + 5*a^2 + 3*a + 6 : 1)
Got:
    (2*a^4 + 3*a^3 + 5*a^2 + 6*a + 4 : 6*a^4 + 4*a^3 + a + 6 : 1)
**********************************************************************
File "/storage/jec/sage-4.3.4.alpha1/devel/sage-tests/sage/schemes/elliptic_curves/ell_finite_field.py", line 358:
    sage: P = E.random_element(); P
Expected:
    (a^4 + a^3 + a : 1 : 1)
Got:
    (a^4 + a^2 + 1 : a^3 + a : 1)
**********************************************************************
3 items had failures:
   1 of  10 in __main__.example_21
   1 of  25 in __main__.example_24
   3 of  20 in __main__.example_9
***Test Failed*** 5 failures.
For whitespace errors, see the file /home/jec/.sage//tmp/.doctest_ell_finit

These are all but one trivial and I'll fix them with a reviewer patch. But the other one looks stranger. So some more investigation is required...watch this space!

Changed 12 years ago by cremona

replaces previous

comment:4 Changed 12 years ago by cremona

My patch (after reviewing and testing the whole sage library) has to be applied *instead* of Robert's, though it still has his tag on it (sorry). It does two things relative to his:

  1. I changed a few doctest outputs for the random point tests. I am worried though, since these changes were not only replacing a point by its negative! Why?
  2. testing with -long revealed a bug in sqrt() for integer-mods: when 0 then the return was 0 and not [0] which broke the new code since it uses the all=true option. This was *only* revealed in the -long test! Take note!!

I left this as "needs review" since it needs someone else (e.g. robertwb) to check my change, especially the one at 2. above, and also I would like to hear views on my other remark under 1.

comment:5 Changed 12 years ago by cremona

PS Robert: why do you care about missing half the group? the only places I know where this function is used do not care (finding random points in order to find generators for the group of points). Are you just being pedantic? We could always add a paramter to the random_point() function which switches on or off this new behaviour?

comment:6 Changed 12 years ago by robertwb

Thanks. I thought I had fixed all the doctest changes. The reason that some tests were changed by more then negation is because there is a second call to random() that updates the state of the random number generator. Regarding remark 2, see #8507. My motivation was actually that when using the all=False flag, half the time an (expensive, especially over non-prime fields) error is raised, but I think the current behavior is better as well. It would be like ZZ.random_element() always returning a positive value.

comment:7 Changed 12 years ago by cremona

  • Authors set to Robert Bradshaw, John Cremona
  • Reviewers set to John Cremona, Robert Bradshaw

Robert, if you are happy with my patch then you could give this a positive review. Or tell me, and I will.

Changed 12 years ago by robertwb

comment:8 Changed 12 years ago by robertwb

  • Status changed from needs_review to positive_review

Yes, I'm happy with it. I re-posted the patch removing the conflict with #8507, just in case that gets into an alpha before this.

Release manager: exactly one of trac_8505-review.patch or trac_8505-review-post-8507.patch should be applied.

comment:9 Changed 12 years ago by jhpalmieri

  • Status changed from positive_review to needs_work

This (" trac_8505-review-post-8507.patch") doesn't apply cleanly to 4.3.5 or to Sage 4.4.alpha0. Please rebase it against 4.4.alpha0, and we'll try hard to get this into 4.4.alpha1.

Changed 12 years ago by robertwb

Rebased on 4.4.alpha0

comment:10 Changed 12 years ago by robertwb

  • Status changed from needs_work to needs_review

comment:11 Changed 12 years ago by robertwb

  • Status changed from needs_review to positive_review

Yep, #8311 touched the same code, but it was trivial to merge. I'm remarking this as positive review because it was just a rebase.

comment:12 Changed 12 years ago by jhpalmieri

  • Merged in set to sage-4.4.alpha1
  • Resolution set to fixed
  • Status changed from positive_review to closed

Merged "8505-ell-finite-random-rebased.patch" into 4.4.alpha1.

Note: See TracTickets for help on using tickets.