 mersenneforum.org > Math Number Theorem
 Register FAQ Search Today's Posts Mark Forums Read  2006-11-14, 10:02 #1 herege   Nov 2006 510 Posts 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  2006-11-14, 11:25   #2
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

6,563 Posts 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.  2006-11-14, 11:37 #3 herege   Nov 2006 516 Posts 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  2006-11-14, 12:15   #4
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

6,563 Posts 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  2006-11-14, 12:16   #5
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

5·1,493 Posts Quote:
 Originally Posted by herege 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.  2006-11-14, 12:18 #6 Wacky   Jun 2003 The Texas Hill Country 108910 Posts 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.  2006-11-14, 12:29   #7
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

6,563 Posts 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.  2006-11-14, 12:34 #8 herege   Nov 2006 58 Posts 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  2006-11-14, 12:41   #9
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

6,563 Posts 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  2006-11-14, 13:02 #10 herege   Nov 2006 5 Posts 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  2006-11-14, 13:19   #11
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

11001101000112 Posts 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.  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Nick Number Theory Discussion Group 0 2017-01-07 13:15 Nick Number Theory Discussion Group 0 2016-11-10 23:10 Nick Number Theory Discussion Group 4 2016-10-31 22:26 davieddy Math 1 2011-08-08 03:14 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