# How i can solve the problem of primitive root?

26 ビュー (過去 30 日間)

Hello matalb community.
Why not all the values of p shows?, where there are (NaN) values in the array of y
p = 54497; % p is a prime number
a=3; % a is a primitive root to p
for i = 1:p-1
y(i) = mod(power(a,i),p);
end

サインインしてコメントする。

### 採用された回答

John D'Errico 2022 年 11 月 26 日

What you mistake is that a and p are represented as DOUBLES. Can you compute a number as you want to do? What happens?
a = 3;
p = 54497;
x = 21666;
power(a,x)
ans = Inf
Do you see there are precision problems? Double precision arithmetic overflows when you try to compute those large powers. And then mod must fail.
Instead, while you CAN use syms to compute the moduli, it is far better to learn about the powermod function.
powermod(3,x,p)
ans = 1521
Powermod EFFICIENTLY compute the modulus here, without ever computing the number a^x, and so we won't see an overflow, at least not until the modulus gets too large.
y = zeros(100,1);
for i = 1:100
y(i) = powermod(a,i,p);
end
table((1:100)',y)
ans = 100×2 table
Var1 y ____ _____ 1 3 2 9 3 27 4 81 5 243 6 729 7 2187 8 6561 9 19683 10 4552 11 13656 12 40968 13 13910 14 41730 15 16196 16 48588
However, it sounds as if you want to know how to solve for the primitive roots modulo some prime.
"In particular, for a to be a primitive root modulo n, φ(n) has to be the smallest power of a that is congruent to 1 modulo n."
We would also learn that
If a is a primitive root modulo a prime p, then mod(a.^(p-1)/2,p) == p-1.
Remember, for n prime, the Euler Totient function has the property that phi(n)==n-1.
What, for example, are the primitive roots of 11? This will be the set of integers r in the interval [2,n-2], such that
powermod(r,(n-1)/2,n) == -1 == n-1 (mod n)
n = 11;
rtest = 2:n-2;
primitiveroots = rtest(powermod(rtest,(n-1)/2,n) == n-1)
primitiveroots = 1×4
2 6 7 8
And on that wiki page, we would see the primitive roots of 11 are [2,6,7,8].
Finally, we would see this comment:
No simple general formula to compute primitive roots modulo n is known.
So, at best, for a large prime modulus, the above computation seems about the best you can do.
##### 1 件のコメント表示非表示 なし
Thank you so much...

サインインしてコメントする。

### カテゴリ

Find more on Number Theory in Help Center and File Exchange

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!