mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Closed Thread
 
Thread Tools
Old 2006-11-14, 10:02   #1
herege
 
Nov 2006

510 Posts
Default Number Theorem

Based on the theorie of numbers - Fermat and Miller-Rabin, i'm able to prove with a probability of 1-2^n if a number is prime or not.

But what if i wanted to proof that a prime number has a diffenter probability.

Say x is prime with a probability of 10^-n???

Thanks.

Best Regards
Nuno
herege is offline  
Old 2006-11-14, 11:25   #2
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

6,563 Posts
Question

Quote:
Originally Posted by herege
i'm able to prove with a probability of 1-2^n if a number is prime or not.
1-2^n? It seems to me to give a valid probability only for n<=0. What are you talking about? Is there a specific question that you have? Or are you trying to state a new theory? Sorry if I am confused, maybe I am just dense.
retina is online now  
Old 2006-11-14, 11:37   #3
herege
 
Nov 2006

516 Posts
Default post

what i would like to figure out is if there is any way to prove that a given number is a prime with a probability less than 10^n.

Based on Miller-Rabin algorithm we can only say that a number as a probability of being prime of 2^n.

Can you help with it?

Thanks
herege is offline  
Old 2006-11-14, 12:15   #4
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

6,563 Posts
Default

Quote:
Originally Posted by herege
what i would like to figure out is if there is any way to prove that a given number is a prime with a probability less than 10^n.
I am going to assume you meant something like 1-10^-n instead of the 10^n you stated. So based on the figure you meant then you can just keep running the MR test until you are satisfied that your probability of error is low enough for you.
Quote:
Originally Posted by herege
Based on Miller-Rabin algorithm we can only say that a number as a probability of being prime of 2^n.
Once again I am going to assume you meant 1-2^-n, instead of 2^n. My (limited) understanding of the MR test is that each base you test gives you a worst case of 1/4 probability of a false result (i.e. a strong pseudo prime to the base tested). So just keep running bases (like I said above) until you get the probability where you want it to be.

Last fiddled with by retina on 2006-11-14 at 12:17 Reason: Stupid typos
retina is online now  
Old 2006-11-14, 12:16   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

5·1,493 Posts
Default

Quote:
Originally Posted by herege View Post
Based on the theorie of numbers - Fermat and Miller-Rabin, i'm able to prove with a probability of 1-2^n if a number is prime or not.

But what if i wanted to proof that a prime number has a diffenter probability.

Say x is prime with a probability of 10^-n???

Thanks.

Best Regards
Nuno
Codswallop. You have no idea what you are talking about.
It is gibberish. To begin with, 1-2^n is *negative* for all n > 0.
Secondly, you blather about variables x and n without defining a
relationship between them.

Finally,

A *given* number is prime with probability 0 or probability 1.
R.D. Silverman is offline  
Old 2006-11-14, 12:18   #6
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

108910 Posts
Default

herege,

"with a probability less than 10^n" does not make sense.

For example, with n=3, you are asking for "a probability less than 1000".

Similarly, in your original question "with a probability of 1-2^n" translates into "a probability of -7".

Perhaps you can again try to get the correct limit on the probability that you seek. If so, then we might be able to understand your question.
Wacky is offline  
Old 2006-11-14, 12:29   #7
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

6,563 Posts
Default

Quote:
Originally Posted by R.D. Silverman
A *given* number is prime with probability 0 or probability 1.
Yes, but a *given* person might only be sure with a probability somehwere between 0 and 1 that a *given* number is prime.
retina is online now  
Old 2006-11-14, 12:34   #8
herege
 
Nov 2006

58 Posts
Default Ler

I posted it in the wrong way.

Let me correct:

Based on MR we can assume that p is prime with a probability of 1-2^-n.

What i wanted was a way to make an algorithm capable of showing that p is prime with a probability of 1-10^-n, that is with an error less than 0.001

Thanks
herege is offline  
Old 2006-11-14, 12:41   #9
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

6,563 Posts
Default

Quote:
Originally Posted by herege
Based on MR we can assume that p is prime with a probability of 1-2^-n.
Hmm, it depends on how many bases you test with. Do you know how to run an MR test?
Quote:
Originally Posted by herege
What i wanted was a way to make an algorithm capable of showing that p is prime with a probability of 1-10^-n, that is with an error less than 0.001
Okay, I thought we might be getting somewhere, but now you don't make any sense to me. If the probability is 1-10^-n then how can the error be 0.001? The error rate would seem to be related by the quality of your system to produce proper results. The probability is related to the mathematics of the MR test.

Try to understand that testing with more and more bases can increase your confidence that the given number is prime. Error rates don't seem to be relevant unless you can't trust you computer system to run the tests.

Oh, yeah, how does p relate to n? Are they supposed to be the same number? R. D. Silverman has already raised this point with you.

Last fiddled with by retina on 2006-11-14 at 12:43 Reason: Added Q about p and n relationship
retina is online now  
Old 2006-11-14, 13:02   #10
herege
 
Nov 2006

5 Posts
Default Read

Thanks Retina for being so patient.

I'm studying the MR test right know.

I beliave i'm starting to realize how it works.

So based on it, i got the following:

If there are any solutions for x^2 = 1 (mod n) besides 1 or -1, then n is not prime.

So with MR algorithm if i test a given number n for primality, and give it a number x < n, i might get that the number n may be prime with a probability of 1|2.
So if i execute the algorithm a few times, the probability becomes 1-2^-n.

What i have to figure out is how to have an algorithm that i can say that for a given number, i can say about it that the probability of being prime is less than 10^-n

Thanks for your answers.

Best ragards
herege is offline  
Old 2006-11-14, 13:19   #11
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

11001101000112 Posts
Default

Quote:
Originally Posted by herege
So if i execute the algorithm a few times, the probability [of a correct result] becomes 1-2^-n.
I thought it was more like 1-2^-(2n), (where n is the number of tests run).
Quote:
Originally Posted by herege
What i have to figure out is how to have an algorithm that i can say that for a given number, i can say about it that the probability of being prime is less than 10^-n
For this the "n" has to be a different "n" from the above, so I will just assume you have some particular "n" that you like to use and try to carry on ... So just run the MR test (with different bases) more times to improve your confidence. I thought I already said that up there somewhere.

Let's say you have in your head n=9, then you want a probability of correct result of 1-10^-9. Note that the number is approximately 1-2^-30. so if we do 15 trial MR test bases that would seem to give a prob of ~1-2^-(2*15). Am I making any sense? It has been a while since I last programmed an MR test.
retina is online now  
Closed Thread

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Basic Number Theory 15: Lagrange's theorem, cyclic groups and modular arithmetic Nick Number Theory Discussion Group 0 2017-01-07 13:15
Basic Number Theory 8: equiv. relations and Fermat's little theorem Nick Number Theory Discussion Group 0 2016-11-10 23:10
Basic Number Theory 6: functions and the Chinese Remainder Theorem Nick Number Theory Discussion Group 4 2016-10-31 22:26
My(?) Three body theorem. davieddy Math 1 2011-08-08 03:14
Another vindication of Gödel's Theorem? devarajkandadai Miscellaneous Math 1 2006-09-22 17:43

All times are UTC. The time now is 05:55.


Sat Aug 20 05:55:54 UTC 2022 up 2 days, 3:24, 0 users, load averages: 1.33, 1.22, 1.19

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