This paper introduces a novel paradigm for sub-quadratic-time quantum integer multiplication that does not require any ancilla qubits. The authors achieve an asymptotic gate count of $\mathcal{O}(n^{1+\epsilon})$ for any $\epsilon > 0$, with practical scalings as low as $\mathcal{O}(n^{1.3})$. This algorithm is particularly useful in quantum algorithms such as Shor's algorithm for factoring, where it yields a circuit with $\mathcal{O}(n^{2+\epsilon})$ gates and only $2n + \mathcal{O}(\log n)$ qubits. The technique is also applicable to Regev's recent factoring algorithm, achieving a gate count of $\mathcal{O}(n^{1.5+\epsilon})$. The paper demonstrates that this algorithm can outperform previous proposals in terms of qubit count and gate count for problem sizes relevant in practice, including the smallest circuits known for classically-verifiable quantum advantage. The authors achieve this by combining classical fast multiplication algorithms with quantum phase rotations, leveraging the reversibility of addition to avoid the need for ancilla qubits. The paper also discusses space-time trade-offs, including base case optimization, implementing arbitrary phase rotations with low overhead, and achieving sub-linear circuit depth. Finally, the authors explore the application of their fast quantum multiplication algorithm in Shor's algorithm for factoring and a cryptographic proof of quantum computational advantage, showing promising results in terms of gate and qubit counts.This paper introduces a novel paradigm for sub-quadratic-time quantum integer multiplication that does not require any ancilla qubits. The authors achieve an asymptotic gate count of $\mathcal{O}(n^{1+\epsilon})$ for any $\epsilon > 0$, with practical scalings as low as $\mathcal{O}(n^{1.3})$. This algorithm is particularly useful in quantum algorithms such as Shor's algorithm for factoring, where it yields a circuit with $\mathcal{O}(n^{2+\epsilon})$ gates and only $2n + \mathcal{O}(\log n)$ qubits. The technique is also applicable to Regev's recent factoring algorithm, achieving a gate count of $\mathcal{O}(n^{1.5+\epsilon})$. The paper demonstrates that this algorithm can outperform previous proposals in terms of qubit count and gate count for problem sizes relevant in practice, including the smallest circuits known for classically-verifiable quantum advantage. The authors achieve this by combining classical fast multiplication algorithms with quantum phase rotations, leveraging the reversibility of addition to avoid the need for ancilla qubits. The paper also discusses space-time trade-offs, including base case optimization, implementing arbitrary phase rotations with low overhead, and achieving sub-linear circuit depth. Finally, the authors explore the application of their fast quantum multiplication algorithm in Shor's algorithm for factoring and a cryptographic proof of quantum computational advantage, showing promising results in terms of gate and qubit counts.