Current research topics

At ArgoTech we believe that a strong emphasis on novel research will keep us at the leading edge of software technology. We are particularly involved in fast arithmetic algorithms and implementation methods with applications in domains such as cryptography and signal processing. Some highlights are in the particular area of curves and finite field arithmetic:

  • Theoretical work on counting points on elliptic curves.
  • Implementation of the above in our ECPC product. For results at cryptographic sizes and larger “research level” sizes, see immediately below.
  • Note: demos of the above are available.
  • Extension to hyperelliptic curves of genus 2 (pure research!)

ECPC Results

The first version of ECPC was our efficient implementation of the Satoh-FGH algorithm, described below. It sped up the computation of elliptic-curve group sizes by a factor of about 6 (or more for large fields) over what had previously been possible.

ECPC v2 implemented a new (patent-pending) method based on a non-converging AGM iteration, which gained a factor of about 8 in speed, while reducing memory usage to a negligible amount, at least for cryptographic sized curves. ECPC v3 had many internal improvements and used a fast ‘norm’ algorithm to gain another factor of 3 or so in speed.

The current version is ECPC v4 which uses an asymptotically and practically faster algorithm, which gains a factor ranging from 2 or 3 at small sizes up to 30 or more for record sizes.

Table 1: Time for counting one arbitrary curve with ECPC v4.

Alpha EV6
750 MHz
Pentium III
1 GHz
163 0.06 sec 0.09 sec
197 0.09 sec 0.15 sec
239 0.13 sec 0.22 sec
283 0.29 sec 0.46 sec
409 0.70 sec 1.17 sec
571 1.74 sec 3.25 sec
1000 5.91 sec 11.17 sec

ECPC can be used for cryptographic key generation. The following table describes the runtime for curves used in elliptic-curve cryptography using v3. For instance a secure 163-bit curve can be generated in 2 seconds on average by trying about 70 random curves, filtering out ¾’s of them using an early-abort strategy and counting the remaining ones to find those whose number of points is twice a prime. The resulting ECC key is roughly as secure as a 1000-bit RSA key.

Table 2: Secure curve generation times
WARNING: ECPC v4 times not yet available.

Alpha EV6
750 MHz
163 2 sec
197 5 sec
239 8 sec

For information on record results, please head over to this page.

Technical Description of ECPC v1

Please note: A technical description of the more recent ECPC versions will be available soon!

The following is a brief technical explanation of the Satoh-FGH point-counting algorithm used in ECPC v1. It was designed by Robert Harley at ArgoTech with Gaudry, Fouquet and Morain at the Computer Science Laboratory of École Polytechnique, by extending the ideas reported by Professor Satoh in his preprint [Sat] to apply in characteristic two (and three) as described in [FGH]. We refer to the algorithm as Satoh-FGH to distinguish it from a different extension designed by Berit Skjernaa.

The input to the algorithm is an elliptic curve E: y2 + x·y = x3 + a6 defined over a finite field Fq where q = 2d.

First of all it is necessary to lift the curve E up to a curve defined over a certain 2-adic ring Zq above Fq. Intuitively, Zq is to Fq as the 2-adic integers Z2 are to the 2-element field F2. More precisely, Zq is the unique (unramified) discrete valuation ring having residue field Fq. By a result of Lubin-Serre-Tate, there is a canonical way to lift E by lifting its j-invariant from Fq to Zq using the modular polynomial Phi2. A direct implementation of LST would be slow due to computations of the (rather complicated) Frobenius in Zq.

The remarkable efficiency of the algorithm comes from an insight by Pr. Satoh: rather than lifting j up to J in isolation, it is faster to lift j along with all its conjugates ji simultaneously. Indeed writing out the equations Phi2(Ji, Ji+1) for 0 <= i < d yields an algebraic system over Zqwithout Frobenius, which can be solved quickly by a multi-variate Newton iteration.

The first stage of Satoh-FGH is thus to compute all the Ji‘s to 2-adic precision O(2n) where n = ceiling(d/2)+1.

Next for each i we find a curve y2 + x·y = x3 + A6 defined over Zq and having j-invariant Ji. This is done with an ordinary Newton iteration to compute A6 to precision O(2n). Next for each curve, we find (half of) the X-coordinate of the non-trivial point in the kernel of the dual isogeny of the Frobenius. This is done with another Newton iteration to precision O(2n-1).

