Ask Your Question
0

primitive root

asked 2013-11-06 10:41:16 -0500

00Luca00 gravatar image

updated 2013-11-06 11:20:26 -0500

I am writing a program to find the primitive root. In the lecture we have given that

x is a primitive root in F_p, where p a prime number, if
x^((p-1)/pi) is not 1. (With pi the prime factors of p-1).

So here my programm:

p = 468889
R = IntegerModRing(p)
factor(p-1)
#gives: p-1 =  2^3 * 3 * 7 * 2791

list = [2,3,7,2791]
c=True

(I changed the for loop:)

for x in range(1,p):
  for pi in list:
    a = (p-1)/pi
    if a == int(a):
        k = R(x^a)
        if k==1:
            c=False
        else:
            print k
    else:
        pass
  if c==True:
    print x
  else:
    print c, x

But still there is no result. Can anyone help? I don't see the problem. Thanks a lot!

edit retag flag offensive close merge delete

2 answers

Sort by » oldest newest most voted
0

answered 2013-11-06 11:18:03 -0500

tmonteil gravatar image

Can you tell us which error you got (I did not get one for a long time, then i stopped the loop) ?

Moreover, in the first pass through the loop (x = 1, p = 2), c get the value False, and it will never become True again, because it is not reset in the loop. So, your code will not print anything !

Also, instead of writing:

if c==True:

you can simply write:

if c:

because c is a boolean, which has value True or False.

Also, you can remove:

else:
    pass
edit flag offensive delete link more
0

answered 2013-11-06 11:39:29 -0500

00Luca00 gravatar image

I found my mistake. In the end there was no error, only, that the programm did not give any primitive root. That's because the

c=True

Must lie inside the first loop. Otherwise it was all the time False if it did not work out once. So the correct version is:

for x in range(1,p):
  c=True
  for pi in list:
    a = (p-1)/pi
    if a == int(a):
        k = R(x^a)
        if k==1:
            c=False
        else:
            print k
    else:
        pass
 if c==True:
    print 'Lösung:', x
    break
 else:
    print c, x
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2013-11-06 10:41:16 -0500

Seen: 1,366 times

Last updated: Nov 06 '13