Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: √ ∞ ≠ ≤ ≥ ≈ ⇒ ∈ Δ θ ∴ ∑ ∫ π -

Login

Username

Password

Not registered yet?

#1 2013-04-07 02:47:40

Agnishom
Real Member
Award: Wink Sherlock

Offline

Miller-Rabin

Somebody please explain me the Miller Rabin Primality test


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'Who are you to judge everything?' -Alokananda
 

#2 2013-04-07 02:49:04

bobbym
Administrator

Offline

Re: Miller-Rabin

It is a probabilistic test for determining primality belonging to the field of computational number theory.


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
 

#3 2013-04-07 02:59:50

Agnishom
Real Member
Award: Wink Sherlock

Offline

Re: Miller-Rabin

Yes, how to do it?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'Who are you to judge everything?' -Alokananda
 

#4 2013-04-07 02:03:23

bobbym
Administrator

Offline

Re: Miller-Rabin

For once Wiki actually did a good job explaining something!!!!

Code:

Input: n > 3, an odd integer to be tested for primality;
Input: k, a parameter that determines the accuracy of the test
Output: composite if n is composite, otherwise probably prime

Go:
write n − 1 as 2^sd with d odd by factoring powers of 2 from n − 1
WitnessLoop: repeat k times:
   pick a random integer a in the range [2, n − 2]
   x ← ad mod n
   if x = 1 or x = n − 1 then do next WitnessLoop
   repeat s − 1 times:
      x ← x^2 mod n
      if x = 1 then return composite
      if x = n − 1 then do next WitnessLoop
   return composite
return probably prime

Can not do any better than that except to do some filling in.


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
 

#5 2013-04-07 02:07:31

Agnishom
Real Member
Award: Wink Sherlock

Offline

Re: Miller-Rabin

And what does this method actually rely on?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'Who are you to judge everything?' -Alokananda
 

#6 2013-04-07 02:11:26

bobbym
Administrator

Offline

Re: Miller-Rabin

A whole lot of number theory and a thing called a strong pseudo prime.


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
 

#7 2013-04-07 02:14:47

Agnishom
Real Member
Award: Wink Sherlock

Offline

Re: Miller-Rabin

Mainly fermat's little theorem?
And what ensures it is strong?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'Who are you to judge everything?' -Alokananda
 

#8 2013-04-07 02:21:42

bobbym
Administrator

Offline

Re: Miller-Rabin

Offhand I never remember that definition of them but I could look it up.

More to the point is the test itself and the fact that it is a non deterministic test.


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
 

#9 2013-04-07 02:32:09

Agnishom
Real Member
Award: Wink Sherlock

Offline

Re: Miller-Rabin

Not the definition but I am asking what gives them a HIGH probability of being prime?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'Who are you to judge everything?' -Alokananda
 

#10 2013-04-07 02:37:16

bobbym
Administrator

Offline

Re: Miller-Rabin

That I do not remember. I am sorry.


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
 

#11 2013-04-07 02:54:02

Agnishom
Real Member
Award: Wink Sherlock

Offline

Re: Miller-Rabin

Thats okay.
Once I know that a number is probably prime, how do I make sure?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'Who are you to judge everything?' -Alokananda
 

#12 2013-04-07 02:58:45

bobbym
Administrator

Offline

Re: Miller-Rabin

Three of your countryman developed the AKS algorithm which is deterministic and fast. Or you can use Miller Rabin.


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
 

#13 2013-04-07 03:07:04

Agnishom
Real Member
Award: Wink Sherlock

Offline

Re: Miller-Rabin

Three of my countrymen? Who are they?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'Who are you to judge everything?' -Alokananda
 

#14 2013-04-07 03:10:34

bobbym
Administrator

Offline

Re: Miller-Rabin

Manindra Agrawal, Neeraj Kayal, and Nitin Saxena


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
 

#15 2013-04-07 03:26:47

Agnishom
Real Member
Award: Wink Sherlock

Offline

Re: Miller-Rabin

I did not know them.

I shall google it


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'Who are you to judge everything?' -Alokananda
 

#16 2013-04-07 03:33:22

bobbym
Administrator

Offline

Re: Miller-Rabin

Are they all three Indians?


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
 

#17 2013-04-07 03:45:33

Agnishom
Real Member
Award: Wink Sherlock

Offline

Re: Miller-Rabin

The names sound so, but how does it matter?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'Who are you to judge everything?' -Alokananda
 

#18 2013-04-07 03:46:42

bobbym
Administrator

Offline

Re: Miller-Rabin

It matters in the sense that I like to differ from the rest of my kind.


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
 

#19 2013-04-07 03:54:48

Agnishom
Real Member
Award: Wink Sherlock

Offline

Re: Miller-Rabin

Would that change the method essentially?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'Who are you to judge everything?' -Alokananda
 

#20 2013-04-07 03:59:57

bobbym
Administrator

Offline

Re: Miller-Rabin

Change the method? I am not understanding you.


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
 

#21 2013-04-07 04:02:07

Agnishom
Real Member
Award: Wink Sherlock

Offline

Re: Miller-Rabin

Me neither big_smile


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'Who are you to judge everything?' -Alokananda
 

#22 2013-04-07 04:09:18

bobbym
Administrator

Offline

Re: Miller-Rabin

The AKS proves a number is prime while the Miller Rabin tells the probability it is prime.


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
 

#23 2013-04-07 11:08:59

anonimnystefy
Real Member

Offline

Re: Miller-Rabin

Or we could just wait for someone to solve the P vs NP problem.


The limit operator is just an excuse for doing something you know you can't.
It's the subject that nobody knows anything about that we can all talk about! ― Richard Feynman
Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment
 

#24 2013-04-07 13:48:29

Agnishom
Real Member
Award: Wink Sherlock

Offline

Re: Miller-Rabin

Who will bell the cat?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'Who are you to judge everything?' -Alokananda
 

#25 2013-04-07 17:39:53

bobbym
Administrator

Offline

Re: Miller-Rabin

Did you have anymore questions about MIller Rabin?


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
 

Board footer

Powered by FluxBB