Now, the trace of Frobenius can be written as a norm from Zq to Z2 of a certain partial trace. Each triple (Ji, A6, X) allows us to compute the square of one of the conjugate partial traces, using the formulae of Vélu, to precision O(2n+2).

To finish, we compute the product of these conjugates and take a 2-adic square root, yielding the trace c of Frobenius to precision O(2n+1), except for its sign. As is well known, c is confined to the interval -2d/2+1,...,2d/2+1. Since it is necessarily equal to 1 modulo 4, the number of points q+1-c can be determined exactly.

Much more detail may of course be found in the referenced papers. And here is an easy read.


[FGH]:Mireille Fouquet, Pierrick Gaudry, Robert Harley,”An extension of Satoh’s algorithm and its implementation“,Journal of the Ramanujan Mathematical Society,vol. 15, pp. 281-318 (2000).[Sat]:Takakazu Satoh,”The Canonical Lift of an Ordinary Elliptic Curve over a Finite Field and its Point Counting“,Journal of the Ramanujan Mathematical Society,vol. 15, pp. 247-270 (2000).



What is the ECPC suite?

ArgoTech has developed a suite of programs using new mathematical breakthroughs which dramatically speed up the generation of secure curves for elliptic curve cryptography. The suite is dubbed ECPC, for Elliptic Curve Point Counting. It will allow a significant advance in the quality of security offered, with particular application to low-power devices.

Why use cryptography?

Businesses are moving en masse to the Net, hundreds of millions of people are online and there is no doubt that in the 21st century the Internet economy will be worth trillions of dollars annually. All this activity is vulnerable unless properly secured. Privacy of communications, security of transactions and confidence in their strength are crucial ingredients for the growth of electronic commerce.

As a result there is strong demand for cryptographic software and related services, and this sector is on course to continue its very rapid growth. Among companies currently specialized in securing business-to-business transactions on the Internet: Verisign, RSA Security, Entrust Technologies and Baltimore Technologies have a combined market capitalization of about $10 billion.

Why use elliptic curves?

Public-key cryptography, is a vital component for securing electronic communications and transactions, for user authentication, for digital signatures and so on. This is a system under which each participant generates an encoding key and makes it public, while keeping an accompanying decoding key private. The alternative system is to generate a single secret key and communicate it only to selected recipients; the secret key is typically communicated using a public key!

The security of public-key systems is built on the difficulty of solving certain hard mathematical problems. The three principal systems are based on integer factorization (for the RSA algorithm), elliptic curves (for ECC i.e., elliptic-curve cryptography) and discrete logarithms in finite fields. Each method involves a function that is easy to compute but whose inverse is extremely difficult to compute. The size of the key to be used must be chosen so that the inverse is totally impossible to compute in practice, both now and throughout the useful lifetime of the data.

In the case of ECC the difficulty of the underlying problem grows exponentially with the key-size. This means that ECC offers high levels of security, even with small keys. For instance, RSA requires keys of at least 1000 bits to be secure whereas ECC is secure with keys six times smaller. Small keys have many advantages including faster calculations that use less CPU time and battery power. These advantages become especially significant in low-power devices such as mobile phones, PDAs, palm-top computers, and numerous embedded chips.

Why generate elliptic curves with ECPC?

The initial step in cryptographic protocols based on ECC is to choose a secure elliptic curve to form part of the key. It is essential to know the cardinality i.e., the number of points on the curve, in order to check that it is divisible by a large prime number. Before ECPC, computing the cardinality was a time consuming and cumbersome process.

In order to circumvent this problem, vendors of ECC software have resorted to various compromises. One involves the selection of curves with special mathematical properties which make it easy to determine their cardinality. However this is now understood to be a risky proposition because the very same properties are likely to make such special curves vulnerable to attack by sophisticated mathematical methods. One example of such a weakness has been demonstrated by ArgoTech’s expert mathematician Robert Harley.

Another more recent approach is selection from a short-list of standard curves drawn up by the U.S. National Security Agency. This list is the subject of intense scrutiny and wide-spread use of such a small number of curves could lead to wide-spread failure if any weaknesses are discovered.

It is now widely accepted among researchers in cryptography that the ideal method for generating the most secure curves is to pick arbitrary curves at random and select those whose cardinality is divisible by a large prime. Previously this ideal process took hours of computation on a powerful workstation, whereas now with ECPC it can be performed in one minute on an ordinary server or PC.

Commercial implications of the ECPC suite.

