This paper introduces a new quantum algorithm for integer multiplication that uses no ancilla qubits, achieving sub-quadratic gate complexity. The algorithm operates solely on the input and output registers, with gate counts scaling as $ \mathcal{O}(n^{1+\epsilon}) $ for any $ \epsilon > 0 $, and practical implementations achieving $ \mathcal{O}(n^{1.3}) $. When used in Shor's algorithm for factoring, it results in a circuit with $ \mathcal{O}(n^{2+\epsilon}) $ gates and $ 2n + \mathcal{O}(\log n) $ qubits, which is the best known qubit count for a sub-cubic gate factoring circuit. When used in Regev's factoring algorithm, the gate count is $ \mathcal{O}(n^{1.5+\epsilon}) $. The algorithm also has potential to outperform previous proposals at practical problem sizes, yielding the smallest circuits for classically-verifiable quantum advantage. The algorithm is based on a combination of classical fast multiplication techniques and quantum phase rotations. It leverages the Toom-Cook algorithm to decompose the multiplication into manageable parts, which are then implemented using quantum phase rotations. This approach avoids the need for ancilla qubits by using classical precomputation to eliminate the need for intermediate storage. The algorithm is applied to both classical-quantum and quantum-quantum multiplication, with the latter requiring three registers instead of two. The algorithm also enables an exact quantum Fourier transform with sub-quadratic gate complexity and no ancilla qubits. This is achieved by decomposing the phase rotation into a series of simpler operations that can be implemented efficiently. The algorithm is also applied to modular multiplication, which is essential for Shor's algorithm and other cryptographic protocols. The paper also discusses the practical implications of the algorithm, including the use of measurement-based uncomputation to reduce the number of ancilla qubits. The algorithm is shown to be efficient in both gate count and qubit usage, with significant improvements over previous methods. The results are demonstrated for specific applications, including Shor's algorithm and cryptographic proofs of quantum computational advantage. The algorithm is shown to be compatible with other quantum algorithms and has potential for further optimization.This paper introduces a new quantum algorithm for integer multiplication that uses no ancilla qubits, achieving sub-quadratic gate complexity. The algorithm operates solely on the input and output registers, with gate counts scaling as $ \mathcal{O}(n^{1+\epsilon}) $ for any $ \epsilon > 0 $, and practical implementations achieving $ \mathcal{O}(n^{1.3}) $. When used in Shor's algorithm for factoring, it results in a circuit with $ \mathcal{O}(n^{2+\epsilon}) $ gates and $ 2n + \mathcal{O}(\log n) $ qubits, which is the best known qubit count for a sub-cubic gate factoring circuit. When used in Regev's factoring algorithm, the gate count is $ \mathcal{O}(n^{1.5+\epsilon}) $. The algorithm also has potential to outperform previous proposals at practical problem sizes, yielding the smallest circuits for classically-verifiable quantum advantage. The algorithm is based on a combination of classical fast multiplication techniques and quantum phase rotations. It leverages the Toom-Cook algorithm to decompose the multiplication into manageable parts, which are then implemented using quantum phase rotations. This approach avoids the need for ancilla qubits by using classical precomputation to eliminate the need for intermediate storage. The algorithm is applied to both classical-quantum and quantum-quantum multiplication, with the latter requiring three registers instead of two. The algorithm also enables an exact quantum Fourier transform with sub-quadratic gate complexity and no ancilla qubits. This is achieved by decomposing the phase rotation into a series of simpler operations that can be implemented efficiently. The algorithm is also applied to modular multiplication, which is essential for Shor's algorithm and other cryptographic protocols. The paper also discusses the practical implications of the algorithm, including the use of measurement-based uncomputation to reduce the number of ancilla qubits. The algorithm is shown to be efficient in both gate count and qubit usage, with significant improvements over previous methods. The results are demonstrated for specific applications, including Shor's algorithm and cryptographic proofs of quantum computational advantage. The algorithm is shown to be compatible with other quantum algorithms and has potential for further optimization.