Fermat's little theorem

  • Thread starter Dweirdo
  • Start date
  • #1
174
0
Hi, I have spme questions about Fermat's little theorem-http://en.wikipedia.org/wiki/Fermat%27s_little_theorem. [Broken]

I need to think about a mathematical algorithm to deal with this theorem- finding pseudo-primes ,aka, Carmichael numbers.
When I'm dealing with huge numbers ,it is very difficult,let's say:
a is 5, n is 200
than getting a number like 5^200 is stupid, and thus I need another method which will prevent the calculation of this number.
anybody can point me to the right direction?

another thing that I noticed is, if we do the test for non prime numbers such as 15
then we get pairs of reminders, I mean:
(7^15)%15 =13
(13^15)%15=7
just something cool(it's not just for these numbers!! )

Thanks in advance!

DW
 
Last edited by a moderator:

Answers and Replies

  • #2
907
2
Since 200 = 128 + 64 + 8, all you need is to calculate 5^8 mod 200, 5^64 mod 200, and 5^128 mod 200, and multiply those together ... and it's easy to calculate those because

5^2 mod 200 = ((5 mod 200)*(5 mod 200)) mod 200 = 25

5^4 mod 200 = ((5^2 mod 200)*(5^2 mod 200)) mod 200 = 625 mod 200 = 25

etc.

so you can check each b using simple integer arithmetic in log(n) time.
 
  • #3
174
0
cool,
Thank You hamster! :D
 

Related Threads on Fermat's little theorem

  • Last Post
Replies
5
Views
10K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
7
Views
6K
Replies
1
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
13
Views
3K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
9
Views
4K
  • Last Post
Replies
1
Views
3K
Top