The ECPC suite employs the fastest algorithms recently developed by Robert Harley with academic colleagues at École Polytechnique and University of Paris. ArgoTech’s proprietary implementation, ECPC, dramatically increases the speed of computing cardinalities and selecting secure curves suitable for cryptographic use.

ECPC is the only high-performance implementation of these methods that is available. It uses state of the art computational techniques to make it the fastest and most compact implementation likely to appear for several years. ECPC is also a tool of considerable interest to researchers, who could use it to explore computational aspects of elliptic curves not previously within reach. Previous records in determining the cardinality of elliptic curves have been shattered using ECPC with the record now standing at a key-size of 15013 bits, set by Robert Harley and colleagues.

For commercial cryptographic purposes, keys of 200 bits are more than sufficient. With ECPC it is now possible to generate a secure random curve of such a size in 8 seconds on average. The smallest useful curves e.g., the 113-bit ones recommended for short-term security during key-exchange in the WAP standard, can even be generated in ten seconds on a low-power StrongARM chip using 36 K of RAM.

One can envisage, for example, a company such as a bank managing sensitive information over a closed network, generating optimally secure curves in-house on a daily basis. The enhancement in security and in the perception of security would be significant.

It is now possible to create ECC systems many times faster than before, with the highest possible level of security, guaranteed free from external interference; they can be customized to individual workgroups and updated at will. In addition, this security and flexibility can be incorporated in the rapidly growing network of low-power clients using the small key sizes enabled by ECC.


Software Development

ArgoTech makes use of the latest research results to produce practical applications with unbeatable performance. We specialize in creating quality software that incorporates advanced algorithms in areas such as:

  • Number theory and algebra, multi-precision arithmetic, primality testing, finite fields, number fields, fast polynomial computations…
  • Cryptography, arithmetic aspects and key generation for public-key methods such as RSA and ECC, etc.
  • Numerical algorithms: precise mathematical library functions, IEEE 754 and high-precision floating point,
  • Signal processing: FFT, DCT, image compression, JPEG, wavelets…

As an example of our achievements in software development at the leading edge of current technology, our ECPC suite (Elliptic Curve Point Counting) speeds up the computation of elliptic-curve group sizes by a factor ranging from ten to several hundred over what is possible with other packages.

The primary application of ECPC is in elliptic-curve cryptography. It rapidly calculates the most secure keys and can do so even on systems with constrained computational power such as mobile electronic devices. In this manner ECPC improves the key generation phase of electronic signatures and Diffie-Hellman type protocols, for instance.

ECPC represents a technological advance because it achieves the best performance possible in its domain, according to current mathematical research. With software of this type, ArgoTech can offer your company a clear technical advantage over competitors and help place you at the heart of the new information and communication technologies.

Business consulting

ArgoTech offers consulting services to solve your managerial and organisational problems and, in addition, to provide you with the most appropriate legal advice and draft contracts. By way of example we can adapt your human resource management policy for the 35-hour working week in France and find a contractual solution taking account of financial incentives to which you may be entitled.

We can also help you to take advantage of the growing French and European markets. ArgoTech can provide the advice necessary to adapt your business plan to local conditions and in particular, precise guidance to help you overcome regulatory obstacles confronting your project. We can also assist you in responding to new market challenges, for instance in creating a new subsidiary if appropriate to improve your organisation’s structure.

We offer practical training to minimise your risks under French and European law. Our courses can be customized to suit your decision-makers and typically cover areas such as:

  • Intellectual property law and trademark law,
  • Droit social (company and labour law),
  • Commercial aspects of penal law.


Products and development

At ArgoTech, our main business is advanced software development. We can develop software components to your specifications. We also design products independently and some of them are available for licensing.

ECPC: Elliptic Curve Point Counting (made easy!)

ECPC is our first and foremost product at the present time. It is a specialized technical product which dramatically speeds up the generation of secure curves for elliptic-curve cryptography. Please see this non-technical pitch describing the advantages of ECPC. There is also a ZDNet article. We are currently seeking a partner, ideally a leading crypto provider, to license ECPC and incorporate it as a part of their software offer. Such a combination would lead to a clear technical superiority over competing crypto toolkits.

Future plans

We are investigating the feasibility of a business software package for automating the somewhat complex design and implementation of BSA and BSPCE plans for French companies (BSA = Bons de Souscription d’Actions, BSPCE = Bons de Souscription de Parts de Créateurs d’Entreprise) to reduce the costly lawyer and accountant time currently required.