# Classical Cryptosystems in a Quantum Setting [thesis] by M. Brown

By M. Brown

Read or Download Classical Cryptosystems in a Quantum Setting [thesis] PDF

Best nonfiction_6 books

Wellness and Prevention, An Issue of Primary Care Clinics in Office Practice (The Clinics: Internal Medicine)

This factor covers quite a lot of sufferer matters, together with weight reduction, smoking cessation, pressure, sleep difficulties, workout, and use of supplements. additionally incorporated are articles approximately fighting middle ailment, weight problems, and melanoma.

Additional info for Classical Cryptosystems in a Quantum Setting [thesis]

Example text

M b1 m b2 m If two such fractions cannot be found, return FAIL. 4. Let t = lcm(b1 , b2 ). If t > 5. If f (0) = f (t), return FAIL. 6. Return t. m , 2 return FAIL. 4. 12. 11 finds the correct value of r with probability at least 32 . π4 If it does not return FAIL, it returns a multiple of r. Proof. 8 twice independently, obtaining results yk1 and yk2 . 7, y ki m − ki r ≤ 1 m k1 r and k2 , r respectively. with probability at least 8 π2 for i = 1, and indepen- dently for i = 2. The probability that the inequality is satisfied for both i = 1 and i = 2 is therefore at least 64 .

Otherwise, take r to be the minimum non-FAIL output. 4. If r is odd, return FAIL. 5. Let t = gcd(ar/2 − 1, n). If t = 1, return FAIL. 6. Return t. 14. 13 correctly returns a non-trivial factor of n with probability at least 31 . Proof. For any integer a ∈ {0, 1, . . , n − 1} which is coprime with n and whose order in 34 CHAPTER 3. INTRODUCTION TO QUANTUM ALGORITHMS Z∗n is r, we know that ar ≡ 1 (mod n) ar − 1 ≡ 0 (mod n) (ar/2 − 1)(ar/2 + 1) ≡ 0 (mod n) (if r is even). Since r is the order of a, we know that ar/2 − 1 ≡ 0 (mod n).

It is easily verified that the resulting integers are indeed the four square roots of c. Note that if one or both of p or q is congruent to 1 mod 4, the square roots can still be efficiently computed, but the algorithm is more complicated [MvOV96]. For this reason, during the key generation procedure it makes sense to choose the primes p and q to be congruent to 3 mod 4. It is also interesting to note as in [MvOV96] that Rabin encryption is more efficient than RSA encryption, since it requires a single modular squaring operation.