In a recent work in collaboration with Fang Song, I presented the first quantum polynomial time algorithm for computing the S-unit group of a number field for a given set of prime ideals S. This algorithm works for arbitrary classes of number fields, even with large degree. It implies polynomial time algorithms for computing the ideal class group, solving the so-called "Principal Ideal Problem" (PIP), computing ray class groups and solving some norm equations. I will discuss the relevance of the efficient PIP resolution method for cryptography.

In collaboration with David Jao and Anirudh Sankar, I also described a quantum algorithm which finds an isogeny between two given supersingular curves over a finite field. In some cases, this algorithm runs in subexponential time. This can be used to attack quantum-safe cryptographic schemes relying on the hardness of finding an isogeny between two given supersingular curves.

Let $S$ be the set generated by these rules: Let $1\in S$ and if $x\in S$, then $2x\in S$ and $1-x\in S$; so that $S$ grows in generations: \[ \mbox{gen}{(1)} = \{1\}, \mbox{gen}{(2)}=\{0,2\}, \mbox{gen}{(3)} =\{-1,4\} \ldots \] Prove or disprove that each generation contains at least one Fibonacci number or its negative.

In this talk we will discuss the solution using techniques involving the dragon curve, binary sequences and trees.

This is joint work with Karyn McLellan (Mt. St. Vincent University)

Some surprising results occur in the multidimensional setting: addition may be of quadratic rather than linear complexity ($O(n^2)$ instead of $O(n)$, where $n$ is the length of input), and for some addition tables, the standard multidigit addition algorithm may not terminate. Workarounds exist in some cases, making use of an idea similar to the two's complement algorithm for subtraction in one dimension. This talk will briefly review the construction of multidimensional radix representations, will summarize the work recently completed in the Master's thesis of M. ALmutairi, and will present some variations of the addition algorithm that may simplify multidigit addition in the multidimensional setting.

Our present method applies to any finite field of composite extension degree. It exploits the available subfields with a cheap (polynomial-time) linear algebra step, resulting in a much more smooth decomposition of the target. This leads to a new trade-off in the asymptotic complexity of the initial splitting step: it is improved by a factor 2 in the exponent with FFS and $2^{1/3}$ in the exponent with NFS, for any finite field of even extension degree, and with a much smaller smoothness bound. In medium and large characteristic, it can be combined with Pomerance's Early Abort strategy. In small characteristic, it replaces the Waterloo algorithm of Blake, Fuji-Hara, Mullin and Vanstone. Moreover it reduces the width and the height of the following decreasing tree.

In this talk, we describe our on-going efforts to expand and update Devitt's computations, by considering the more-appropriate geometric mean of $s(n)/n$ as opposed to the arithmetic mean considered by Devitt, and greatly extending Devitt's computations using modern factoring algorithms.

This is joint work with K. Chum and R. Guy.

In this talk, we describe that how exactly the infrastructure and the Jacobian are related. We suggest an alternative distance map for the infrastructure in order to improve the efficiency of this structure. We show that the infrastructure with the new distance and the Jacobian have identical performance in practice for cryptographic sized curves. We support this claim both mathematically and computationally.