Factorizing numbers with the Gauss sum technique: NMR implementations

Several physics-based algorithms for factorizing large numbers were recently presented. A notable recent algorthm by Schleich et al. uses Gauss sums for distinguishing between factors and nonfactors. We demonstrate two NMR techniques that evaluate Gauss sums and thus implement their algorithm. The first one is based on differential excitation of a single spin magnetization by a cascade of rf pulses. The second method is based on spatial averaging and selective refocusing of magnetization for Gauss sums corresponding to factors. All factors of 16 637 and 52 882 363 are successfully obtained.

Figure 1

Pulse sequence for the differential excitation method.

Figure 2

Factorization of 52 882 363 using the differential excitation method and the truncation number $M=15$.

Figure 3

Pulse sequence for the spatial averaging method. The initial pulse is an rf pulse that creates transverse magnetization. The Gaussian-shaped second pulse is a magnetic field gradient pulse, and the subsequent rectangular pulses are rf pulses with flip angle $\theta$ and phase ${\varphi }_m$.

Figure 4

Factorization of 16 637 using the spatial averaging method with the truncation number $M=12$.