Number Theorem

[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

[retina]

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.

[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.

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

[retina]

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.

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.

[R.D. Silverman]

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.

[Wacky]

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.

[retina]

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.

[herege]

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

[retina]

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?

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.

[herege]

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

[retina]

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).

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.