The history of the construction, organisation and publication of factor tables from 1657 to 1817, in itself a fascinating story, also touches upon many topics of general interest for the history of mathematics. The considerable labour involved in constructing and correcting these tables has pushed mathematicians and calculators to organise themselves in networks. Around 1660 J. Pell was the first to motivate others to calculate a large factor table, for which he saw many applications, from Diophantine...

We discuss how much space is sufficient to decide whether a unary given number n is a prime. We show that O(log log n) space is sufficient for a deterministic Turing machine, if it is equipped with an additional pebble movable along the input tape, and also for an alternating machine, if the space restriction applies only to its accepting computation subtrees. In other words, the language is a prime is in pebble–DSPACE(log log n) and also in accept–ASPACE(log log n). Moreover, if the given n is...

We prove that van Hoeij’s original algorithm to factor univariate polynomials over the rationals runs in polynomial time, as well as natural variants. In particular, our approach also yields polynomial time complexity results for bivariate polynomials over a finite field.

Let $K$ be a number field containing, for some prime $\ell$, the $\ell$-th roots of unity. Let $L$ be a Kummer extension of degree $\ell$ of $K$ characterized by its modulus $𝔪$and its norm group. Let $K_{𝔪}$ be the compositum of degree $\ell$ extensions of $K$ of conductor dividing $𝔪$. Using the vector-space structure of $Gal(K_{𝔪}/K)$, we suggest a modification of the rnfkummer function of PARI/GP which brings the complexity of the computation of an equation of $L$ over $K$ from exponential to linear.

On établit les majorations $\left|M\left(x\right)\right|\le \frac{0.002969x}{{(logx)}^{1/2}}$, valable pour $x\ge 142194,\left|M\left(x\right)\right|\le \frac{0.6437752x}{logx}$ qui est la meilleure majoration possible en $\frac{x}{logx}$ valable pour tout $x\>1(\left|M\left(5\right)\right|=2=\frac{0.6437752\times 5}{log5})$, et d’autres analogues. On montre enfin comment trouver des majorations effectives $\left|M\left(x\right)\right|\>\frac{c_{k}x{(loglogx)}^{2k}}{{(logx)}^k}$ pour tout $k$.

Let $𝒪$ be the maximal order of the cubic field generated by a zero $\epsilon$ of $x^3+(\ell -1)x^2-\ell x-1$ for $\ell \in \mathbb{Z}$, $\ell \ge 3$. We prove that $\epsilon ,\epsilon -1$ is a fundamental pair of units for $𝒪$, if $[𝒪:\mathbb{Z}[\epsilon \left]\right]\le \ell /3.$