Exponential Congruences - Introduction to Cryptography with Java Applets - page 239

Calculate the lnr of x z modulo p . If the least nonnegative residue is 1 modulo p , x is
not a generator. Return to step 1.

b)

3. x is a generator modulo p .

E XAMPLE . Here we generate a safe prime p , and then a generator for p . This will be simple
because we will know the factorization of p 1 by our method of construction. We begin
by finding a large random prime t :

t = 106134897172928103943918854073295879814210153054070185316305605667648
115167285318268319586681005150020607472483671576748374031351891166746019
548973818467282112460367080990486066014392977005040386442558294459608658
668158933760001311189926258441385295561653708006547249455162460344775949
000288933247779568497479.

begins with the value
1, and increments by 1 for each iteration. It turns out that this happens when

We will now search for the first prime of the form 2 rt + 1, where r

r reaches the

value 362, and the target safe prime p is

p = 768416655531999472553972503490662169854881508111468141690052585033772

353811145704262633807570477286149198100781782215658227986987692047241181
534570445703122494213057666371119117944205153516492397844122051887566688
757470680422409493015066111115629539866372845967402086055376212896177870
76209187671392407592174797.

(You may wish to verify that p is, indeed, 2 362 t + 1, and is prime.) Since r = 362 is a

relatively small integer, it can be easily factored. The prime factorization of r is:

r

= 362 = 2 181

x p x

Now we generate another random integer between 2 and 2. Let us choose = 2.

x p

We test if is a generator by raising it to all of the following powers modulo :

( p 1)/2

x

768416655531999472553972503490662169854881508111468141690052585033772353
811145704262633807570477286149198100781782215658227986987692047241181534
570445703122494213057666371119117944205153516492397844122051887566688757
470680422409493015066111115629539866372845967402086055376212896177870762
09187671392407592174796 (mod p )

( p 1)/181

x

759610078033092819549168009542029758562732552302229095079700578685006509
781787175350810699575676555672711591634685786263572318673572188350335378
422741882791298343532264353436668160520311489609485712535342907357206171
457774990867629982901232534301789080080079058523455688622892974408888364
96564879035543972034961 (mod p )