Re: My brain hurts More than a dozen jokes - thanks guys and girls!
(plus some anti-French abuse from the usual suspect).

Well my brain doesn't hurt so much any more, and it was well worth it.
I've now got an even faster method for elliptic-curve point counting,
both pratically and asymptotically.

It lifts a curve over a field of degree n in time O(n^(2+1/2+eps)),
or O(n^(2+eps)) with precomputation.  Before the best methods took
O(n^(3+eps)) without precomputation, or O(n^(2+1/2+eps)) with it.
The precomputation is done once per field, not per curve, and takes
time O(n^(3+eps)).  Here eps is an arbitrarily small number, hiding
some logarithmic factors.

After lifting, you compute a norm in time O(n^(2+1/3+eps)) to get the
number of points on the curve.

Here's an example over a 1009-bit field, without precomputation, using
a 1 GHz Pentium III:

------------------------------------------------------------------------------
> ./ecpc4 -d 1009 -j 0x123
INFO: -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
INFO: -=-=-=-=-= ECPC: Elliptic Curve Point Counting, made easy! =-=-=-=-=-
INFO: -=-=-=-=-= v4.0.0. (c) ArgoTech 2001. All rights reserved. =-=-=-=-=-
INFO: -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
[...]
INFO: Picked field polynomial 1+x^55+x^1009.
INFO: Starting ECPC on j = 0x123...
INFO: Done after 138.33 seconds.
INFO: Checking... OK OK OK OK OK OK OK OK OK OK
[...]
CURVE: 5486124068793688683255936251187209270074392635932332070112001988456197381759672947165175699536362793613284725337872111744958183862744647903224103718245568925556758419805069056847065147709058947190200192542277555125346128173135573355537502225974504428432790108988791795746287271944131683364548299056172016
[...]
INFO: 1 curve processed.
INFO: Bye!
------------------------------------------------------------------------------


L8r,
  Rob.
     .-.                    Robert.Harley@argote.ch                    .-.
    /   \           .-.      Software Development       .-.           /   \
   /     \         /   \       .-.     _     .-.       /   \         /     \
  /       \       /     \     /   \   / \   /   \     /     \       /       \
 /         \     /       \   /     `-'   `-'     \   /       \     /         \
            \   /         `-'       ArgoTech      `-'         \   /
             `-'                http://argote.ch/              `-'
http://xent.com/mailman/listinfo/fork