Question

HELP! primitive roots
http://prntscr.com/4lfgrn

Answer 1

order of \(\large a\) in \(\large \mod n \) is defined as the least positive integer \(\large k\) such that :
\[\large a^k \equiv 1 \pmod n \]

Answer 2

you could use trial but first 1,2,3,...k
or use Eluer phi function

Answer 3

how to use phi function here ?

Answer 4

Binary exponentiation will help you out. But note that the order of some such \(a\) divides \(\varphi(n)\)

Answer 5

well
a^16=1 mod 17

so try from 1,....,15
if any of them give a^k=1 mod 17

Answer 6

And, of course, since all of \(n\) are prime, then \(\varphi(n)=n-1\)

Answer 7

is there an easy way to see that order of \(\large a\) divides \(\large \phi(n)\) ?

Answer 8

Sure, I wrote up a proof some time ago, let me find it for you

Answer 9

knowing this fact reduces the number of trials to the divisors of \(\phi(n)\)

Answer 10

http://scriptogr.am/guilleofficial/post/proof-of-eulers-theorem

Answer 11

noo, im not looking for a proof

Answer 12

just want to see it divides intuitively if possible
otherwise ill look up the proof later :)

Answer 13

\(\large \phi(17) = 16\)
so order has to be one of the divisors of \(16\)

is that right ?

Answer 14

Well, the proof is fairly straightforward. It relies on the fact that the product of all of the numbers in the modulus is the same as some constant \(k\) times all of the numbers in the modulus.

Answer 15

That is correct.

Answer 16

because order | \(\large \phi(17)\)

interesting xD

Answer 17

So, it must be either 1, 2, 4, 8, or 16.

Answer 18

it could be {2,4,8}

Answer 19

Oh ok yeah 1 and 16 inclusive

Answer 20

Yessir/ma'am.

Answer 21

\(\large 2^1 \not \equiv 1 \pmod {17} \)
\(\large 2^2 \not \equiv 1 \pmod {17 }\)
\(\large 2^4 \not \equiv 1 \pmod {17} \)
\(\large 2^8 \equiv 1 \pmod {17} \)

so the order of 2 in mod 17 is 8

nice :) thank you both !!

Answer 22

also 8 | 16

Answer 23

I see xD

Answer 24

Yep, and sure thing.

Answer 25

\(\large \phi(19) = 18\)
divisors of 18 = {1,2,3,6,9,18}

ok same story thanks !!

Answer 26

Indeed. Sadly, it turns out there is no simple algorithm to solve this quickly (especially since most current computer security makes use of this fact). This problem is well-known and it is called the 'discrete logarithm.'

Answer 27

cryptography is my next chapter xD
are you saying \(\large k | \phi(n)\) is useful in crypto ?

Answer 28

Well, I'm saying that computing \(a^k\mod u\) for given \(a,k\) is far easier than finding \(k\) such that \(a^k\equiv b\mod u\) is true.

Answer 29

This odd asymmetry in computation is often exploited for security systems. Though the RSA algorithm makes use of the factoring/multiplication problem in some modulus of the product of two large primes.

Answer 30

Got you :) i heard of large primes method before - it relies on the fact that prime factorization is a difficult task

I still don't see how the order method works, but i hopefully learn this by the end of next chapter i hope ! thanks again for all good info :)

Answer 31

ok here is why order | pi(n)

a^pi(n)=1 mod n

a^(p1..p^k)=1 mod n

take p root for both side
idk if u could see it from here

Answer 32

how

\(\large \phi(n) = p1\ldots p^k\)

?

Answer 33

pi(n) always composite :o

Answer 34

wait not k let it be any other variable :P

Answer 35

could you elaborate a bit more

Answer 36

\(\large \phi(n) = p1\ldots p^k\)

is the right hand side, the prime factorization of \(\large \phi(n)\) ?

Answer 37

How the order method works? Well, if we establish that, for all \(m\), \(a^{\varphi(m)}\equiv 1 \mod m\), then it follows that \(\text{ord}(a,m)\;|\;\varphi(m)\). Since, if it didn't, then \(a^{\varphi(m)}\equiv 1 \mod m\) wouldn't hold. (For example, say the order is three but \(\varphi(m)=4\), then \(a^{\varphi(m)} \equiv a^{3+1}\equiv a\), which contradicts our original statement).

Answer 38

very nice :) im looking for exact this kind of nice argument
as the proofs in textbooks don't make sense to me easily

Answer 39

that remainder has to be 0 for the euler's generalization to hold i see

Answer 40

yeah ^^

Answer 41

Yessir/ma'am.

So, the power is in Euler's theorem, pretty much. It also holds for non-prime moduli. The post I put up, though has a fairly simple proof that is easy to follow and is fairly intuitive.

Answer 42

\[\large \phi(n) = ord(n) *q + r \]

\(\large r \) has to be 0, otherwise \(\large a^{ord(n)*q}a^r \equiv 1 \pmod n\)

\(\large a^r \equiv 1 \pmod n\)

Answer 43

\(\large r = 0\)

Answer 44

Yep!

Answer 45

thats not in proper form, but i think i get your proof :)

Answer 46

Well, the point is there, jaja, but you seem to be on the right track.