CWI Cryptology Group

Abstract: Some factorization and discrete logarithm algorithms have a linear algebra phase, where a huge sparse system must be solved over a finite field. One avoids a memory explosion by using iterative methods, but run time can remain high. We describe how to parallelize the linear algebra and relate our experiences.

Abstract: We survey some applications that involve spectral analysis in various domains. First one is the analysis of classic Pollard Rho. Second one stems from the question if all elliptic curves of the same order over a finite field have the same difficulty of discrete log. The third one involves the design of a stream cipher called MV3. This is joint work with Steve Miller (Rutgers), David Jao (Waterloo).

Abstract: Height functions describe in a certain sense the arithmetic complexity of an algebraic number or more generally of an algebraic variety.
We will present which kind of lower bounds for the height of algebraic varieties (Bogomolov's problem) and points of such varieties one can expect.
Even if most of the results can be stated for semi-abelian varieties, we will mainly deal with the torus case, roughly speaking G_m×... ×G_m over the algebraic closure of Q

Abstract: From a string of zeros and ones of finite length we construct a stepped line that we call a cutting path. By projecting the integer points on this path onto the y-axis, we form a new string of zeros and ones. If σ is a Sturmian substitution, we apply this process to u_n=σⁿ(0) to define a sequence of words v_n. We will show that if σ has an incidence matrix with determinant 1, then there exists a Sturmian substitution τ such that v_n=τ(v_n-1) for every n >1.