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

[QUOTE="herege"]i'm able to prove with a probability of 1-2^n if a number is prime or not.[/QUOTE]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.

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

[QUOTE="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.[/QUOTE]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="herege"]Based on Miller-Rabin algorithm we can only say that a number as a probability of being prime of 2^n.[/quote]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.

[QUOTE=herege;91425]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[/QUOTE]

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.

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.

[QUOTE="R.D. Silverman"]A *given* number is prime with probability 0 or probability 1.[/QUOTE]Yes, but a *given* [b]person[/b] might only be sure with a probability somehwere between 0 and 1 that a *given* number is prime.

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

[QUOTE="herege"]Based on MR we can assume that p is prime with a probability of 1-2^-n.[/QUOTE]Hmm, it depends on how many bases you test with. Do you know how to run an MR test?[QUOTE="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[/QUOTE]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.

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

[QUOTE="herege"]So if i execute the algorithm a few times, the probability [of a correct result] becomes 1-2^-n.[/QUOTE]I thought it was more like 1-2^-(2n), (where n is the number of tests run).[QUOTE="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[/QUOTE]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. [color=white]I thought I already said that up there somewhere.[/color]

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.

Pretty much.

I will try that. Thanks for your help.

Best regards.

[QUOTE=herege;91437]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.

Thanks[/QUOTE]

What is n??? If you are going to discuss mathematics, LEARN TO DEFINE
YOUR VARIABLES.

I suggest that you read a paper by Kim & Pomerance in Math. Comp.
I forget the exact title, but it is along the lines of "The probability that a
strong prp is composite".

If one runs MR n times on a candidate p, and it declares the number
prime, the probability that the declaration is in error is much lower than
2^(-2n). The exact probability depends on the size of p. If MR declares
a very large number (at least several hundred digits) to be prime, the
probability is VERY small that the declaration is in error.

Futhermore, each successive trial of MR on a given number (with a different
base for the test) is NOT INDEPENDENT of the preceeding trials. This is
(partially) what the Kim & Pomerance paper is about.

Once we have run MR with a given base (say b), and MR declares the number
prime, and we now run another trial with base b1, the probability of an
erroneous answer with base b1 is not independent of an erroneous answer
with base b. This is because once MR is run, a second run becomes
*conditional* on the first. The fact that the first trial declares a number prime eliminates a lot of candidates that might cause a second trial to err.

BTW, the use of the expression "probability that p is prime" is wrong
headed. p is either prime or composite. What should be said is that
p had been declared prime by a decision procedure and the probability that
the DECISION PROCEDURE IS IN ERROR is small. One can NOT say
"Based on MR we can assume that p is prime with a probability of 1-2^-n."
as you stated above. What we can say is that the probability that the
MR test is in error is 4^-n. (and yes, it is 4^-n, not 2^-n). A number
is either prime or it is not.

When one discusses probability, one MUST base the discussion upon
*random variables* having some probability density function. To do
otherwsie is meaningless blather.

Go read the Kim & Pomerance paper.

[QUOTE=retina;91444]Am I making any sense? It has been a while since I last programmed an MR test.[/QUOTE]

No, you are not making sense. And what has programming MR got to do
with understanding the math behind it??

Do us all a favor. If you are unsure about a subject, then KEEP QUIET.

herege, from your posts my best guess is that you are looking for "logarithm base conversion."

Alex

[QUOTE=akruppa;91496]herege, from your posts my best guess is that you are looking for "logarithm base conversion."

Alex[/QUOTE]

A person who does not know to convert logarithms from one base to
another should probably not be participating in this forum. Their
math background is just too weak. I expect that anyone participating here
has mastered (not just passed) high school math through pre-calculus.
If they haven't, then discussions will be a total mystery to them.

I would never have guessed that herege was looking to solve 2^-n =
10^-k for k. I thought that he was asking how to achieve probability
10^-n with n trials of MR. The former is just too trivial a question.

[QUOTE="R.D. Silverman"]Do us all a favor. If you are unsure about a subject, then KEEP QUIET.[/QUOTE]I don't accapt that statement. I was simply trying to help, if got something wring then so what. Everyone can correct me, or the mods can delete it, I don't mind. The important thing is that the intention is not to belittle or discourage. If one cannot give encouragement then that is the time to keep quiet.

Asking how to convert logarithm bases is a valid math question, if at a pretty elementary level. Not sure if this thread should go into Miscellaneous... it's a beginner's question and was not very well stated, but at least it isn't a "look at teh uber-leet factoring algorithm I found" post.

Alex

[QUOTE=retina;91526]I don't accapt that statement. I was simply trying to help, if got something wring then so what. Everyone can correct me, or the mods can delete it, I don't mind. The important thing is that the intention is not to belittle or discourage. If one cannot give encouragement then that is the time to keep quiet.[/QUOTE]


"then so what"??

The answer is that one adds, rather than detracts from the confusion,
and a less than sophisticated reader would not know the difference.

Indeed, we already knew that the O.P. was less than sophisticated by
the nature of the original question. So how is such a person going to tell
that a supplied "answer" isn't correct?

[QUOTE="R.D. Silverman"]"then so what"??

The answer is that one adds, rather than detracts from the confusion,
and a less than sophisticated reader would not know the difference.

Indeed, we already knew that the O.P. was less than sophisticated by
the nature of the original question. So how is such a person going to tell
that a supplied "answer" isn't correct?[/QUOTE]herege seemed quite satisfied with the result. That is enough for me. It seems the real question herege was asking was finally extracted and thus answered.

I doubt there is any harm in the method used to get there. "With so many mistakes we must surely be learning" (I can't remember who said it but it's a damn good quote). We can't all be right all the time, so mistakes and wrong conclusions will happen occasionally, and so what. It all gets fixed up in the end and we learn something because of it.

If the answer is not correct then there is no harm in someone else politely saying "umm, I think you made a mistake or misunderstood, a better answer is this ...".

Your response to herege about how the probabilty of each test being conditional on previous tests is indeed correct, but how did that help poor herege? herege, I feel quite certain, just needed a simple computation to satisfy his/her need. With you being so quick to measure the sophistication of herege but at the same time not realising that talking about conditional probabilities was most likely not helping seems to be somewhat poor judgement.

[QUOTE="R.D. Silverman"]Go read the Kim & Pomerance paper.[/QUOTE]Do you really think that herege, at his/her level of sophistication that you judged so easily, would be able to understand the Kim & Pomerance paper? Perhaps herege can understand given enough study time, but not everyone has oodles of time to devote to studying every piece of mathematical minutae.

[QUOTE=retina;91579]

Do you really think that herege, at his/her level of sophistication that you judged so easily, would be able to understand the Kim & Pomerance paper? Perhaps herege can understand given enough study time, but not everyone has oodles of time to devote to studying every piece of mathematical minutae.[/QUOTE]

If you want to discuss a subject you need the pre-requisites.
If you are unwilling to do background reading then you should not
get involved.

Your attitude stinks. "oodles of time". If you are not willing to devote the
time to learning and reading what you need to know then take up another
subject.

Yet another instance of the "instant gratification" generation. A person
who wants to participate but is unwilling to spend the necessary time to
acquire needed background.

[QUOTE=akruppa;91554]Asking how to convert logarithm bases is a valid math question, if at a pretty elementary level. Not sure if this thread should go into Miscellaneous... it's a beginner's question and was not very well stated, but at least it isn't a "look at teh uber-leet factoring algorithm I found" post.

Alex[/QUOTE]

But the O.P. did NOT ask: how do I convert 2^-n to 10^-k? What was
asked was:

"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???"

Note the use of the word "diffenter (sic)" [different]. The O.P was
not asking how to convert 2^-n to an EQUIVALENT 10^-k, but was asking
for a different probability: 2^-n vs. 10^-n. Why else use the word "different"???

Asking "If 2^-n = 10^-k then what is k" is so totally a simple question
that it is hard to imagine from the gibberish posted that this is what the O.P.
intended. The wording of the original post strongly suggested that the O.P.
was trying to *improve* the probability of being wrong from 2^-n to 10^-n.

This math is only at the (U.S.) first year high school level or perhaps
the year before in a good math program.

You can't participate if you don't speak the language (math, not English).

[QUOTE="R.D. Silverman"]If you want to discuss a subject you need the pre-requisites.[/QUOTE]But there are no such statements made on this forum stating any pre-requisites. I think it is fair for herege to find a math forum and ask a question. I also think it is fair for me to try to ask for clarification and answer whatever I can. You suggested I keep quiet but where would herege be now if I did?

Without knowing the upbringing or background of the posters it is not fair to judge so quickly. Perhaps it is a simple English language barrier thing, maybe herege was born in some-poor-country and is trying his/her best to learn something to improve his/her life with a better (or any) job. There could be a thousand other reasons why people post and I see no reason to keep quiet when I might be able to help.

But, never mind, I think I might have caught you on a bad day. Perhaps tomorrow will be a better day.

[quote=R.D. Silverman;91583]If you want to discuss a subject you need the pre-requisites.[/quote]Perhaps you recall exchanges you and I had a while back about the differences between this public forum and a formal classroom. As retina points out, no prerequisites (other than simple mersenneforum.org registration) have been placed on participation in this forum by the forum administration.

[quote]If you are unwilling to do background reading then you should not get involved.[/quote]I remind you that [I]your[/I] background reading should have included the rules, regulations, and prerequisites of this forum, and that, therefore, you should be aware that no prerequisites of the sort you seem to demand here actually pertain to this forum.

So it looks like [I]you[/I] are the one who is here deficient in prerequisites. I write "looks like" because I'm sure you actually have been aware of all forum prerequisites, including the absence of any required reading, knowledge, and so forth, in the past, but have just temporarily forgotten some of that recently.

[quote]Your attitude stinks.[/quote]Ahem.

[quote]Yet another instance of the "instant gratification" generation.[/quote]That's a mistaken attribution.

retina and you obviously have some differences in worldview along the lines of those I have not yet :blush: summarized from George Lakoff (a project in progress). It's not a generational matter.

Closing this thread before it devolves into yet another neverending snipe and countersnipe fest -- if anyone has anything further to add regarding the substance of the original thread topic, PM me.

[QUOTE=R.D. Silverman;91451]What we can say is that the probability that the
MR test is in error is 4^-n. (and yes, it is 4^-n, not 2^-n). [/QUOTE]

Bob, if you're going to require precise statements from all participants, then you must also allow me to be pernickety.

Your statement quoted above is just plain wrong. I'm certain you've already done your background reading so I'll have to assume you failed to proof-read your post carefully enough. :wink:

The probability of the result of a single MR test on integer N to base b, where 1 < b < N, being in error is [b]at most[/b] 1/4. For provably most integers, the probability of error is much less than 1/4.

It took me ages to get this concept over to the PGP developers in the mid-90s. They kept wanting to run numerous tests, even though one or two MR tests are easily sufficient for the purpose. (In the early 90s I spent even longer persuading them that a MR-test was better than the Fermat test they were then using --- it's faster, has a lower probability of failure in the average case and a much much better reliability in the worst case.)


Paul