Introduction to Cryptography with Open-Source Software

Public-key cryptosystems based on factoring 113

The pseudo-random sequence is easily generated by sta rting with, s ay x

0

=

2 (althoug h any value will do), and defining

x

k

= f (x

k−1

)

for all k ≥ 1 for some non-linear function f. In practise a simple quadratic is

used, such as

f(x) = x

2

+ 1.

To find the values i and j, produce a subsequence of the original sequence by

taking every second term. For example, suppo se n = 17 ·19 = 323. There will

be two sequences x

i

and y

i

:

x

0

x

1

x

2

x

3

x

4

x

5

x

6

x

7

x

8

x

9

x

10

x

11

x

12

2 5 2 6 31 316 50 240 107 145 31 316 50 240

y

0

y

1

y

2

y

3

y

4

y

5

y

6

with the x

i

sequence starting to repeat at x

3

with a per iod of six; the first

period is shown with an over-bar. ...