Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Let p be an odd primer number and N=2^(p)1. The goal of this problem is to show
- that 2^(N-1) is equivalent to 1 mod N, namely that N passes the Fermat primality
- test for a=2. [Note: This doesn't mean that N is necessarily prime. For example,
- if p=11, N=2047=23*89 and if p=23, then N=8388607=47*178481.] Then, do the following:
- a) Explain why 2^p is equivalent to 1 mod M is true
- b) Show that N-1 is equivalent to 0 mod p
- 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