All My Notes On Solving Modular Square Root In BQP With an Oracle For GENERATORS
updated, 04-21-2026, 1:10 p.m. All steps and most facts for MSR proof. 1 - Use the railtracks definition from the other file, DL.txt. Call it "tracks" not "railtracks." 2 - Recall that we have a "generator oracle," that takes as input an integer M and strings of bits and blanks and returns true if the blanks could be filled in with bits so that the final bit string represents a generator of the integer M. 3 - Given the integer M: Use Shor's algorithm to factor it into prime factors. Then, using the Chinese Remainder Theorem, take a in the expression x^2 = a (mod M), and write it as: a (mod p_1^k_1), a (mod p_2^k_2), ... , a (mod p_j^k_3) ...where j is the number of distinct prime factors that M has. 4 - Now, find generators for each group (mod p_i^k) for each integer i from 1 to j. Use the oracle, which works for any modulus integer p^k where p is prime and k is a natural number, including 1. 5 - Importantly, if we fix an arbitrary one of our modu...