Yan - Quantum Attacks on Public-Key Cryptosystems

Fig. 1.1

Definition 1.1.

A standard multitape Turing machine , M (see Fig.), is an algebraic system defined by where

Fig. 1.2

Example 1.1.

Given two positive integers x and y , design a Turing machine that computes x + y . First, we have to choose some convention for representing positive integers. For simplicity, we will use unary notation in which any positive integer x is represented by , such that| w ( x )|= x . Thus in this notation, 4 will be represented by 1111. We must also decide how x and y are placed on the tape initially and how their sum is to appear at the end of the computation. It is assumed that w ( x ) and w ( y ) are on the tape in unary notation, separated by a single 0, with the readwrite head on the leftmost symbol of w ( x ). After the computation, w ( x + y ) will be on the tape followed by a single 0, and the readwrite head will be positioned at the left end of the result. We therefore want to design a Turing machine for performing the computation where q f F is a final state and indicates an unspecified number of steps as follows: Constructing a program for this is relatively simple. All we need to do is to move the separating 0 to the right end of w ( y ), so that the addition amounts to nothing more than the coalition of the two strings. To achieve this, we construct with Note that in moving the 0 right we temporarily create an extra 1, a fact that is remembered by putting the machine into state q 1. The transition ( q 2,1)=( q 3,0, R ) is needed to remove this at the end of the computation. This can be seen from the sequence of instantaneous descriptions for adding 111 to 11: or briefly as follows: