As said in the previous post, we will now present Dixon’s algorithm, which is a straightforward implementation of the ideas discussed so far. As we will see, it is still not very fast, but at least it is significantly better than trial division.

# Category Archives: Maths

# Factoring integers—Factor bases

We are now facing the following problem: given an integer $n$ which we wish to factor, find integers $x_1,\dots,x_k$ such that $\prod \left(x_i^2-n\right)$ is a square. We mentioned in the previous post that Kraitchik basically used trial and error to find such values, but still he did not try completely random values.

# Factoring integers—Fermat and Kraitchik

### Fermat

Some integers with no obvious small divisor, such as for example $8051$, are nonetheless easily factored on paper. One need only notice that

\[ 8051 = 8100-49 = 90^2 – 7^2, \]

and use the well-known identity $a^2-b^2 = (a+b)(a-b)$ to find that $8051 = 83\times 97$.

# Polynomial factorisation over finite fields, part 3: Final splitting (Cantor-Zassenhaus)

*(Part of this.)*

We are left with the following problem: given a polynomial $A \in \mathbf{F}_p[X]$ which is known to be squarefree and the product of irreducible factors which are all of degree $d$, find these factors. One algorithm to do this was introduced by Cantor and Zassenhaus in 1981.

# Polynomial factorisation over finite fields, part 2: Distinct degree factorisation

*(Part of this.)*

We now have our squarefree polynomial $A_i$, which is the product of all the factors of $A$ with exponent $i$. Our goal is to factor it into $A_i = A_{i,1}A_{i,2}\dots A_{i,\ell}$, where $A_{i,d}$ is the product of all the factors of $A_i$ of degree $d$. This is much simpler than the squarefree factorisation algorithm; it is essentially based on the fact that, over a field $\mathbf{F}_p$, the irreducible factors of $X^{p^n}-X$ are precisely the (monic) irreducible polynomials whose degree is a divisor of $n$.

# Polynomial factorisation over finite fields, part 1: Squarefree factorisation

*(Continues this post.)*

We wish to factor a polynomial $A$ with coefficients in the finite field $\mathbf{F}_p$ where $p$ is prime. As we stated in the previous post, the first step is to obtain a *squarefree factorisation* of $A$. Namely, we wish to obtain polynomials $A_1,A_2,\dots,A_k$, which are all squarefree and relatively prime, and such that $A = A_1A_2^2\dots A_k^k$. Ultimately, $A_i$ will be precisely the product of all the irreducible factors of $A$ with exponent $i$, which will ensure that all the above conditions are satisfied. We first need some preliminary results.

# The Guillou-Quisquater protocol

Introduced by Guillou and Quisquater in 1988, it is a zero-knowledge identification protocol.

The scenario is as follows: we first have a trusted authority, whom we will name Trent. Trent is trusted by everyone: what he says is true. Trent distributes to all interested parties a secret based on their identity, that he only can compute. Then, when Alice wants to identify to Bob, she uses a zero-knowledge protocol to demonstrate that she knows the secret associated to her identity, but without revealing it (so that Bob cannot subsequently impersonate her).

# Pseudo-random sequences and finite fields

One way to symmetrically encrypt a message is to generate a sequence of bits of the same length as the message, and perform a bitwise exclusive-or between the message and the sequence. Then the recipent performs the same operation, and recovers the original message. (This is one way to construct a *stream cipher*.)

Clearly, the security level provided by such an encryption scheme depends entirely on the way in which the sequence was generated. If it is truly random, then we obtain a so-called *one time-pad*, which, as long as it is used only once, guarantees perfect secrecy. At the other extreme, if the sequence consists of only 0-bits, then the encryption process does nothing at all and an adversary can directly read the message.

# Rapport de TER : Inégalités informationnelles et groupes finis

Mon rapport de TER (Travail d’étude et de recherche) est disponible ici (en français uniquement pour le moment). J’y étudie un résultat de Chan et Yeung qui fait apparaître un lien entre les inégalités de grandeurs informationnelles (au sens de la théorie de Shannon) et la théorie des groupes finis. Le principal attrait de ce résultat est qu’il permet potentiellement d’utiliser les nombreux résultats de la théorie des groupes pour prouver de nouvelles inégalités de grandeurs informationnelles.

# Secret-sharing with polynomials

Suppose you have a secret you wish to transmit to $n$ people, but in such a way that all of those $n$ people must collaborate in order for the secret to be revealed. In other words, it must not be possible for even $n-1$ of those people to obtain the secret, even partially, if the $n$th person does not cooperate.