(英) |
In this paper, we calculate the quantum space complexity of the $S$-unit group computation quantum algorithm proposed by Biasse and Song (SODA'16). We follow the approach of Barbulescu and Poulalion (AFRICACRYPT'23), and the framework given by de Boer, Ducas, and Fehr (EUROCRYPT'20) and Eisentr"{a}ger, Hallgren, Kitaev, and Song (STOC'14). As applications, we derive the quantum space complexity for the principal ideal problem and the class group computation. |