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.

Continue reading

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$.

Continue reading

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.

Continue reading

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).

Continue reading

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.

Continue reading

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.

Continue reading