Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ π -¹ ² ³ °

You are not logged in.

- Topics: Active | Unanswered

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'

'Humanity is still kept intact. It remains within.' -Alokananda

**Online**

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,705

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.Of course that result can be rigorously obtained, but who cares?Combinatorics is Algebra and Algebra is Combinatorics.**

Offline

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'

'Humanity is still kept intact. It remains within.' -Alokananda

**Online**

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,705

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

```
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^s·d 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.Of course that result can be rigorously obtained, but who cares?Combinatorics is Algebra and Algebra is Combinatorics.**

Offline

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'

'Humanity is still kept intact. It remains within.' -Alokananda

**Online**

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,705

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.Of course that result can be rigorously obtained, but who cares?Combinatorics is Algebra and Algebra is Combinatorics.**

Offline

Mainly fermat's little theorem?

And what ensures it is strong?

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

'Humanity is still kept intact. It remains within.' -Alokananda

**Online**

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,705

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.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

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

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

'Humanity is still kept intact. It remains within.' -Alokananda

**Online**

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,705

That I do not remember. I am sorry.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

Thats okay.

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

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

'Humanity is still kept intact. It remains within.' -Alokananda

**Online**

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,705

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

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

Three of my countrymen? Who are they?

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

'Humanity is still kept intact. It remains within.' -Alokananda

**Online**

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,705

Manindra Agrawal, Neeraj Kayal, and Nitin Saxena

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

I did not know them.

I shall google it

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

'Humanity is still kept intact. It remains within.' -Alokananda

**Online**

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,705

Are they all three Indians?

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

The names sound so, but how does it matter?

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

'Humanity is still kept intact. It remains within.' -Alokananda

**Online**

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,705

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

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

Would that change the method essentially?

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

'Humanity is still kept intact. It remains within.' -Alokananda

**Online**

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,705

Change the method? I am not understanding you.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

Me neither

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

'Humanity is still kept intact. It remains within.' -Alokananda

**Online**

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,705

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

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

**anonimnystefy****Real Member**- From: The Foundation
- Registered: 2011-05-23
- Posts: 15,525

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

Here lies the reader who will never open this book. He is forever dead.

Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment

Offline

Who will bell the cat?

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

'Humanity is still kept intact. It remains within.' -Alokananda

**Online**

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,705

Did you have anymore questions about MIller Rabin?

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline