mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2007-03-15, 23:03   #1
TalX
 

22×34×29 Posts
Default application of euler's phi function

Question using euler's phi function
Let p be an odd prime number, and suppose that p - 1 is not divisible by 3. Prove that, for every integer a, there is an integer x, such that
x^3 is defined as a (mod p).
  Reply With Quote
Old 2007-04-26, 20:07   #2
m_f_h
 
m_f_h's Avatar
 
Feb 2007

24×33 Posts
Default

Quote:
Originally Posted by TalX View Post
..., such that x^3 is defined as a (mod p).
"defined as" = "equal to" ? should this go into the "puzzles" section ?
m_f_h is offline   Reply With Quote
Old 2007-04-27, 08:03   #3
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Puzzles, or maybe homework? Sounds like a typical question on RSA from an Introduction to Cryptography course.

So what you want to prove, I guess, is that for every a (mod p), x3a (mod p) has a unique solution, if p ≡ 2 (mod 3).

One way of going about this proof is using the fact that (Z/pZ)* is a cyclic group, using the isomorphy to the group {0, ..., p-1} with addition, and showing that dividing by three always has a unique solution there (use the extended GCD). Hint: Why is taking cube roots in (Z/pZ)* equivalent to dividing by three in {0, ..., p-1} with addition? I.e., what isomorphic map are we using?

If you never heard any group theory, none of the above might make any sense. But if you're studying RSA, you probably did.

Alex

Last fiddled with by akruppa on 2007-04-27 at 10:05 Reason: Missing ()*
akruppa is offline   Reply With Quote
Old 2007-04-27, 11:50   #4
Citrix
 
Citrix's Avatar
 
Jun 2003

22×397 Posts
Default

There is an easier approach.

X^3=a (mod p)

Then you calculate x^3*n=a^n (mod p) and choose n such that 3*n% (p-1)==1

so you get x=a^n (mod p).

Thus for any given a you can solve for x.

I leave it up to you to show that for all primes such that p%3==2, there exists an n.

(I suspect this to be an homework problem)

Citrix is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Basic Number Theory 7: idempotents and Euler's function Nick Number Theory Discussion Group 17 2016-12-01 14:27
Srsieve Application failed PawnProver44 Information & Answers 12 2016-03-11 00:43
lasievee application pinhodecarlos NFS@Home 2 2013-05-19 20:23
Ports of the application nohero Twin Prime Search 9 2007-06-17 10:12
euler's totient function toilet Math 1 2007-04-29 13:49

All times are UTC. The time now is 09:13.


Fri Aug 12 09:13:35 UTC 2022 up 36 days, 4 hrs, 2 users, load averages: 1.36, 1.22, 1.25

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