Advanced Search

Le problème de la primalité est l’un des problèmes les plus simples et les plus anciens de la théorie des nombres. À la fin des années 1970, Adleman, Pomerance et Rumely ont donné le premier algorithme de primalité déterministe, dont le temps de calcul était presque polynomial. Il a fallu 20 années supplémentaires pour qu’Agrawal, Kayal et Saxena donnent un algorithme déterministe de temps de calcul polynomial. L’exposé présentera ces travaux, et il fera également le point sur les différents autres...

Nous décrivons dans cet article les algorithmes nécessaires à une implantation efficace de la méthode de Schoof pour le calcul du nombre de points sur une courbe elliptique dans un corps fini. Nous tentons d’unifier pour cela les idées d’Atkin et d’Elkies. En particulier, nous décrivons le calcul d’équations pour $X_0\left(\ell \right)$, $\ell$ premier, ainsi que le calcul efficace de facteurs des polynômes de division d’une courbe elliptique.

Let $ℰ/\overline{\mathbb{Q}}$ be an elliptic curve having complex multiplication by a given quadratic order of an imaginary quadratic field $𝕂$. The field of definition of $ℰ$ is the ring class field $\Omega$ of the order. If the prime $p$ splits completely in $\Omega$, then we can reduce $ℰ$ modulo one the factors of $p$ and get a curve $E$ defined over ${𝔽}_p$. The trace of the Frobenius of $E$ is known up to sign and we need a fast way to find this sign, in the context of the Elliptic Curve Primality Proving algorithm (ECPP). For this purpose, we propose...

A generalised Weber function is given by ${}_N\left(z\right)=\eta (z/N)/\eta \left(z\right)$, where η(z) is the Dedekind function and N is any integer; the original function corresponds to N=2. We classify the cases where some power ${}_N^e$ evaluated at some quadratic integer generates the ring class field associated to an order of an imaginary quadratic field. We compare the heights of our invariants by giving a general formula for the degree of the modular equation relating ${}_N\left(z\right)$ and j(z). Our ultimate goal is the use of these invariants in constructing...