Advertisement
Guest User

Untitled

a guest
Oct 31st, 2014
125
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.49 KB | None | 0 0
  1. Let p be an odd primer number and N=2^(p)1. The goal of this problem is to show
  2. that 2^(N-1) is equivalent to 1 mod N, namely that N passes the Fermat primality
  3. test for a=2. [Note: This doesn't mean that N is necessarily prime. For example,
  4. if p=11, N=2047=23*89 and if p=23, then N=8388607=47*178481.] Then, do the following:
  5.  
  6. a) Explain why 2^p is equivalent to 1 mod M is true
  7.  
  8. b) Show that N-1 is equivalent to 0 mod p
  9.  
  10. c) Use parts a and b to show that 2^(N-1) is equivalent to 1 mod N
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement