[Mac_crypto] Elliptic Curve Point Counting, made easy
R. A. Hettinga
mac_crypto@vmeng.com
Fri, 16 Aug 2002 18:20:24 -0400
--- begin forwarded text
Status: RO
Delivered-To: fork@xent.com
To: fork@xent.com
Subject: Elliptic Curve Point Counting, made easy
From: harley@argote.ch (Robert Harley)
Sender: fork-admin@xent.com
Date: Fri, 16 Aug 2002 22:44:31 +0200 (CEST)
Here are some numbers with the new algorithm for counting points on
elliptic curves (over fields of characteristic 2).
In 1998, Reynald Lercier set a record at 1663 bits in 330 days of CPU
on 266 MHz Alphas. In 1999, Frederik Vercauteren set a record at 1999
bits in 65 days of CPU on 400 MHz PCs.
I've been working on the problem since then. These were measured just
now on Rajit's 750 MHz Alpha:
1009 bits:
Lift: 4.8 s + 0.64 s precomputation.
Norm: 2.6 s + 0.31 s precomputation.
1663 bits:
Lift: 18.5 s + 2.1 s precomputation.
Norm: 7.0 s + 1.9 s precomputation.
1999 bits:
Lift: 29.4 s + 3.6 s precomputation.
Norm: 16.6 s + 3.4 s precomputation.
15013 bits:
Lift: 1 h 39 m + 13 m precomputation
Norm: 39 m + 1 h 41 m precomputation
Bye,
Rob.
.-. Robert.Harley@argote.ch .-.
/ \ .-. Software Development .-. / \
/ \ / \ .-. _ .-. / \ / \
/ \ / \ / \ / \ / \ / \ / \
/ \ / \ / `-' `-' \ / \ / \
\ / `-' ArgoTech `-' \ /
`-' http://argote.ch/ `-'
http://xent.com/mailman/listinfo/fork
--- end forwarded text
--
-----------------
R. A. Hettinga <mailto: rah@ibuc.com>
The Internet Bearer Underwriting Corporation <http://www.ibuc.com/>
44 Farquhar Street, Boston, MA 02131 USA
"... however it may deserve respect for its usefulness and antiquity,
[predicting the end of the world] has not been found agreeable to
experience." -- Edward Gibbon, 'Decline and Fall of the Roman Empire'